[PYTHON] Implementieren Sie die Suche nach dem kürzesten Pfad für das Labyrinth
Dieser Artikel ist der Artikel zum 20. Tag von tomowarkar Alone Adventskalender 2019.
Einführung
Die Suche nach Breitenprioritäten und die Suche nach Tiefenprioritäten scheinen schwierig zu sein, daher habe ich sie bisher noch nicht angesprochen, aber ich war irgendwie motiviert, also habe ich die kürzeste Routensuche für das Labyrinth geschrieben.
Der Inhalt selbst erscheint häufig, und ich habe nichts Ungewöhnliches getan. Ich werde es als Memorandum und Ausgabe schreiben.
Ergebnisse
Code
def printMaze(maze):
"""Zeichne ein Labyrinth"""
for i in range(maze["height"]):
row = maze["data"][i * maze["width"] : (i + 1) * maze["width"]]
print(" ".join(row))
def at(x, y, maze):
"""Vom Labyrinth(x, y)Gibt ein Koordinatenobjekt zurück"""
return maze["data"][y * maze["width"] + x]
def setChar(x, y, char, maze):
"""Vom Labyrinth(x, y)Stellen Sie das Koordinatenobjekt ein"""
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"]
#Startposition(0, 1)
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
while len(queue) > 0:
#
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#
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
#
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)
Extrahieren Sie die Position aus der Warteschlange. Überprüfen Sie nach oben, unten, links und rechts. Verfolgen Sie die Kosten des Ziels, um den kürzesten Weg zu finden. Erläuterung Definieren Sie die Labyrinthinformationen in einem Wörterbuchtyp. "#" "Ist die Wand" "" ist die Passage, "S", "G" ist der Start bzw. das Ziel. Gleichzeitig werden die (x, y) -Koordinaten von Start und Ziel auch manuell eingegeben.
maze = {
"width": 43,
"height": 35,
"data": "###########################################S # # # ## ### ########### # ################# ### ## # # # # # # # #### ########### # # ##### ##### ### ### # ## # # # # # # # # # # ## ####### ### # ####### ### ### # ##### # ## # # # # # ###### ### ##### ### ##### ### ##### ##### ## # # # # # # # # # # # ## # # # # ### # # ### ### # ### ### # ### ## # # # # # # # # # # # # # # # # ## # # # ##### # ####### ### # ### # # # # ## # # # # # # # # # # # ## # # # ##### ### ### ####### ### ### # # ## # # # # # # # # # # # ## # # ##### ### ### ########### ### ### # ## # # # # # # # # # ## # ##### ### # ### ### ##### # # # ### # ## # # # # # # # # # # # # # ## ##### ### # ### ##### ### ### # ### # # ## # # # # # # # #### # # ### ### ######### ### ### ### ### ## # # # # # # # # # # ## ### ### ### ##### # ### ### ####### ### ## # # # # # # # # ## ### ####### ### ### # ##### ### ### # #### # # # # # # # # # # ## # # # ### ### # ##### ##### ##### # ### ## # # # # # # # # # # # ## # # # # ### ### # # ####### ##### ### # ## # # # # # # # # # # # ## # ##### # ####### # ######### ### # ### ## # # # # # G###########################################",
}
start = [0, 1]
goal = [42, 33]
Vorbereitung
Definieren Sie "Warteschlange" und "besucht" für die Suche und "Kosten" für die kürzeste Route.
Das Labyrinth wird als zweidimensionales Array ausgegeben, aber die gesamte Datenverarbeitung wird mit einem eindimensionalen Array ausgeführt, sodass eine entsprechende Konvertierung durchgeführt werden muss.
visited = [False] * maze["width"] * maze["height"]
costs = [999999] * maze["width"] * maze["height"]
#Startposition(0, 1)Schlange
queue = [start]
costs[start[1] * maze["width"] + start[0]] = 0
Suche Hauptprozess
Da es sich um eine Suche mit Breitenpriorität handelt, nehmen wir sie aus dem Kopf der Warteschlange heraus und überprüfen sie. Wenn der Zustand von oben, unten, links und rechts eine Passage ist, wird er immer mehr zur Warteschlange hinzugefügt. Die Kostenaktualisierung kann verwendet werden, um die kürzeste Route abzuleiten, indem immer +1 zu den Kosten des Referenzpunkts addiert werden.
while len(queue) > 0:
#Position aus der Warteschlange abrufen
p, queue = queue[0], queue[1:]
visited[p[1] * maze["width"] + p[0]] = True
#Überprüfen Sie oben, unten, links und rechts
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
Kürzeste Routenableitung
Da "Kosten" der Entfernung vom Start entspricht, kann die kürzeste Route abgeleitet werden, indem von den Kosten der Zielposition auf 0 zurückgegriffen wird.
#Folgen Sie den Kosten vom Ziel, um den kürzesten Weg zu finden
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)
Ergebnis
abschließend
Ich werde morgen mein Bestes geben! !! Tomowarkar Allein Adventskalender Adventskalender 2019
Referenz
https://qiita.com/nati-ueno/items/a789095aff0aec10d5d0 https://vigne-cla.com/18-2/
Recommended Posts