Trouver un chemin hamiltonien dans un graphique

Question

Déclaration de problème

donné un graphique de tous les carrés bleus dans l'image suivante où chaque carré bleu est connecté à d'autres carrés bleues dans les 4 directions cardinales.

donné tout nœud de départ.

Quel algorithme permettra de trouver le chemin le plus long (ish).

Considérant que chaque nœud ne peut être visité qu'une seule fois.

Considérant que nous ne nous soucions pas d'où se termine le chemin.

Considérant que la vitesse est plus importante que nécessairement visiter chaque noeud.

Exemple

J'ai tracé un exemple du résultat souhaité dans l'image ci-dessous.Comme vous pouvez le constater, le chemin ne visit pas chaque noeud et c'est bien.Je recherche un algorithme rapide qui me donnera l'un des plus longs chemin possibles sur ce graphique.80% de couverture ou plus est ce que je tire pour.

Answer 1

J'ai fini par utiliser le UCT (MCT avec UCB1) algorithme mais avec une torsion.

Normalement, dans UCT, la phase de simulation est une lecture simulée d'une partie avec des mouvements choisis au hasard. Si le jeu simulé se termine dans une victoire, le score du nœud, de l'endroit où la simulation a été jouée, et tous les scores de parents de ses parents jusqu'à la racine, sont incrémentés de 1.

Dans ma mise en œuvre, le "jeu" simulé "est en fait une promenade aléatoire dans l'arbre des tuiles voisines qui n'ont pas encore été visitées. Une fois que la simulation atteint un nœud de terminal (décès), il attribue un score de S= D / M où d est la profondeur du nœud terminal dans l'arborescence et m est la profondeur maximale possible.

sur une grille de 15 x 15 sans obstacles, vous allez définir M à 225 au fur et à mesure que le chemin le plus long visiterait tous les tuiles. J'ai défini le mien légèrement inférieur à celui que j'ai besoin de l'algorithme à généraliser et de travailler sur des cartes générées au hasard qui ont généralement 10 à 30 tuiles occupées par des obstacles.

Au lieu d'incrémenter le score des parents, l'algorithme de retour en arrière définit le score de chaque parent sur le score nouvellement calculé, s'il est supérieur à leur score actuel. En d'autres termes, le score d'un nœud représente toujours la longueur du chemin le plus long atteint jusqu'à présent de ce nœud.

UCT utilise UCB1 afin de sélectionner le nœud à exploiter ou à explorer une fois que tous les enfants du nœud actuel ont été élargis et que j'ai en grande partie tenu avec cela. La seule modification que j'ai faite est au terme d'exploitation. Dans UCB1, le terme d'exploitation est w / v où w est le score accumulé du nœud et V est le nombre de temps que le nœud a été visité. Cela fonctionne bien dans un jeu où vous souhaitez sélectionner le mouvement qui optimise vos chances de gagner. Dans mon cas, puisque le score ne reflète pas une fonction binaire de win= 1 et de perdre= 0 mais plutôt une échelle de 0= chemin super court vs 1= le chemin le plus long possible et je veux descendre le chemin le plus long trouvé par l'algorithme , Je mets simplement définir le terme d'exploitation à S= score= chemin le plus long accessible à partir de ce nœud.

Le contexte dans lequel j'utilise cet algorithme me permet d'environ 40 ms de temps de calcul dans un environnement Nodejs avant que je doive sélectionner un geste. Cela donne généralement environ 785 travers d'arbres sur ma machine. En moyenne, à cette époque, et sur la carte montrée dans OP, cet algorithme trouvera un chemin de 70 nœuds profonds. Ce qui est plus que suffisant pour que mes objectifs constatent que je commence à exécuter l'algorithme à nouveau le prochain tour. En pratique, lors de l'utilisation de cet algorithme pour sélectionner les prochains mouvements, je finis par déplacer un chemin de 100 à 110 marches avant de frapper une mort et je couvre une très grande partie des tuiles bleues.

Pour le plaisir, j'ai dirigé l'algorithme pendant de plus de 300 000 travers (30 secondes sur ma machine), en moyenne encore sur la carte indiquée en op, il trouve un chemin de 125 nœuds profonds qui est jolie. près de la profondeur maximale sur cette carte.

Answer 2

C'est le problème de chemin le plus long.C'est NP-Difficile de trouver le chemin le plus long dans un graphique général.Vous pouvez essayer d'appliquer n'importe quel algorithme standard pour trouver des chemins les plus longs.Recherche sur ce site pour "chemin le plus long" et "chemin hamiltonien" pour trouver de nombreuses références.Puisque vous êtes prêt à accepter des solutions sous-optimales, vous pouvez rechercher un algorithme heuriste ou approximatif (par exemple, à l'aide d'un algorithme de recherche local).