Pas une solution mais peut-être que vous pouvez penser cette idée un peu plus loin. Le problème est que vous devrez calculer aussi le chemin le plus long possible pour obtenir tous les chemins. Le longest path problem est NP complet pour les graphes généraux, donc il obtiendra un temps très long même pour des graphes relativement petits (8x8 et plus). Imaginez que le sommet de début se trouve dans le coin supérieur gauche et que le sommet final se trouve 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
- matrice 3x3 => 2 ** *** 4 + 2 * 2 voies => 12
- 3x4 matrice => 2 ** *** 12 + 12 + 2 voies => 38
Chaque fois que j'ai combiné les résultats du calcul précédent pour le nombre actuel de chemins. Il se pourrait qu'il y ait un formulaire proche pour un tel graphe planaire, peut-être y a-t-il 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 C++ expert: - /) snippet 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 => 1262 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 bas, à droite coin, puis utilisez cette matrice pour rechercher rapidement le nombre de chemins. Dynamic programming (en utilisant les résultats calculés précédemment) pourrait accélérer les choses un peu.
Le nombre de chemins possibles sera beaucoup plus grand que le nombre de chemins considérés par un BFS, donc je ne vois pas comment cela pourrait aider. Un BFS combine plusieurs fois des chemins similaires, ce qui réduit la complexité. La complexité d'un BFS est O (| V | + | E |). – fgb
Voulez-vous une liste de tous les chemins ou juste le nombre de chemins? Si vous voulez le nombre de chemins, vous contenteriez-vous d'une approximation? – user287792
Je ne veux pas de liste d'entre eux. Je veux calculer le nombre d'entre eux sans les compter. –