[Python] Suche nach Tiefenpriorität und Suche nach Breitenpriorität

Ich fand (irgendwie) den Unterschied zwischen den beiden, den ich beim Studium des Algorithmus nicht verstand, und beschloss, ihn zu erklären. Dieses Mal werden wir Methoden verwenden, die Datenstrukturen verwenden, die als Stapel bzw. Warteschlangen bezeichnet werden. Wiederholungen werden nicht behandelt.

Was ist Tiefenprioritätssuche?

Die Suche mit Tiefenpriorität (Fukasa Yusentansaku, Englisch: Tiefensuche, DFS, auch als Backtrack-Methode bekannt) ist ein Algorithmus zum Suchen von Bäumen und Grafiken. Der Algorithmus beginnt an der Wurzel (im Fall eines Diagramms bestimmt er, welcher Knoten gewurzelt werden soll) und sucht so viel wie möglich, bis er zurückverfolgt wird. Wird auch als "vertikale Suche" bezeichnet. [Aus Wikipedia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7% B4% A2)

Bild Wir werden die Suche aus dem tiefen Teil des Labyrinths priorisieren, und wenn wir eine Sackgasse erreichen, werden wir zurückkehren und versuchen, an einen Ort zu gehen, den wir noch nicht besucht haben.

Was ist die Suche nach Breitenpriorität?

Die Suche nach Breitenpriorität (Habayu Sentansaku, Englisch: Breitensuche) ist ein Algorithmus zur Suche nach Baumstrukturen und Graphen in der Graphentheorie. Der Algorithmus beginnt mit dem Wurzelknoten und sucht nach allen benachbarten Knoten. Dann wird dasselbe für jeden dieser nächsten Knoten wiederholt, um den zu durchsuchenden Knoten zu finden. Auch als "horizontale Suche" bekannt. Die Suche nach Breitenprioritäten erweitert und überprüft alle Knoten im Diagramm umfassend, um eine Lösung zu finden. Im Gegensatz zur Suche mit der besten Priorität verwendet er keine Heristik für die Knotensuche und durchsucht das gesamte Diagramm, ohne zu berücksichtigen, ob es sich in der Nähe des Zielknotens befindet, bis der Zielknoten gefunden wird. Aus Wikipedia

Bild Nachdem Sie alles neben Ihrem Standort erkundet haben, fahren Sie mit dem nächsten fort. Sie priorisieren die Breite vor der Tiefe.

DFS (Tiefenprioritätssuche) mit Stapelstruktur

Was ist Stapel

Last in first out LIFO (Last In First Out) Das Bild, Bücher zu stapeln und von oben zu ordnen. (Das Buch, das später platziert wurde, wird zuerst herausgenommen.)

Aus dem Beispiel ATC001 A Problemstellung Die Stadt, in der Takahashi lebt, hat eine rechteckige Form und ist in gitterartige Abschnitte unterteilt. Jede Seite des Rechtecks verläuft parallel zu Ost-West und Nord-Süd. Jeder Abschnitt ist entweder eine Straße oder eine Mauer, und Takahashi kann die Straße nach Norden, Süden, Osten und Westen bewegen, jedoch nicht diagonal. Auch der Zaunabschnitt kann nicht passiert werden. Stellen Sie fest, ob Takahashi den Fischladen über die Straße erreichen kann, ohne den Zaun zu durchbrechen.

#===Standardeingabe und Organisation der verwendeten Daten===#
h, w = map(int, input().split())
sx, sy, gx, gy = None, None, None, None
town = []
edge = ['#'] * (w+2) #Umgeben Sie die Ober- und Unterseite mit einer Wand
for i in range(h):
    line = list(input())
    line = ['#'] + line + ['#'] #Umgeben Sie links und rechts mit einer Wand
    for j in range(w+2):
        if line[j] == 's':
            sx, sy = j, i+1 #Koordinaten starten
    for j in range(w+2):
        if line[j] == 'g':
            gx, gy = j, i+1 #Zielkoordinaten
    town.append(line)
town = [edge] + town + [edge] #Karte der Stadt in dieser Angelegenheit
visited = [[False]*(w+2) for _ in range(h+2)] #Notieren Sie, wo Sie in der Stadt waren

