Où puis-je trouver du code pour générer des promenades auto-évitables aléatoires sur des réseaux à 2 et 3 dimensions dont les longueurs latérales sont des puissances de deux? La marche doit passer par tous les points du réseau Plus précisément, comment puis-je trouver un chemin hamiltonien aléatoire sur une grandeou graphique en grille?
La distribution ne doit pas être complètement uniforme, mais en général, le réseau doit avoir l'air froissé. La méthode utilisée pour générer le chemin devrait avoir une faible probabilité de produire des tronçons de ligne droite extrêmement longs.
random-walks
lattices
J. Antonio Perez
la source
la source
Réponses:
Une procédure est décrite dans Un algorithme combinatoire pour la génération efficace de longues chaînes de réseau compactes maximales .
la source
Voici deux implémentations javascript d'un algorithme pour échantillonner des chemins hamiltoniens sur des graphiques à grille bidimensionnelle: http://clisby.net/projects/hamiltonian_path/ et http://clisby.net/projects/hamiltonian_path/hamiltonian_path_v1.html (c'est mon code. L'implémentation au premier lien a plus de fonctionnalités, tandis que le second vous permet de télécharger la séquence des sites visités par le chemin d'accès.)
Les programmes javascript génèrent des chemins hamiltoniens sur une grille n × n en utilisant le mouvement de morsure décrit dans l'article «Structures secondaires dans les polymères longs compacts» de Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen et Jané Kondev, Phys. Rev. E 74, 051801 (2006). Papier disponible via l'APS (abonnement requis) ou en pré-impression sur l'arXiv à https://arxiv.org/abs/cond-mat/0508094
Le code comprend un paramètre réglable qui détermine la proximité de la distribution uniforme de votre échantillon, et vous pouvez adapter la méthode (chaîne de Markov Monte Carlo avec mouvements de morsure) aux graphiques de grille 3D avec un peu de travail.
la source