[GO] Denken Sie an Suchvorgänge mit Tiefenpriorität und Breitenpriorität in Python

Hallo: grinsend: Dieses Mal werden wir die Suche nach Tiefenpriorität und die Suche nach Breitenpriorität unter Verwendung eines Labyrinths betrachten. Das diesmal verwendete Labyrinth: arrow_down:

Eingang

Die Eingabe erfolgt in n Zeilen.

• Die erste Zeile ist der Start- und Endpunkt des Labyrinths ――Die zweite Linie ist die vertikale und horizontale Länge des Labyrinths
• Die Zeilen 3 bis n sind Labyrinthinformationen

n-2 ist die vertikale Länge des Labyrinths, und # wird angegeben, wenn kein Leerzeichen vorhanden ist. ex.)

S G
3 5
# B E F G
S A C H #
# D # # #

Ausgabe

Die Ausgabe besteht aus 3 Zeilen. Die erste Linie ist der Abstand zwischen dem Startpunkt und dem Zielpunkt Die zweite Zeile gibt die Anzahl der Suchvorgänge an Die dritte Linie ist die Route vom Startpunkt zum Zielpunkt ex.)

Abstand zwischen Start- und Endpunkt: 5
Anzahl der Suchvorgänge: 10
Route: G.<= F <= H <= C <= A <= S

Tiefenprioritätssuche

Code-Fluss

1. Lesen Sie die Eingabeinformationen
2. Fügen Sie Start zu verschiedenen Listen hinzu
3. Vom Stapel nehmen
4. Zielbeurteilung
5. Fügen Sie dem Stapel benachbarte Punkte hinzu
6. Zur Checkliste hinzufügen und zu 3 zurückkehren

Implementierung

stack

# cording = utf-8
start, goal = input().split()  #Startpunkt und Zielpunkt
height, width = map(int, input().split())  #Labyrinthlänge und -breite
maze, stack, checked, route = [], [], [], {}
num_of_t = 0  #Anzahl der Suchvorgänge
for i in range(height):
    x = input().split()
    maze.append(x) #Matze
    if start in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Speichern Sie die Koordinaten des Startpunkts
stack += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = stack, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while stack[-1] != goal:
    stack.pop()
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    for j in range(height):
        if stack[-1] in maze[j]:
            route[stack[-1]] = maze[now_height][now_width]
            now_height, now_width = j, maze[j].index(stack[-1])
print("Abstand zwischen Start- und Endpunkt:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Anzahl der Suchanfragen:" + str(num_of_t))
print("Wurzel:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Ausgabeergebnis

Abstand zwischen Start- und Endpunkt: 5
Anzahl der Suchvorgänge: 5
Route: G.<= F <= E <= B <= A <= S

Suche nach Breitenpriorität

Code-Fluss

Ändern Sie den Stapel der Suche mit Tiefenpriorität in die Warteschlange

Implementierung

queue

# cording = utf-8
start, goal = input().split() #Geben Sie den Start- und Zielpunkt ein
height, width = map(int, input().split()) #Vertikale und horizontale Länge des Labyrinths
maze, queue, checked, route = [], [], [], {}
num_of_t = 0 #Anzahl der Suchvorgänge
for i in range(height):
    x = input().split()
    maze.append(x)  #Matze
    if "A" in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Speichern Sie die Koordinaten des Startpunkts
queue += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = queue, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while queue[0] != goal:
    place = queue.pop(0)
    tmp = len(queue)
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    if tmp < len(queue):
        for i in range(1, len(queue) - tmp+1):
            route[queue[-i]] = place
    for j in range(height):
        if queue[0] in maze[j]:
            now_height, now_width = j, maze[j].index(queue[0])
print("Abstand zwischen Start- und Endpunkt:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Anzahl der Suchanfragen:" + str(num_of_t))
print("Wurzel:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Ausgabeergebnis

Abstand zwischen Start- und Endpunkt: 5
Anzahl der Suchvorgänge: 8
Route: G.<= F <= H <= C <= A <= S

Erwägung

Das Wissen über den Algorithmus wurde ausreichend vertieft. Einige Leute können es vielleicht kürzer schreiben, aber im Moment bin ich so.