Comment tracer le chemin d'une Largeur de Recherche?

Comment tracer le chemin d'une Largeur de Recherche, tel que dans l'exemple suivant:

Si vous recherchez la clé 11, de retour de la plus court liste de connecter de 1 à 11.

[1, 4, 7, 11]

C'était en fait un vieux de la tâche qui m'a été d'aider un ami sur mois, basée sur l'Kevin Bacon Loi. Ma solution finale a été très bâclée, en gros, j'ai fait un autre en Largeur d'abord de la recherche pour "revenir en arrière" et revenir en arrière. Je wan pas à trouver une meilleure solution.
Excellent. - Je envisager de revoir un vieux problème dans une tentative de trouver une meilleure réponse à une admirable trait à un ingénieur. Je vous souhaite bonne chance dans vos études et de carrière.
Merci pour les éloges, je crois si je n'ai pas l'apprendre maintenant, je vais être aux prises avec le même problème à nouveau.
double possible de Comment obtenir le chemin d'accès entre 2 nœuds à l'aide de Largeur tout d'Abord de Recherche?

InformationsquelleAutor Christopher Markieta | 2012-01-19

157

Vous devriez avoir regarder http://en.wikipedia.org/wiki/Breadth-first_search premier.

Ci-dessous est une mise en œuvre rapide, dans lequel j'ai utilisé une liste de liste de représenter la file d'attente de chemins.
```
# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')
```
Une autre approche serait de maintenir une cartographie à partir de chaque nœud à son parent, et lors de l'inspection du nœud adjacent, enregistrement de son parent. Lorsque la recherche est terminé, il suffit de backtrace selon le parent cartographie.
```
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')
```
Les codes ci-dessus sont basées sur l'hypothèse qu'il n'y a pas de cycles.
- C'est excellent! Mon processus de pensée me poussent à croire en la création d'un certain type de tableau ou d'une matrice, j'ai encore à apprendre sur les graphes. Je vous remercie.
- J'ai aussi essayé en utilisant un retour de traçage approche bien que cela semble beaucoup plus propre. Serait-il possible de faire un graphique si vous ne connaissez que le début et la fin, mais aucun des nœuds entre les deux? Ou même une autre approche en plus des graphiques?
- Je n'ai pas réussi à comprendre votre question 🙁
- Si nous savons que le nœud de départ est "1" et le nœud de fin est "11", mais les autres nœuds sont inconnus jusqu'à ce que nous commençons à la recherche, telles que le graphe est dynamique et continuera de fonctionner même si l'arbre a 100 nœuds. Ex: { '1': [a, b, c], a: [d, e], d: [f, g], c: [a, h, i], h: [11, k] }
- Aussi longtemps que les nœuds adjacents sont déterminés lorsqu'un nœud est atteint, alors l'algorithme ci-dessus fera l'affaire.
- Puisque vous avez utilisé une table de hachage (parent) dans la deuxième méthode. Il est facile de modifier la méthode pour gérer les cycles. En fait, BFS est souvent mise en œuvre à l'aide d'une file d'attente avec une table de hachage(pour indiquer si un nœud est visité).
- Est-il possible d'adapter le premier algorithme de sorte qu'il sera de retour tous chemins de 1 à 11 (en supposant qu'il existe plus d'une)?
- Lorsque vous trouvez un chemin d'accès (node==end), ajoutez le chemin d'accès à une autre liste qui contiendra tous les chemins que vous avez trouvé, alors continue au lieu de return. Si vous utilisez une visité d'empêcher les cycles, n'ajoutez pas votre nœud de fin de la visités jamais (sinon un seul chemin d'accès peut jamais avoir ce nœud de fin).
- est-il un moyen pour imprimer tous les parents d'enfants jusqu'à une profondeur donnée?
- Il est recommandé d'utiliser des collections.deque au lieu d'une liste. liste.pop(0), s'de la complexité est O(n), tandis que deque.popleft() est O(1)
InformationsquelleAutor qiao
20

J'ai aimé qiao première réponse beaucoup!
La seule chose qui manque ici, c'est pour marquer les sommets visité.

Pourquoi nous avons besoin de le faire?

Permet d'imaginer qu'il y a un autre noeud le numéro 13 est connecté à partir de nœud 11. Maintenant, notre objectif est de trouver nœud 13.

Après un peu de la file d'attente va ressembler à ceci:
```
[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]
```
Noter qu'il existe DEUX chemins avec nœud numéro 10 à la fin.

Ce qui signifie que les chemins d'accès du nœud numéro 10 sera vérifié deux fois. Dans ce cas, il n'a pas l'air si mal parce que le numéro de nœud 10 n'ont pas d'enfants.. Mais il pourrait être vraiment mauvais (même ici, nous allons vérifier que le nœud à deux reprises pour aucune raison..)

Nœud numéro 13 n'est pas dans les chemins de sorte que le programme ne sera pas de retour avant d'arriver à la deuxième chemin avec le numéro de nœud 10 à la fin..Et nous allons les enregistrer..

Tous nous manquer, c'est un jeu pour marquer les nœuds visités et de ne pas vérifier de nouveau..

C'est qiao du code après la modification:
```
graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)
```
La sortie du programme seront:
```
[1, 4, 7, 11, 13]
```
Sans unneccecery revérifie..
- Il pourrait être utile d'utiliser collections.deque pour queue sous forme de liste.pop(0) engager O(n) de la mémoire des mouvements. Aussi, pour le bien de la postérité, si vous voulez faire DFS juste mis path = queue.pop() auquel cas la variable queue en fait agit comme un stack.
InformationsquelleAutor Or Kazaz

Je pensais que je voudrais essayer ce code pour le fun:

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

Si vous voulez cycles vous pourriez ajouter ce:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]

+1, vous m'avez rappelé une chose: assume no cycles 🙂
Où voulez-vous ajouter ce bout de code?
après que vous avez construit le next_for_front. Un suivi sur la question, que si le graphe contient des boucles? E. g. si le nœud 1 a une arête reliant à lui-même? Que faire si le graphe possède plusieurs arêtes entre deux nœuds?

InformationsquelleAutor robert king

Très facile code. Vous gardez en ajoutant le chemin à chaque fois que vous découvrez un nœud.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))

Je trouve votre code très lisible, par rapport à d'autres réponses. Merci beaucoup!

InformationsquelleAutor SeasonalShot

J'aime les deux @Qiao première réponse et @Ou de l'ajout. Pour une vue d'un peu moins de traitement, je voudrais ajouter Ou de réponse.

Dans @Ou la réponse de garder une trace de visité nœud est grande. On peut aussi autoriser le programme à quitter plus tôt qu'il ne l'est actuellement. À un certain point dans la boucle de la current_neighbour devra être le end, et une fois que cela arrive le plus court chemin est trouvé et le programme peuvent revenir.

Je voudrais modifier la méthode à suivre, attention à la boucle de

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

La sortie et tout le reste sera le même. Toutefois, le code prendra moins de temps. Ceci est particulièrement utile sur les grands graphes. J'espère que cela aide quelqu'un dans le futur.

InformationsquelleAutor Darie Dorlus

Vous devez vous connecter pour publier un commentaire.