#===Die Suche nach Tiefenpriorität wurde gestartet===#
stack = [[sx, sy]] #Legen Sie die Koordinaten des Startpunkts in den Stapel
visited[sy][sx] = True #Der Startpunkt"hat besucht"Zu
while stack: #Während sich Inhalt im Stapel befindet
    x, y = stack.pop()
    if town[y][x] == 'g':
        print('Yes')
        exit() #Wenn Ihr aktueller Standort das Ziel ist'Yes'Wird ausgegeben, um die Ausführung zu beenden
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Nächster zu besuchender Ort: oben links, unten rechts
    for dx, dy in hjkl:
        if (dx<1) or (dx>w+1) or (dy<1) or (dy>h+1) or town[dy][dx] == '#' or visited[dy][dx] is True:
            #Überspringen Sie, wenn die Fahrtrichtung eine Mauer außerhalb des Stadtbereichs ist oder wenn Sie bereits besucht haben
            continue
        #Wenn nicht, legen Sie die Fahrtrichtung auf einen neuen Stapel und markieren Sie ihn als besucht.
        stack.append([dx, dy])
        visited[dy][dx] = True

print('No') #Wenn Sie nicht erreichen können'No'Ausgabe

BFS (Breitenprioritätssuche) unter Verwendung der Warteschlangenstruktur

Was ist Warteschlange?

First In First Out FIFO (First In First Out) Das Bild, das Personen an der Registrierkasse aufgereiht haben, wird von der Person verarbeitet, die zuerst aufgereiht ist (first in, first out).

Aus dem Beispiel ABC007 C Problemstellung Takahashi mag Labyrinthe. Ich versuche ein Labyrinth auf einem zweidimensionalen Brett zu lösen, das sich nach oben, unten, links und rechts bewegen kann. Zunächst werden die Größe des Bretts und die Koordinaten der Start- und Endpunkte des Labyrinths angegeben. Als nächstes wird eine Tafel mit Informationen darüber gegeben, ob jede Zelle eine passierbare leere Zelle (.) Oder eine unpassierbare Wandzelle (#) ist. Das Brett ist von Wandquadraten umgeben. Der Startpunkt und der Zielpunkt sind immer leere Quadrate, und Sie können den Zielpunkt immer erreichen, indem Sie den leeren Quadraten vom Startpunkt bis zum Zielpunkt folgen. Insbesondere ist es ratsam, sich auf ein Eingabe- / Ausgabebeispiel zu beziehen. Jetzt möchte er die Mindestanzahl von Zügen finden, die erforderlich sind, um das obige Labyrinth zu lösen. Als ich nachforschte, wie ich es finden konnte, stellte ich fest, dass eine Methode namens "Suche nach Breitenpriorität" effizient war. (Teilweise weggelassen)

#===Standardeingabe und Organisation der verwendeten Daten===#
r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = [i-1 for i in [sx, sy, gx, gy]] #Korrigieren Sie die zu indizierenden Koordinaten
maiz = []
for _ in range(r):
    line = list(input())
    maiz.append(line)

#===Die Suche nach der Breitenpriorität wurde gestartet===#
queue = [[sx, sy]] #Den Startpunkt in die Warteschlange stellen
maiz[sy][sx] = 0 #Beginnen Sie mit 0 Schritten
visited = [[False]*c for _ in range(r)] #Notieren Sie sich, ob Sie besucht haben
while queue:
    x, y = queue.pop(0)
    visited[y][x] = True #Machen Sie es besucht
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Nächster zu besuchender Ort: oben links, unten rechts
    for dx, dy in hjkl:
        if (maiz[dy][dx] == '.') and (visited[dy][dx] is False):
            #Wenn Sie fortfahren können und noch nicht besucht haben, stellen Sie den Aufwand in die Warteschlange und zeichnen Sie ihn auf
            queue.append([dx, dy])
            maiz[dy][dx] = maiz[y][x]+1

print(maiz[gy][gx]) #Beziehen Sie sich auf die Anzahl der am Zielpunkt aufgezeichneten Schritte

Frage: Über die Reihenfolge der Fahrtrichtung diagonale Richtung

Reihenfolge der Fahrtrichtung

Es gibt insgesamt 24 verschiedene Bestellungen in 4 Richtungen, aber die Reihenfolge der Reiserichtungen ist wahrscheinlich alles. (Bitte lassen Sie mich wissen, wenn es ein Muster gibt, das nicht funktioniert, wenn Sie in dieser Reihenfolge fortfahren.)

Diagonale Richtung

Ich werde fortfahren. Abhängig vom Problem gibt es eine Bedingung, dass Sie diagonal vorgehen können. Seien Sie also flexibel. AOJ 1160 Wie viele Inseln gibt es?