Comment puis-je modifier l'algorithme de recherche en largeur en premier pour inclure également le chemin de la solution?

Question

J'ai le pseudo-code suivant dans mon livre pour une recherche en largeur:

function breadth_first_search: 
    begin 
     open := [Start] 
     closed := []; 
     while open != [] do 
      begin 
       remove leftmost state from open, call it X; 
        if X is a goal then return SUCCESS 
         else begin 
          generate children of X; 
          put X on closed; 
          discard children of X if already on open or closed; 
          put remaining children on right end of open; 
         end 
      end 
     return FAIL; 
    end 

J'ai mis en place un algorithme similaire me suivant ces instructions pseudo-code. Ma question est la suivante: quelle est la manière la plus simple de la modifier afin de maintenir le chemin de la solution?

Simplement savoir que je peux atteindre une solution n'est pas aussi utile que d'avoir une liste de transitions pour arriver à la solution.

Answer 1

Y a-t-il une possibilité de changer la structure de l'arborescence? Si tel est le cas, vous pouvez ajouter un pointeur parent dans chaque nœud/feuille, de sorte que lorsque vous trouvez la solution, vous montez en suivant les pointeurs parents jusqu'à la racine.

Answer 2

Définissez Parent[childNode] = currentNode lorsque vous mettez en file d'attente chaque nœud (lorsque vous définissez Visible[Node] = 1).

Ensuite, recherchez récursivement le tableau Parent, en commençant par le nœud que vous voulez et ajoutez chaque nœud que vous voyez dans le tableau Parent au chemin. est nil et la récursivité s'arrêtera là.