Je veux calculer le chemin le plus court entre 2 nœuds. Chaque nœud a une position comme [1,2]. Lorsque je parcoure les nœuds à l'aide de BFS, je marque chaque nœud comme visité et ajoute la distance par rapport au nœud de départ. Lorsque le nœud de fin est trouvé, je veux appeler une fonction, passer le nœud de début et de fin et obtenir le chemin le plus court

Contribution:

[3,3], [5,6], [all visited] (output included in all visited)

Sortie désirée:

[[3,4], [3,5], [3,6], [4,6]]

Comment filtrer toutes les visites pour obtenir le chemin le plus court ?

2
Zobla 13 sept. 2020 à 19:20

1 réponse

Meilleure réponse

Si je comprends bien, vous demandez comment vous pouvez reconstruire le chemin le plus court à partir d'une recherche en largeur d'abord qui a trouvé une cible.

Il existe plusieurs façons de le faire, mais l'une consiste à transformer votre marquage visité en un marquage avec une référence arrière au nœud d'où vous venez.

Sur Wikipedia vous pouvez trouver un pseudo-code où cette référence arrière est un parent propriété du nœud :

procedure BFS(G, root) is
     let Q be a queue
     label root as discovered
     Q.enqueue(root)
     while Q is not empty do
         v := Q.dequeue()
         if v is the goal then
             return v
         for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered then
                 label w as discovered
                 w.parent := v
                 Q.enqueue(w) 

Bien que vous puissiez conserver un indicateur booléen séparé pour « visité » (ou « découvert »), vous pouvez économiser de l'espace en utilisant simplement cette propriété parent : si elle est non nulle, considérez le nœud comme visité.

Une fois que vous avez trouvé le nœud cible, vous pouvez revenir en arrière via la propriété de référence arrière parent jusqu'à ce que vous arriviez au nœud de départ. Il n'est pas difficile de construire le chemin en revenant comme ça :

     if v is the goal then
         let path be a stack
         path.push(v)
         while v is not the root do
             v := v.parent
             path.push(v)
         return path

Notez qu'en fonction de la structure de données réelle utilisée pour path, vous devrez peut-être l'inverser.

2
trincot 13 sept. 2020 à 19:01