def neighbor(town, dist_mat=dist_mat, threshold=1): #Funktion zum Abrufen der Adjazenzliste 1
    return [x[0] for x in enumerate(np.where(dist_mat[town] <= threshold, True, False)) if x[1]]

Das Anwendungsbeispiel sieht folgendermaßen aus.

neighbor(12) #Welche Städte sind 1 Entfernung von Tokio entfernt?

[7, 8, 9, 10, 11, 12, 13]

Grafiksuchfunktion 1

In Grundlagen der Graphentheorie wurde die while-Anweisung verwendet, um das Graphsuchproblem zu lösen, aber hier möchte ich den Fortschritt Schritt für Schritt zeigen. Ich habe die Funktion definiert, um einen Schritt der Suche wie folgt voranzutreiben.

def traverse(i=0): #Ein Schritt der Tiefenprioritätssuche
    if len(stack) != 0: #Wenn der Stapel nicht leer ist
        next_town, current_town = stack.pop() #Holen Sie sich die nächste Route (aktueller Standort und nächste Stadt)
        current_direction = [[next_town, current_town]] #Zum Zeichnen
        if next_town not in visited_towns: #Wenn die nächste Stadt nicht besucht wurde
            used_routes.append([next_town, current_town]) #Registrieren Sie die Route
            visited_towns.append(next_town) #Machen Sie es besucht
            for nei in neighbor(next_town): #Nehmen Sie die Städte neben der besuchten Stadt nacheinander heraus
                if nei not in visited_towns: #Wenn Sie nicht besucht haben
                    stack.append([nei, next_town]) #Legen Sie die Route auf den Stapel
    return current_direction #Zum Zeichnen

Suchanimation für Tiefenpriorität 1

Jetzt animieren wir es.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Der Ausgangspunkt ist Tokio
visited_towns = [] #Anordnung zur Aufbewahrung der besuchten Städte
used_routes = [] #Ein Array, in dem die tatsächlich verwendeten Routen gespeichert werden
current_direction = [] #Route wird gerade überprüft
ims = [] #Anordnung zum Speichern von Standbildern
i = 0
while len(stack) > 0: #Wenn der Stapel nicht leer ist
    if i != 0: #Da der Anfangswert zum ersten Mal angezeigt wird, kann die Suche nicht fortgesetzt werden.
        current_direction = traverse() #Machen Sie die Suche einen Schritt
    image = [] #Ein Array, in dem zu schreibende Teile in einem Standbild gespeichert werden
    for edge in get_edges(stack): #Die rote Linie ist die "Kandidaten" -Route im Stapel
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #Die blaue Linie ist die Route, die gerade überprüft wird
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Schwarze Linie wird Route verwendet
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Stadtnamen anzeigen

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru ist die Stadt, die gerade überprüft wird
    ims.append(image) #Speichern Sie ein Standbild
    i += 1

#In Video konvertieren
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation2.gif", writer='pillow') #Als GIF-Datei speichern
HTML(ani.to_jshtml()) #Anzeige in HTML

Suchanimation für Tiefenpriorität 1

• Wenn die Animation endet und stoppt, können Sie sie erneut verschieben, indem Sie auf das Bild klicken.

Funktion zum Abrufen der Adjazenzliste 2

Bei der obigen Suche nach Tiefenpriorität ist die "letzte Stadt auf dem Stapel" der nächste Zielkandidat. Wenn Sie in eine Stadt ziehen, befinden sich die Nachbarstädte im Stapel. Zu diesem Zeitpunkt ändert sich das Verhalten auch bei gleicher Suche nach Tiefenpriorität, indem die Reihenfolge berücksichtigt wird, in der sie in den Stapel gelegt werden. Ändern wir es so, dass Städte, die nahe beieinander liegen, bevorzugt als Zielkandidaten ausgewählt werden.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Funktion zum Abrufen der Adjazenzliste 2
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()][::-1]

Suche nach Tiefenprioritätssuche 2

Der folgende Code entspricht dem vorherigen "Tiefenprioritätssuchanimation 1" (nur der Dateiname des gespeicherten Videos ist unterschiedlich). Mal sehen, wie das Ändern der Funktion "Nachbar" ihr Verhalten ändert.

