Visiter tous les nœuds d'un graphe en répétant le moins possible les visites.

Question

J'ai une carte basée sur des tuiles où plusieurs tuiles sont des murs et d'autres sont praticables. Les tuiles praticables constituent un graphe que j'aimerais utiliser dans la planification des chemins. Ma question est la suivante : existe-t-il de bons algorithmes pour trouver un chemin qui visite chaque nœud du graphe, en minimisant les visites répétées ?

Par exemple :

exemple de carte http://img220.imageshack.us/img220/3488/mapq.png

Si la tuile jaune inférieure est le point de départ, le meilleur chemin pour visiter toutes les tuiles avec le moins de répétitions est :

exemple de chemin d'accès http://img222.imageshack.us/img222/7773/mapd.png

Il y a deux visites répétées dans ce parcours. Un chemin plus difficile serait de prendre à gauche à la première intersection, puis de revenir en arrière sur trois tuiles déjà visitées.

Je ne me soucie pas du nœud final mais le nœud de départ est important.

Merci.

Edit :

J'ai ajouté des photos à ma question mais je ne peux pas les voir en la visualisant. Les voici :

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

De plus, dans les graphiques pour lesquels j'ai besoin de ces données, il n'y aura jamais de situation où min répétitions = 0. C'est-à-dire que pour marcher sur chaque tuile de la carte, le joueur doit croiser son propre chemin au moins une fois.

Answer 1

Votre formulation est mauvaise -- elle permet une réduction à un problème NP-complet. Si vous pouviez minimiser les visites répétées, alors vous pourriez les pousser à 0 et alors vous auriez un Cycle Hamiltonien . Ce qui est soluble mais difficile.

Answer 2

On dirait qu'il pourrait être transposé au problème du voyageur de commerce ... et donc qu'il est probablement complet NP et qu'aucun algorithme déterministe efficace n'est connu.

La recherche d'un chemin est assez simple : trouver un sous-arbre (ou le minimum) et effectuer une traversée en profondeur/en largeur d'abord. La recherche de la route optimale est la partie la plus difficile.

Vous pourriez utiliser l'une des techniques d'optimisation dynamique pour essayer de converger vers une solution relativement bonne.

À moins qu'il n'existe un attribut du sous-arbre d'envergure minimale qui pourrait être utilisé pour générer le meilleur chemin ... mais je ne me souviens pas assez de la théorie des graphes pour cela.