Quel est un exemple d'un algorithme de Monte-Carlo pour trouver un chemin hamiltonien?

Question

J'ai récemment été informé qu'il existe un algorithme de Monte-Carlo (S?) Pour déterminer si un chemin hamiltonien existe dans un graphique.J'ai du mal à comprendre comment cela fonctionnerait.Quel est l'élément aléatoire?

Answer 1

Il existe plusieurs algorithmes de ce type pour divers problèmes de graphique;Pour le chemin Hamiltonien, un exemple est dû à Björklund [1].Ces algorithmes sont souvent algébriques et «élément aléatoire» découle de l'application du Schwartz-Zippel Lemma .Habituellement, les algorithmes fonctionnent de sorte que la propriété graphique que nous souhaitons être intéressée est d'une manière ou d'une autre, comme un polynôme (multivarié) avec la propriété qui existe exactement lorsque le polynôme n'est pas identique à zéro.

---

[1] Björklund, Andreas."SUMS déterminants pour une hamilonicité non dirigée."Journal Siam sur l'informatique 43.1 (2014): 280-299.