# -*- coding: UTF-8 -*-
# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Der Ausgangspunkt ist Tokio
visited_towns = [] #Anordnung zur Aufbewahrung der besuchten Städte
used_routes = [] #Ein Array, in dem die tatsächlich verwendeten Routen gespeichert werden
current_direction = [] #Route wird gerade überprüft
ims = [] #Anordnung zum Speichern von Standbildern
i = 0
while len(stack) > 0: #Wenn der Stapel nicht leer ist
    if i != 0: #Da der Anfangswert zum ersten Mal angezeigt wird, kann die Suche nicht fortgesetzt werden.
        if stack[0] != []: #Die Suche wird auch bei der letzten Anzeige nicht fortgesetzt
            current_direction = traverse() #Machen Sie die Suche einen Schritt
    image = [] #Ein Array, in dem zu schreibende Teile in einem Standbild gespeichert werden
    for edge in get_edges(stack): #Die rote Linie ist die "Kandidaten" -Route im Stapel
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #Die blaue Linie ist die Route, die gerade überprüft wird
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Schwarze Linie wird Route verwendet
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Stadtnamen anzeigen

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru ist die Stadt, die gerade überprüft wird
    ims.append(image) #Speichern Sie ein Standbild
    
    if len(stack) == 0: #Für die letzte Anzeige
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Für die letzte Flucht
        break
    i += 1

#In Video konvertieren
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation3.gif", writer='pillow') #Als GIF-Datei speichern
HTML(ani.to_jshtml()) #Anzeige in HTML

Suche nach Tiefenprioritätssuche 2

• Wenn die Animation endet und stoppt, können Sie sie erneut verschieben, indem Sie auf das Bild klicken.

Suche nach Breitenpriorität

Als nächstes führen wir eine Suche nach Breitenpriorität durch. Der grundlegende Algorithmus ist fast der gleiche. Stellen Sie den Stapel (first in, last out) einfach in eine Warteschlange (queue: first in, first out).

Grafiksuchfunktion 2

Schreiben Sie die Funktion "Traverse" neu. Der neu zu schreibende Teil ist nur ein Punkt, der als "Änderung" angezeigt wird. Da sich die als Stapel verwendete Liste in eine Warteschlange ändert, möchte ich den Variablennamen "Stapel" ändern, aber dadurch wird der neu zu schreibende Teil vergrößert. Lassen wir also "Stapel" so wie er ist.

def traverse(i=0): #1 Schritt der Suche nach Breitenpriorität
    if len(stack) != 0:
        next_town, current_town = stack.pop(0) #Wechselpunkt
        current_direction = [[next_town, current_town]]
        if next_town not in visited_towns:
            used_routes.append([next_town, current_town])
            visited_towns.append(next_town)
            for nei in neighbor(next_town):
                if nei not in visited_towns:
                    stack.append([nei, next_town])
    return current_direction

Funktion zum Abrufen der Adjazenzliste 3

Die Funktion zum Abrufen der Adjazenzliste wurde ebenfalls neu geschrieben, ist jedoch im Grunde dieselbe wie die vorherige. Der Stapel befindet sich in der Warteschlange, sodass Sie die Reihenfolge einfach umdrehen.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Funktion zum Abrufen der Adjazenzliste 3
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()] #Ändere nur das Ende

Suchanimation mit Breitenpriorität

Der folgende Code entspricht auch "Tiefenprioritätssuchanimation 1" und "Tiefenprioritätssuchanimation 2" (nur der Dateiname des gespeicherten Videos ist unterschiedlich). Mal sehen, wie das Ändern der Funktion "Traverse" das Verhalten ändert.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Der Ausgangspunkt ist Tokio
visited_towns = [] #Anordnung zur Aufbewahrung der besuchten Städte
used_routes = [] #Ein Array, in dem die tatsächlich verwendeten Routen gespeichert werden
current_direction = [] #Route wird gerade überprüft
ims = [] #Anordnung zum Speichern von Standbildern
i = 0
while len(stack) > 0: #Wenn der Stapel nicht leer ist
    if i != 0: #Da der Anfangswert zum ersten Mal angezeigt wird, kann die Suche nicht fortgesetzt werden.
        if stack[0] != []: #Die Suche wird auch bei der letzten Anzeige nicht fortgesetzt
            current_direction = traverse() #Machen Sie die Suche einen Schritt
    image = [] #Ein Array, in dem zu schreibende Teile in einem Standbild gespeichert werden
    for edge in get_edges(stack): #Die rote Linie ist die "Kandidaten" -Route im Stapel
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #Die blaue Linie ist die Route, die gerade überprüft wird
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Schwarze Linie wird Route verwendet
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Stadtnamen anzeigen

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru ist die Stadt, die gerade überprüft wird
    ims.append(image) #Speichern Sie ein Standbild
    
    if len(stack) == 0: #Für die letzte Anzeige
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Für die letzte Flucht
        break
    i += 1

