Quelle est la différence entre les versions de recherche graphique et de recherche arborescente concernant les recherches DFS, A * en intelligence artificielle ?

À en juger par les réponses existantes, il semble y avoir beaucoup de confusion à propos de ce concept.

Le problème est toujours un graphique

La distinction entre recherche arborescente et recherche graphique n'est pas enracinée dans le fait que le graphe problématique est un arbre ou un graphe général. On suppose toujours que vous avez affaire à un graphique général. La distinction réside dans le modèle de parcours utilisé pour rechercher dans le graphique, qui peut être en forme de graphique ou en forme d'arbre.

Si vous avez affaire à un problème en forme d'arbre , les deux variantes d'algorithme conduisent à des résultats équivalents. Vous pouvez donc choisir la variante de recherche d'arbre la plus simple.

Différence entre la recherche graphique et arborescente

Votre algorithme de recherche graphique de base ressemble à ceci. Avec un nœud de départ start, des arêtes dirigées comme successorset une goalspécification utilisée dans la condition de boucle. openconserve les nœuds en 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).

Recherche d'arbre

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

Selon la façon dont vous implémentez select from open, vous obtenez différentes variantes d'algorithmes de recherche, comme la recherche en profondeur d'abord (DFS) (sélectionner l'élément le plus récent), la recherche en largeur en premier (BFS) (sélectionner l'élément le plus ancien) ou la recherche à coût uniforme (sélectionner l'élément avec le coût de chemin le plus bas ), la recherche populaire A-star en choisissant le nœud avec le coût le plus bas plus la valeur heuristique , et ainsi de suite.

L'algorithme indiqué ci-dessus est en fait appelé recherche arborescente . Il visitera plusieurs fois un état du graphe de problème sous-jacent, s'il existe plusieurs chemins dirigés vers celui-ci s'enracinant dans l'état de départ. Il est même possible de visiter un état un nombre infini de fois s'il se trouve sur une boucle dirigée. Mais chaque visite correspond à un nœud différent dans l'arbre généré par notre algorithme de recherche. Cette apparente inefficacité est parfois souhaitée, comme expliqué plus loin.

Recherche graphique

Comme nous l'avons vu, la recherche arborescente peut visiter un état plusieurs fois. Et en tant que tel, il explorera plusieurs fois le "sous-arbre" trouvé après cet état, ce qui peut être coûteux. La recherche graphique résout ce problème en gardant une trace de tous les états visités dans une liste fermée . Si un successeur nouvellement trouvé nextest déjà connu, il ne sera pas inséré dans la liste ouverte:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Comparaison

Nous remarquons que la recherche de graphe nécessite plus de mémoire, car elle garde une trace de tous les états visités. Cela peut être compensé par la plus petite liste ouverte, ce qui améliore l'efficacité de la recherche.

Solutions optimales

Certaines méthodes de mise en œuvre selectpeuvent garantir de renvoyer des solutions optimales - c'est-à-dire un chemin le plus court ou un chemin avec un coût minimal (pour les graphiques avec des coûts attachés aux arêtes). Cela est valable chaque fois que les nœuds sont développés par ordre croissant de coût, ou lorsque le coût est une constante positive non nulle. Un algorithme courant qui implémente ce type de sélection est la recherche de coût uniforme , ou si les coûts d'étape sont identiques, BFS ou IDDFS . IDDFS évite la consommation de mémoire agressive de BFS et est généralement recommandé pour la recherche non informée (aka force brute) lorsque la taille des pas est constante.

UNE*

De plus, l' algorithme de recherche d' arborescence A * (très populaire) fournit une solution optimale lorsqu'il est utilisé avec une heuristique admissible . L' algorithme de recherche de graphe A * , cependant, n'offre cette garantie que lorsqu'il est utilisé avec une heuristique cohérente (ou "monotone") (une condition plus forte que l'admissibilité).

(2) Failles du pseudo-code

Par souci de simplicité, le code présenté ne:

• gérer les recherches qui ont échoué, c'est-à-dire que cela ne fonctionne que si une solution peut être trouvée

Un arbre est un cas particulier d'un graphe, donc tout ce qui fonctionne pour les graphes généraux fonctionne 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 aucun cycle, comme l'indique une réponse précédente, mais un graphe orienté sans cycles (un DAG, graphe acyclique dirigé) n'est pas nécessairement un arbre.

Cependant, si vous savez que votre graphe a certaines restrictions, par exemple qu'il s'agit d'un arbre ou d'un DAG, vous pouvez généralement trouver un algorithme de recherche plus efficace que pour un graphe sans restriction. Par exemple, il n'a probablement pas beaucoup de sens d'utiliser A *, ou son homologue non heuristique «l'algorithme de Dijkstra», sur un arbre (où il n'y a qu'un seul chemin à choisir de toute façon, que vous pouvez trouver par DFS ou BFS) ou sur un DAG (où un chemin optimal peut être trouvé en considérant les sommets dans l'ordre obtenu par tri topologique).

Comme pour dirigé vs non orienté, un graphe non orienté est un cas particulier d'un graphe dirigé, à savoir le cas qui suit la règle «s'il y a une arête (lien, transition) de u à v, il y a aussi une arête de v à u .

Mise à jour : Notez que si vous vous souciez du modèle de parcours de la recherche plutôt que de la structure du graphique lui-même, ce n'est pas la réponse. Voir, par exemple, la réponse de @ ziggystar.

La seule différence entre un graphique et un arbre est le cycle . Un graphique peut contenir des cycles, un arbre ne peut pas. Ainsi, lorsque vous allez implémenter un algorithme de recherche sur un arbre, vous n'avez pas besoin de tenir compte de l'existence de cycles, mais lorsque vous travaillez avec un graphe arbitraire, vous devrez les prendre en compte. Si vous ne gérez pas les cycles, l'algorithme peut éventuellement tomber dans une boucle infinie ou une récursivité sans fin.

Un autre point à considérer est les propriétés directionnelles du graphe que vous traitez. Dans la plupart des cas, nous traitons des arbres qui représentent des relations parent-enfant à chaque extrémité. Un DAG (graphique acyclique dirigé) présente également des caractéristiques similaires. Mais les graphiques bidirectionnels sont différents. Chaque arête dans un graphique bidirectionnel représente deux voisins. Les approches algorithmiques devraient donc différer un peu pour ces deux types de graphes.

GRAPHIQUE VS ARBRE

• Les graphiques ont des cycles
• Les arbres n'ont pas de cycles "Par exemple, imaginez n'importe quel arbre dans votre tête, les branches n'ont pas de connexions directes avec la racine, mais les branches ont des connexions avec d'autres branches, vers le haut"

Mais en cas de recherche de graphes AI vs recherche d'arbres

La recherche de graphe a une bonne propriété à chaque fois que l'algorithme explore un nouveau nœud et le marque comme visité, "Quel que soit l'algorithme utilisé", l'algorithme explore généralement tous les autres nœuds qui sont accessibles à partir du nœud actuel.

Par exemple, considérons le graphe suivant avec 3 sommets AB et C, et considérons ce qui suit les arêtes

AB, BC et CA, il y a un cycle de C à A,

Et quand DFS à partir de A, A générera un nouvel état B, B générera un nouvel état C, mais lorsque C est exploré, l'algorithme essaiera de générer un nouvel état A mais A est déjà visité, il sera donc ignoré. Cool!

Mais qu'en est-il des arbres? bien l'algorithme des arbres ne marque pas le nœud visité comme visité, mais les arbres n'ont pas de cycles, comment il entrerait dans des boucles infinies?

Considérez cet arbre à 3 sommets et considérez les arêtes suivantes

A - B - C enraciné en A, vers le bas. Et supposons que nous utilisons l'algorithme DFS

A générera un nouvel état B, B générera deux états A et C, car les arbres n'ont pas "Marquer un nœud visité s'il est exploré" donc peut-être que l'algorithme DFS explorera à nouveau A, générant ainsi un nouvel état B, donc nous entrons dans une boucle infinie.

Mais avez-vous remarqué quelque chose, nous travaillons sur des arêtes non dirigées c'est-à-dire qu'il y a une connexion entre AB et BA. bien sûr ce n'est pas un cycle, car le cycle implique que les sommets doivent être> = 3 et tous les sommets sont distincts sauf le premier et le dernier noeuds.

ST A-> B-> A-> B-> A ce n'est pas un cycle car il viole la propriété de cyclage> = 3. Mais en effet A-> B-> C-> A est un cycle> = 3 nœuds distincts Vérifié, le premier et le dernier nœud sont les mêmes vérifiés.

Considérons à nouveau les arêtes de l'arbre, A-> B-> C-> B-> A, bien sûr ce n'est pas un cycle, car il y a deux Bs, ce qui signifie que tous les nœuds ne sont pas distincts.

Enfin, vous pouvez implémenter un algorithme de recherche arborescente, pour éviter d'explorer deux fois le même nœud. Mais cela a des conséquences.

En termes simples, l'arbre ne contient pas de cycles et où le graphique le peut. Ainsi, lorsque nous effectuons une recherche, nous devrions éviter les cycles dans les graphiques afin de ne pas entrer dans des boucles infinies.

Un autre aspect est que l'arbre aura généralement une sorte de tri topologique ou une propriété comme l'arbre de recherche binaire qui rend la recherche si rapide et facile par rapport aux graphiques.