Nombre de voies acycliques distinctes de A [a, b] à A [c, d]?

Question

J'écris un solveur Sokoban pour le plaisir et la pratique, il utilise un algorithme simple (quelque chose comme BFS avec un peu de différence).

Maintenant, je veux estimer son temps de fonctionnement (O et oméga). mais il faut savoir comment calculer le nombre de chemins acyclique d'un sommet à l'autre dans un réseau. en fait je veux une expression qui calcule le nombre de chemins valides, entre deux sommets d'une matrice m * n de sommets.

un chemin valide:

• visites chaque sommet 0 ou une fois.
• ont pas de circuits

Par exemple ceci est un chemin valide:

texte alt http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

mais ce n'est pas:

texte alt http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

Ce qui est nécessaire est une méthode pour trouver le nombre de tous les chemins acyclique entre les deux sommets a et b .

commentaires sur la résolution des méthodes et astuces sont les bienvenus.

Answer 1

Pas une solution, mais peut-être que vous pouvez penser cette idée un peu plus loin. Le problème est que vous devez aussi calculer le chemin le plus long possible d'obtenir tous les chemins. le plus long problème de chemin est NP complet pour les graphes généraux, il obtiendra un temps très long même pour les graphiques relativement petits (8x8 et plus).

Imaginez le sommet de départ est dans le coin supérieur gauche et le sommet final est dans le coin inférieur droit de la matrice.

• Pour une matrice 1x2 il y a seulement 1 chemin possible
• 2x2 matrice => 2 *** 1 ** chemins => 2
• 3x2 matrice => 2 *** 2 ** chemins => 4
• 3x3 matrice => 2 *** 4 ** + 2 * 2 voies => 12
• 3x4 matrice => 2 *** 12 ** + 12 + 2 voies => 38

Everytime I a combiné les résultats du calcul précédent pour le nombre actuel de chemins. Il pourrait être qu'il ya un formular à proximité d'un tel plan graphique, peut-être il y a encore beaucoup de théorie pour cela, mais je suis trop stupide pour ça ...

Vous pouvez utiliser le Java suivant (désolé, je ne suis pas un expert c ++: - /) extrait pour calculer les chemins possibles pour les matrices plus grandes:

public static void main(String[] args) {
    new Main(3, 2).start();
}
int xSize;
int ySize;
boolean visited[][];

public Main(int maxX, int maxY) {
    xSize = maxX;
    ySize = maxY;
    visited = new boolean[xSize][ySize];
}

public void start() {
    // path starts in the top left corner
    int paths = nextCell(0, 0);
    System.out.println(paths);
}

public int nextCell(int x, int y) {
    // path should end in the lower right corner
    if (x == xSize - 1 && y == ySize - 1)
        return 1;

    if (x < 0 || y < 0 || x >= xSize || y >= ySize || visited[x][y]) {
        return 0;
    }

    visited[x][y] = true;
    int c = 0;
    c += nextCell(x + 1, y);
    c += nextCell(x - 1, y);
    c += nextCell(x, y + 1);
    c += nextCell(x, y - 1);
    visited[x][y] = false;
    return c;
}

=>

• 4x4 => 184
• 5x5 => 8512
• 6x6 => 1.262.816
• 7x7 (même ce cas simple prend beaucoup de temps!) => 575780564

Cela signifie que vous pouvez (seulement en théorie) calculer tous les chemins possibles à partir de toute position d'une matrice MxM au coin inférieur droit, puis utiliser cette matrice pour rechercher rapidement le nombre de chemins. de programmation dynamique (à l'aide des résultats calculés précédents) pourrait accélérer les choses un peu.

Answer 2

Le problème général de compter le nombre de chemins simples dans un graphique est complet #P. Quelques problèmes # P-complet ont des systèmes d'approximation randomisés entièrement polynomiale, et certains ne le font pas, mais vous prétendez ne pas être intéressé par une approximation. Peut-être il y a un moyen de tirer parti de la structure de la grille, car il est pour le calcul du polynôme Tutte, mais je n'ai pas d'idées sur la façon de le faire.

Answer 3

Il y a un problème similaire, mais moins général sur le projet Euler: http: // Project Euler .net / index.php? section = problèmes & id = 237

Je pense que certaines des solutions décrites dans le forum, il peut être étendu pour résoudre votre cas général. Il est un problème assez difficile cependant, en particulier pour votre cas général.

Pour avoir accès à leurs forums, vous devez d'abord résoudre le problème. Je ne vais pas poster la réponse ici, ni créer un lien vers un certain site qui répertorie la réponse, un site que vous pouvez facilement trouver sur google en recherchant quelque chose de vraiment évident.

Answer 4

Ceci est une question ouverte en mathématiques avec application directe à la chimie et la physique à l'utiliser pour modéliser des liaisons polymères. Quelques-uns des premiers travaux effectués sur cela a été fait au cours du projet Manhattan (bombe nucléaire Seconde Guerre mondiale.)

Il est mieux connu comme le problème de la Marche auto éviter.

J'ai passé un été à mon département de mathématiques universitaires recherche un algorithme appelé monte-carlo l'algorithme de pivot pour rapprocher les paramètres de l'ajustement asymptotique du nombre de chemins de randonnée autoévitantes d'un n de longueur donnée.

S'il vous plaît se référer à l'excellent livre de Gordon Slade intitulé " Le Self éviter Walk" pour une large couverture des types de techniques utilisées pour aborder ce problème ainsi loin.

Ceci est un problème très complexe et je me demande ce que votre motivation peut être pour l'examiner. Peut-être que vous pouvez trouver un modèle plus simple pour ce que vous voulez, parce que l'auto éviter Walks ne sont pas simples du tout.

Answer 5

Serait une matrice montrant le travail des bords? Envisager la construction d'une matrice montrant où les bords sont, i.e.. [A, b] = 1 <=> a-> b est un avantage dans le graphique, 0 sinon. Maintenant, soulever cette matrice à divers pouvoirs pour montrer combien de façons existent pour obtenir entre les sommets à l'aide de n étapes, puis les résumer pour obtenir le résultat. Ceci est juste une idée d'une façon de résoudre le problème, il peut y avoir d'autres façons de formuler le problème.

Je me demande si cela fait partie de mathoverflow , comme une autre idée

---

Il est vrai qu'une fois que vous avez une matrice zéro, vous pouvez arrêter exponentiation comme dans votre cas, il n'y a pas beaucoup d'endroits à aller au bout de 3, mais les chemins de 1 à 3 seraient le direct et celui qui traverse 2, donc il n'y a que quelques matrices pour ajouter ensemble avant le tout à zéro l'on se trouve.

---

Je pense qu'il devrait y avoir un moyen de calculer une borne de dire n ^ (n + 1), où n est le nombre de sommets du graphe, qui indiquerait un point d'arrêt que par ce point, tous les sommets aura été visité une fois. Je ne sais pas comment obtenir les chemins cycliques hors du problème cependant, ou peut-on supposer que le graphique est libre de cycles?