Mettre en œuvre la recherche de chemin le plus court pour le labyrinthe

Cet article est l'article du 20e jour du Calendrier de l'Avent Tomowarkar Alone 2019.

introduction

La recherche de priorité de largeur et la recherche de priorité de profondeur semblent être difficiles, donc je n'y ai pas beaucoup parlé, mais j'étais motivé d'une manière ou d'une autre, alors j'ai écrit la recherche d'itinéraire la plus courte pour le labyrinthe.

Le contenu lui-même est quelque chose qui apparaît souvent, et je n'ai rien fait d'inhabituel. Je vais l'écrire sous forme de mémoire et de résultat.

Livrables

image.png

code

def printMaze(maze):
    """Dessine un labyrinthe"""
    for i in range(maze["height"]):
        row = maze["data"][i * maze["width"] : (i + 1) * maze["width"]]
        print(" ".join(row))


def at(x, y, maze):
    """Du labyrinthe(x, y)Renvoie un objet de coordonnées"""
    return maze["data"][y * maze["width"] + x]


def setChar(x, y, char, maze):
    """Du labyrinthe(x, y)Définir l'objet de coordonnées"""
    arr = list(maze["data"])
    arr[y * maze["width"] + x] = char
    maze["data"] = "".join(arr)


if __name__ == "__main__":
    maze = {
        "width": 43,
        "height": 35,
        "data": "###########################################S #   #           #                       ## ### ########### # ################# ### ##   #           # # #               # # # #### ########### # # ##### ##### ### ### # ## #         # # #       # #   # # #     # ## ####### ### # ####### ### ### # ##### # ##         #       #         #     #     # ###### ### ##### ### ##### ### ##### ##### ##   # # # #   # #   # #   #   #     #     ## # # # # ### # # ### ### # ### ### # ### ## # # # #   # # # #     # # #   # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # #       #       #     # #   # # # # ## # # # ##### ### ### ####### ### ### # # ## # # #   # #   # # #           #     # # ## # # ##### ### ### ########### ### ### # ## # #         #             # # # # #   # ## # ##### ### # ### ### ##### # # # ### # ## #     # # # # # #   # #       # #   # # ## ##### ### # ### ##### ### ### # ### # # ##     #     #               # # #   # #   #### # # ### ### ######### ### ### ### ### ## # # # # # #   #       # #             # ## ### ### ### ##### # ### ### ####### ### ##             #   # # #     # #   #   #   ## ### ####### ### ### # ##### ### ### # #### # # # #       #     # #       #   # #   ## # # # ### ### # ##### ##### ##### # ### ## # # # #   # # # #         #       #   # ## # # # # ### ### # # ####### ##### ### # ## # #   # #       # # #       #   # #   # ## # ##### # ####### # ######### ### # ### ## #       #         #               # #   G###########################################",
    }
    start = [0, 1]
    goal = [42, 33]

    visited = [False] * maze["width"] * maze["height"]
    costs = [999999] * maze["width"] * maze["height"]

    #La position de départ(0, 1)Faire la queue
    queue = [start]
    costs[start[1] * maze["width"] + start[0]] = 0

    while len(queue) > 0:
        #Obtenir la position de la file d'attente
        p, queue = queue[0], queue[1:]
        visited[p[1] * maze["width"] + p[0]] = True

        #Vérifiez en haut, en bas, à gauche et à droite
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = p[0] + i[0], p[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue

            if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
                queue.append([x, y])
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
            if at(x, y, maze) == "G":
                queue = []
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
                break
    #Suivez les coûts de l'objectif pour trouver l'itinéraire le plus court
    point = goal
    cost = costs[point[1] * maze["width"] + point[0]]
    while cost != 1:
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = point[0] + i[0], point[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue
            if costs[y * maze["width"] + x] == cost - 1:
                cost = costs[y * maze["width"] + x]
                point = [x, y]
                setChar(x, y, ".", maze)
                break

    printMaze(maze)

Commentaire

Les informations du labyrinthe sont définies comme un type de dictionnaire. " # " Est-ce que le mur "" "est le passage," S ", " G "est respectivement le départ et le but. En même temps, les coordonnées(x, y)` du départ et de l'objectif sont également entrées manuellement.

maze = {
    "width": 43,
    "height": 35,
    "data": "###########################################S #   #           #                       ## ### ########### # ################# ### ##   #           # # #               # # # #### ########### # # ##### ##### ### ### # ## #         # # #       # #   # # #     # ## ####### ### # ####### ### ### # ##### # ##         #       #         #     #     # ###### ### ##### ### ##### ### ##### ##### ##   # # # #   # #   # #   #   #     #     ## # # # # ### # # ### ### # ### ### # ### ## # # # #   # # # #     # # #   # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # #       #       #     # #   # # # # ## # # # ##### ### ### ####### ### ### # # ## # # #   # #   # # #           #     # # ## # # ##### ### ### ########### ### ### # ## # #         #             # # # # #   # ## # ##### ### # ### ### ##### # # # ### # ## #     # # # # # #   # #       # #   # # ## ##### ### # ### ##### ### ### # ### # # ##     #     #               # # #   # #   #### # # ### ### ######### ### ### ### ### ## # # # # # #   #       # #             # ## ### ### ### ##### # ### ### ####### ### ##             #   # # #     # #   #   #   ## ### ####### ### ### # ##### ### ### # #### # # # #       #     # #       #   # #   ## # # # ### ### # ##### ##### ##### # ### ## # # # #   # # # #         #       #   # ## # # # # ### ### # # ####### ##### ### # ## # #   # #       # # #       #   # #   # ## # ##### # ####### # ######### ### # ### ## #       #         #               # #   G###########################################",
}
start = [0, 1]
goal = [42, 33]

Préparation

Définissez «file d'attente» et «visité» utilisés pour la recherche, et «coûts» utilisés pour guider l'itinéraire le plus court.

Le labyrinthe est sorti sous la forme d'un tableau bidimensionnel, mais tout le traitement des données est effectué avec un tableau unidimensionnel, il est donc nécessaire d'effectuer une conversion appropriée.


visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]

#La position de départ(0, 1)Faire la queue
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0

Recherche processus principal

Puisqu'il s'agit d'une recherche de priorité de largeur, nous la retirerons de la tête de la file d'attente et la vérifierons. Si l'état haut, bas, gauche et droite est un passage, il sera de plus en plus ajouté à la file d'attente. La mise à jour des coûts peut être utilisée pour dériver l'itinéraire le plus court en ajoutant toujours +1 au coût du point de référence.

    while len(queue) > 0:
        #Obtenir la position de la file d'attente
        p, queue = queue[0], queue[1:]
        visited[p[1] * maze["width"] + p[0]] = True

        #Vérifiez en haut, en bas, à gauche et à droite
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = p[0] + i[0], p[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue

            if at(x, y, maze) == " " and visited[y * maze["width"] + x] == False:
                queue.append([x, y])
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
            if at(x, y, maze) == "G":
                queue = []
                costs[y * maze["width"] + x] = costs[p[1] * maze["width"] + p[0]] + 1
                break

Dérivation de l'itinéraire le plus court

Puisque le «coût» est le même que la distance prise depuis le départ, l'itinéraire le plus court peut être dérivé en retournant à 0 à partir du coût de la position cible.

    #Suivez les coûts de l'objectif pour trouver l'itinéraire le plus court
    point = goal
    cost = costs[point[1] * maze["width"] + point[0]]
    while cost != 1:
        for i in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            x, y = point[0] + i[0], point[1] + i[1]
            if x < 0 or y < 0 or x > maze["width"] - 1 or y > maze["height"] - 1:
                continue
            if costs[y * maze["width"] + x] == cost - 1:
                cost = costs[y * maze["width"] + x]
                point = [x, y]
                setChar(x, y, ".", maze)
                break

    printMaze(maze)

résultat

image.png

en conclusion

Je ferai de mon mieux demain! !! Tomowarkar Alone Advent Calendar Advent Calendar 2019

référence

https://qiita.com/nati-ueno/items/a789095aff0aec10d5d0 https://vigne-cla.com/18-2/

Recommended Posts

Mettre en œuvre la recherche de chemin le plus court pour le labyrinthe
OSMnx pour la première fois ~ Avec la recherche d'itinéraire la plus courte ~
Rechercher des fichiers avec l'extension spécifiée
Rechercher le labyrinthe avec l'algorithme python A *
[Renforcer l'apprentissage] Rechercher le meilleur itinéraire
Python> sys.path> Liste de chaînes indiquant le chemin pour rechercher des modules
Mettre en œuvre REPL
[Introduction à l'algorithme] Trouvez l'itinéraire le plus court [Python3]
Trouvez l'itinéraire le plus court avec l'algorithme de Python Dijkstra
Calcul de l'itinéraire le plus court selon la méthode de Monte Carlo
Résolution du problème d'itinéraire de transport (VRP) Planification d'entiers mixtes
[Boto3] Rechercher des utilisateurs Cognito avec l'API List Users
Rechercher des fichiers volumineux sous Linux à partir de la ligne de commande
Essayez une recherche similaire de recherche d'images à l'aide du SDK Python [Recherche]
Recherchez le pandas.DataFrame avec une variable et obtenez la ligne correspondante.
[Comprendre au plus court] Principes de base de Python pour l'analyse des données
Google recherche la chaîne sur la dernière ligne du fichier en Python