Discussion :

[ynsmtkl]

salut,

je cherche un algo de determination des chemins Hamiltonien, je souhait qu'il soit tres detaille, je suis debutant en algo
merci pour vos repences

[FR119492]

Salut!

J'ai trouvé dans Wikipedia:

Le problème du chemin Hamiltonien est aussi difficile que celui du graphe hamiltonien, puisqu'ils sont tous les deux NP-complets.

L'algorithme proposé par Adleman est le suivant:

• Générer un grand nombre de séquences, correspondant à des chemins aléatoires
• Filtrer (par exemple par la masse) pour ne garder que les chemins avec n sommets (où n est la taille du graphe)
• Filtrer pour ne garder que les chemins qui contiennent une fois chaque sommet
• S'il reste des séquences qui passent les deux filtres, le graphe a un chemin hamiltonien.

Jean-Marc Blanc

[Arthur Rainbow]

Bonjour,

Je me permet d'insister, ma question suivant celle d'en dessous.
Cela donne t'il en pratique une bonne probabilité de trouver un de ces cycle?

Comment fait on pour choisir un chemin... Pour chaque arrête on tire aléatoirement si on la garde ou non? Ca me parait avoir une probabilité extrêmement faible de fonctionner.

En fait, mon problème est un peu plus étrange, je travaille sur des graphes de forme spécifique, les noeuds sont [[1,n]]^3, et les arrêtes relient les noeuds de distance euclidienne 1.
Des cycles hamiltoniens existent si et seulement si n est pair, et on peut facilement en exhiber. Pour n=10 cf http://www.eleves.ens.fr/home/milchior/struct/10/

Mais pour mon travail, j'ai besoin de cycle d'apparence aléatoire. (Ce n'est pas clairement défini, mais quand ce sera sculpté par des étudiant de l'école des beaux arts il faudra que ce soit "impressionnant à voir")
J'y arrive pour n=4 et n=6, mais à partir de 8 le seul algorithme que j'ai trouvé ne me rend rien, et il tourne depuis 12 heures.

Je suis donc à la recherche de divers algorithmes de créations de cycles hamiltoniens, afin de voir ce qu'ils me rendront.