#In Video konvertieren
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation4.gif", writer='pillow') #Als GIF-Datei speichern
HTML(ani.to_jshtml()) #Anzeige in HTML

Suchanimation mit Breitenpriorität

• Wenn die Animation endet und stoppt, können Sie sie erneut verschieben, indem Sie auf das Bild klicken.

Suche mit bester Priorität und minimaler Baum

Schließlich die Suche mit der besten Priorität. In den beiden obersten Suchanfragen haben wir Städte mit kurzer Entfernung hinzugefügt, die beim Hinzufügen zum Stapel (oder zur Warteschlange) bevorzugt abgerufen werden sollen. Bei der Suche mit der besten Priorität wird der gesamte Stapel (tatsächlich eine Warteschlange) nach dem Hinzufügen sortiert, sodass die Städte mit der kürzesten Entfernung bevorzugt daraus extrahiert werden. Das Ergebnis ist ein "Mindestbaum".

Funktion zum Neuanordnen des Stapels

Die einzige Änderung gegenüber der Vergangenheit besteht darin, den gesamten Stapel neu zu sortieren.

def sort_stack(stack):
    return [stack[i] for i in np.argsort([dist_mat[edge[0]][edge[1]] for edge in stack])]

Suchanimation mit der besten Priorität

Der folgende Code ist im Grunde der gleiche wie zuvor. Die einzigen Änderungen sind das Hinzufügen der Funktion "sort_stack" und das Umbenennen der Datei, in der das Video gespeichert wird.

# -*- coding: UTF-8 -*-
import math
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML

fig = plt.figure(figsize=(10, 8))

stack = [[12, 12]] #Der Ausgangspunkt ist Tokio
visited_towns = [] #Anordnung zur Aufbewahrung der besuchten Städte
used_routes = [] #Ein Array, in dem die tatsächlich verwendeten Routen gespeichert werden
current_direction = [] #Route wird gerade überprüft
ims = [] #Anordnung zum Speichern von Standbildern
i = 0
while len(stack) > 0: #Wenn der Stapel nicht leer ist
    if i != 0: #Da der Anfangswert zum ersten Mal angezeigt wird, kann die Suche nicht fortgesetzt werden.
        if stack[0] != []: #Die Suche wird auch bei der letzten Anzeige nicht fortgesetzt
            stack = sort_stack(stack) #Stapel für die Suche mit der besten Priorität sortieren
            current_direction = traverse() #Machen Sie die Suche einen Schritt
    image = [] #Ein Array, in dem zu schreibende Teile in einem Standbild gespeichert werden
    for edge in get_edges(stack): #Die rote Linie ist die "Kandidaten" -Route im Stapel
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #Die blaue Linie ist die Route, die gerade überprüft wird
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #Schwarze Linie wird Route verwendet
        image += plt.plot(edge[0], edge[1], 'k', lw=2)

    for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
        image.append(plt.text(x, y, city, alpha=0.5, size=12)) #Stadtnamen anzeigen

    if len(current_direction) > 0:
        current_town = current_direction[0][0]
        image += plt.plot(japan.iloc[current_town, :]['Latitude'], 
                          japan.iloc[current_town, :]['Longitude'], 
                          markersize=20, marker='o') #Maru ist die Stadt, die gerade überprüft wird
    ims.append(image) #Speichern Sie ein Standbild
    
    if len(stack) == 0: #Für die letzte Anzeige
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Für die letzte Flucht
        break
    i += 1

#In Video konvertieren
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation5.gif", writer='pillow') #Als GIF-Datei speichern
HTML(ani.to_jshtml()) #Anzeige in HTML

Suchanimation mit der besten Priorität

• Wenn die Animation endet und stoppt, können Sie sie erneut verschieben, indem Sie auf das Bild klicken.