Sommaire

Algorithmes naïfs de recherche de chemins

Ces premiers algorithmes ne sont pas "intelligents" : ils sont dits naïfs, car ils n’utilisent pas de connaissances sur le problème pour agir. Dans le pire des cas, ils testent tous les chemins possibles pour déterminer s’il existe bien un chemin entre deux nœuds.

De plus, rien n’indique que le chemin trouvé est bien le plus court. Ils sont cependant faciles à implémenter.

1. Parcours en profondeur

C’est l’algorithme que l’on essaie naturellement dans un labyrinthe : on cherche à avancer le plus possible, et, si on est coincé, on revient à la dernière intersection que l’on a rencontrée et on teste un nouveau chemin.

Cet algorithme ne permet pas de déterminer le chemin le plus court, mais simplement de trouver un chemin.

a. Principe et pseudo-code

Son fonctionnement est assez simple.

Tout d’abord, on choisit l’ordre des parcours des nœuds puis on applique cet ordre pour avancer un maximum. Si l’on est bloqué, on retourne en arrière, et on teste la deuxième possibilité.

Le parcours en profondeur permet donc de déterminer l’existence d’un chemin, mais il ne prend pas en compte les longueurs des arcs, et donc ne permet pas de dire si l’on a trouvé le chemin le plus court.

De plus, le résultat obtenu dépend fortement de l’ordre choisi pour le parcours du graphe, l’ordre optimal ...