Comment représenter les données à utiliser pour DFS/BFS

Question

J'ai été assigné un problème à résoudre en utilisant diverses techniques de recherche. Le problème est très similaire au problème Escape From Zurg ou le problème . Mon problème est que je suis perdu quant à la façon de représenter les données en tant qu'arbre.

C'est ma supposition quant à la façon de le faire, mais cela n'a pas beaucoup de sens pour la recherche.

Une autre façon pourrait être d'utiliser un arbre binaire triés par leur temps de marche. Cependant, je ne suis toujours pas sûr si j'attaque ce problème correctement puisque les algorithmes de recherche n'exigent pas nécessairement des arbres binaires.

Des conseils sur la représentation de ces données seraient appréciés.

Answer 1

Généralement lorsque vous utilisez une recherche arborescente pour résoudre un problème, chaque nœud représente un "état" possible du monde (qui est sur quel côté du pont, par exemple), et les enfants de chaque nœud représentent tous les possibles "états successeurs" (nouveaux états qui peuvent être atteints en un mouvement par rapport à l'état précédent). Une recherche en profondeur consiste ensuite à essayer une option jusqu'à ce qu'elle se termine, puis à revenir au dernier état où une autre option était disponible et à l'essayer. Une recherche de grande envergure consiste à essayer de nombreuses options en parallèle et à voir quand le premier d'entre eux trouve le nœud de but.

En termes de codage réel, vous représenteriez ceci comme un arbre multi-voies. Chaque nœud contiendrait probablement l'état actuel, plus une liste de pointeurs vers des nœuds enfants.

Espérons que cela aide!

Answer 2

U pourrait utiliser quelque chose comme ceci:

public class Node 
{ 
    public int root; 
    public List<Node> neighbours; 
    public Node(int x) 
    { 
     root=x; 
    } 
    public void setNeighboursList(List<Node> l) 
    { 
     neighbours = l; 
    } 
    public void addNeighbour(Node n) 
    { 
     if(neighbours==null) neighbours = new ArrayList<Node>(); 
     neighbours.add(n); 
    } 
    ... 
} 

public class Tree 
{ 
    public Node root; 
    .... 
}