Je suis curieux de savoir s’il existe une différence fondamentale entre les versions de recherche de graphe et de recherche d’arbre concernant DFS, A * Recherches en intelligence artificielle?
Réponses
Trop de publicités?
ziggystar
Points
9538
À en juger par les questions / réponses, il semble y avoir beaucoup de confusion à propos de ce concept.
Le Problème, c'Est Toujours un Graphique
La distinction entre l'arbre de recherche et de graph search n'est pas enracinée dans le fait que votre problème est un arbre ou un graphe. Il est toujours supposé que vous avez affaire à un graphique. La distinction réside dans la traversée de motif qui est utilisé pour la recherche dans le graphique, qui peut être graphique ou en forme en forme d'arbre.
Si vous faites affaire avec un arbre en forme de problème, les deux variantes de l'algorithme de conduire à des résultats équivalents. Ainsi, vous pouvez choisir la plus simple de l'arbre de recherche de la variante.
La différence Entre le Graphique et l'Arbre de Recherche
Votre base graphique de l'algorithme de recherche ressemble à quelque chose comme ce qui suit. Avec un nœud de démarrage start, dirigé bords successors et goal spécification utilisée dans la condition de la boucle. open détient les nœuds dans la mémoire, qui sont actuellement à l'étude, la liste ouverte. Notez que le pseudo-code suivant n'est pas correct dans tous les aspects (2).
L'Arbre De Recherche
open <- []
next <- start
while next isn't goal {
open += successors of next
next <- select from open
remove next from open
}
return next
Selon la façon dont vous implémentez select from open, vous obtenez différentes variantes des algorithmes de recherche, comme depth-first search (DFS) (pick dernier élément en date), la largeur de la première recherche (choisir la plus ancienne de l'élément) ou de coût uniforme de recherche (sélection de l'élément avec les plus bas coût de chemin), la popularité d'Un star de recherche en sélectionnant le nœud avec les plus bas coût plus heuristique de la valeur, et ainsi de suite.
L'algorithme ci-dessus est en fait appelé arbre de recherche. Il visitera un état du problème sous-jacent graphique plusieurs fois, s'il y a plusieurs chemins orientés à l'enracinement dans l'état de départ. Il est même possible de visiter un état un nombre infini de fois, si elle se trouve sur une boucle. Mais chaque visite correspond à un autre nœud dans l'arbre généré par notre algorithme de recherche. Cette apparente inefficacité est parfois voulu, comme expliqué plus loin.
Graphique Recherche
Comme nous l'avons vu, l'arbre de recherche est possible de visiter un état à plusieurs reprises. Et en tant que tel, il va explorer les "sous l'arbre" trouvés après cela plusieurs fois, ce qui peut être coûteux. Graph search corrige cela en gardant la trace de tous les états visités dans une liste fermée. Si un nouvellement trouvé de successeur de l' next est déjà connu, il ne sera pas inséré dans la liste ouverte:
open <- []
closed <- []
next <- start
while next isn't goal {
closed += next
open += successors of next, which are not in closed
next <- select from open
remove next from open
}
return next
Nous remarquons que le graphe de recherche nécessite plus de mémoire, car il garde la trace de tous les états visités. Mais cela peut souvent être plus que compensé par l'amélioration de l'efficacité de recherche, ce qui peut également conduire à une plus petite liste ouverte.
La Différence Importante: L'Optimalité
Il semble donc que le graphe de recherche, est simplement plus efficace que l'arbre de recherche, et nous devrions toujours le préfère (peut-être à moins que notre problème est un arbre, et il ne fera pas une différence). Mais il y a un aspect important: les solutions optimales.
Certaines méthodes de mise en œuvre de select peut garantir le retour des solutions optimales - c'est à dire un plus court chemin ou d'un sentier avec un coût minime (pour les graphes avec des coûts attachés aux bords). Cela tient essentiellement à chaque fois que les nœuds ne sont pas développés dans l'ordre croissant de coût. Comme à l'époque une meilleure voie à un certain état peut être trouvé plus tard et pourrait être ignorées par le graphe de recherche. Cela est vrai par exemple pour la DFS.
Une étoile
Aussi le très populaire Une star de l'algorithme est en mesure d'offrir une solution optimale lorsqu'il est utilisé avec un admissable heuristique - mais seulement en tant qu'une instance de l'arbre de recherche.
(2) les Défauts de la pseudo-code
Pour des raisons de simplicité, le présent code ne doit pas:
- poignée à défaut de recherches, c'est à dire qu'il ne fonctionne que si une solution peut être trouvée
njlarsson
Points
714
Un arbre est un cas particulier de graphe, donc tout ce qui fonctionne pour général graphiques œuvres pour les arbres. Un arbre est un graphe où il y a précisément un chemin entre chaque paire de nœuds. Cela implique qu'il ne contient pas de cycles, comme une réponse précédente unis, mais un graphe orienté sans cycle (DAG, graphe dirigé acyclique) n'est pas nécessairement un arbre.
Toutefois, si vous savez que votre graphique a certaines restrictions, par exemple, que c'est un arbre ou d'un DAG, habituellement vous pouvez trouver quelques plus efficace de l'algorithme de recherche que pour un illimité graphique. Par exemple, il n'a probablement pas beaucoup de sens d'utiliser Un*, ou de sa non-heuristique de contrepartie "de l'algorithme de Dijkstra", sur un arbre (où il y a un seul chemin pour choisir de toute façon, que vous pouvez trouver par DFS ou BFS) ou sur un DAG (où une trajectoire optimale peut être trouvée en considérant les sommets dans l'ordre obtenu par le tri topologique).
Comme prévu vs non orienté, un graphe non-dirigé est un cas particulier de a réalisé, à savoir le cas qui suit la règle "si il existe une arête (lien, transition) de u à v , il est aussi un bord de v à u.
Mise à jour: Notez que si ce qui vous intéresse, c'est le motif de la traversée de la recherche plutôt que de la structure du graphe lui-même, ce n'est pas la réponse. Voir, par exemple, @ziggystar de réponse.
0605002
Points
5702
La seule différence entre un graphe et d'un arbre est cycle. Un graphe peut contenir des cycles, un arbre ne peut pas. Ainsi, lorsque vous allez mettre en œuvre un algorithme de recherche dans un arbre, vous n'avez pas besoin de tenir compte de l'existence de cycles, mais quand on travaille avec un graphe arbitraire, vous aurez besoin de les examiner. Si vous ne le manipulez pas les cycles, l'algorithme peut éventuellement tomber dans une boucle infinie ou une récursivité sans fin.
Un autre point à penser, c'est les propriétés directionnelles du diagramme que vous avez affaire. Dans la plupart des cas, nous avons affaire avec des arbres qui représentent les relations parent-enfant à chaque bord. Un DAG (graphe dirigé acyclique) montre aussi des caractéristiques similaires. Mais bi-directionnelle graphiques sont différentes. Chaque bord dans un bi-directionnelle graphiques représentent les deux voisins. Si les approches algorithmiques doivent différer un peu pour ces deux types de graphiques.
