def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 1
    return [x[0] for x in enumerate(np.where(dist_mat[town] <= threshold, True, False)) if x[1]]

L'exemple d'utilisation ressemble à ceci.

neighbor(12) #Quelles villes sont à moins de 1 distance de Tokyo?

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

Fonction de recherche graphique 1

Dans Bases de la théorie des graphes, l'instruction while a été utilisée pour résoudre le problème de recherche de graphes, mais ici, je veux montrer la progression étape par étape. J'ai défini la fonction pour avancer d'une étape de la recherche comme suit.

def traverse(i=0): #Une étape de recherche de priorité en profondeur
    if len(stack) != 0: #Si la pile n'est pas vide
        next_town, current_town = stack.pop() #Obtenir l'itinéraire suivant (emplacement actuel et ville suivante)
        current_direction = [[next_town, current_town]] #Pour dessiner
        if next_town not in visited_towns: #Si la ville suivante n'a pas été visitée
            used_routes.append([next_town, current_town]) #Enregistrer l'itinéraire
            visited_towns.append(next_town) #Faites-le visiter
            for nei in neighbor(next_town): #Sortez les villes adjacentes à la ville visitée une par une
                if nei not in visited_towns: #Si vous n'avez pas visité
                    stack.append([nei, next_town]) #Mettez l'itinéraire sur la pile
    return current_direction #Pour dessiner

Animation de recherche de priorité de profondeur 1

Maintenant animons-le.

# -*- 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]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        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)) #Afficher le nom de la ville

    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 est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation2.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de profondeur 1

• Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Fonction pour obtenir la liste de contiguïté 2

Dans la recherche de priorité de profondeur ci-dessus, la «dernière ville de la pile» est la prochaine destination candidate. Lorsque vous vous déplacez dans une ville, les villes voisines sont dans la pile. À ce stade, le comportement change même avec la même recherche de priorité de profondeur en tenant compte de l'ordre de leur mise dans la pile. Modifions-le pour que les villes proches les unes des autres soient préférentiellement sélectionnées comme destinations candidates.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 2
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()][::-1]

Animation de recherche de priorité de profondeur 2

Le code ci-dessous est le même que celui de la précédente "Animation de recherche de priorité à la profondeur 1" (seul le nom de fichier de la vidéo enregistrée est différent). Voyons comment changer la fonction voisin change son comportement.

# -*- 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]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        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)) #Afficher le nom de la ville

    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 est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation3.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de profondeur 2

• Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Recherche de priorité de largeur

Ensuite, faisons une recherche de priorité de largeur. L'algorithme de base est presque le même, il suffit de mettre la pile (premier entré, dernier sorti) dans une file d'attente (file d'attente: premier entré, premier sorti).

Fonction de recherche graphique 2

Réécrivez la fonction «traversée». La partie à réécrire n'est qu'un seul point indiqué comme "changement". Étant donné que la liste utilisée comme pile change en file d'attente, je voudrais changer le nom de la variable stack, mais cela augmentera la partie à réécrire, alors laissons pile telle quelle.

def traverse(i=0): #1 étape de recherche de priorité de largeur
    if len(stack) != 0:
        next_town, current_town = stack.pop(0) #point de changement
        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

Fonction pour obtenir la liste de contiguïté 3

La fonction pour obtenir la liste de contiguïté est également réécrite, mais elle est fondamentalement la même que la précédente. La pile est mise en file d'attente, il vous suffit donc de retourner la commande.

import numpy as np
def neighbor(town, dist_mat=dist_mat, threshold=1): #Fonction pour obtenir la liste de contiguïté 3
    return np.argsort(dist_mat[town])[1:np.where(dist_mat[town] <= threshold, 1, 0).sum()] #Changer seulement la fin

Animation de recherche de priorité de largeur

Le code suivant est également le même que «Animation de recherche de priorité de profondeur 1» et «Animation de recherche de priorité de profondeur 2» (seul le nom de fichier de la vidéo enregistrée est différent). Voyons comment changer la fonction «traverse» change le comportement.

# -*- 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]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        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)) #Afficher le nom de la ville

    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 est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation4.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Animation de recherche de priorité de largeur

• Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.

Recherche de la meilleure priorité et arborescence minimale

Enfin, la meilleure recherche prioritaire. Dans les deux premières recherches, nous avons ajouté une priorité pour les villes à courte distance lors de leur ajout à la pile (ou à la file d'attente). La recherche de la meilleure priorité trie la pile entière (en fait une file d'attente) après son ajout afin que les villes avec la distance la plus courte en soient de préférence extraites. Le résultat est un "arbre minimum".

Fonction pour réorganiser la pile

Le seul changement par rapport au passé est de trier à nouveau la pile entière.

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

Meilleure animation de recherche de priorité

Le code ci-dessous est fondamentalement le même qu'avant. Les seuls changements sont l'ajout de la fonction sort_stack et le changement de nom du fichier qui enregistre la vidéo.

# -*- 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]] #Le point de départ est Tokyo
visited_towns = [] #Arrangement pour stocker les villes visitées
used_routes = [] #Un tableau qui stocke les routes réellement utilisées
current_direction = [] #Route en cours de vérification
ims = [] #Disposition pour stocker des images fixes
i = 0
while len(stack) > 0: #Si la pile n'est pas vide
    if i != 0: #La valeur initiale étant affichée la première fois, la recherche ne peut pas continuer.
        if stack[0] != []: #La recherche ne se poursuit pas même au dernier affichage
            stack = sort_stack(stack) #Trier les piles pour une recherche de la meilleure priorité
            current_direction = traverse() #Faites une étape de recherche
    image = [] #Un tableau qui stocke les parties à écrire dans une image fixe
    for edge in get_edges(stack): #La ligne rouge est la route «candidate» dans la pile
        image += plt.plot(edge[0], edge[1], 'r', alpha=0.5)

    for edge in get_edges(current_direction): #La ligne bleue est l'itinéraire en cours de vérification
        image += plt.plot(edge[0], edge[1], 'b', lw=5, alpha=0.5)

    for edge in get_edges(used_routes): #La ligne noire est un itinéraire utilisé
        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)) #Afficher le nom de la ville

    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 est la ville en cours de vérification
    ims.append(image) #Stocker une image fixe
    
    if len(stack) == 0: #Pour le dernier affichage
        current_direction = []
        stack.append([])
    elif stack[0] == []: #Pour la dernière évasion
        break
    i += 1

#Convertir en vidéo
ani = animation.ArtistAnimation(fig, ims, interval=500, repeat_delay=1000)

ani.save("Animation5.gif", writer='pillow') #Enregistrer en tant que fichier gif
HTML(ani.to_jshtml()) #Afficher sur HTML

Meilleure animation de recherche de priorité

• Si l'animation se termine et s'arrête, vous pouvez la déplacer à nouveau en cliquant sur l'image.