Znajdź wszystkie możliwe ścieżki w skierowanym grafie cyklicznym

Weźmy po prostu ten typowy wzorzec, który pokazuje się na wykresie:

A ---> B
|     /|
|    / v
|   /  C
|  /   |
| /    |
vv    /
D <---

Przepraszam za sztukę ASCII. Masz tutaj trzy ścieżki: A -> D, A -> B -> D i A -> B -> C -> D.

Teraz powiedz, że masz dokładnie tę samą liczbę emanującą z D do innego węzła G:

D ---> E
|     /|
|    / v
|   /  F
|  /   |
| /    |
vv    /
G <---

Masz te same analogiczne trzy ścieżki jak poprzednio: D -> G, D -> E -> G i D -> E -> F -> G.

Ile jest ścieżek od A do G?

Aby dostać się z A do G, musisz dostać się z A do D. Możesz to zrobić na jeden z trzech sposobów. Następnie musisz dostać się z D do G. Możesz to zrobić na jeden z trzech sposobów. Te dwie opcje (A do D i D do G) są od siebie niezależne. W ten sposób masz 3 * 3 = 9 możliwych ścieżek od A do G.

Jeśli będziesz powtarzać figurę, przy każdym powtórzeniu mnożysz liczbę możliwych ścieżek przez 3. Tak więc z trzema postaciami, 27 ścieżek; z czterema cyframi, 81 ścieżek; itp.

To wykładniczy wzrost. Innymi słowy: będziesz musiał znaleźć inny sposób na zrobienie tego, co robisz, jeśli chcesz działać skutecznie.

EDYCJA: Aby uzyskać przybliżone oszacowanie: licząc tylko te liczby, nawet nie patrząc na skomplikowane układy w środku, otrzymuję 3 * 3 * 3 * 3 * (2^8) * (4^8) * 3 * 3 * 2 * 3 = 73383542784 możliwych ścieżek, przez tylko te proste węzły.

EDYCJA: Wydaje się, że robisz analizę kodu. Nie wiedząc dokładnie, co chcesz zrobić, zalecam konsolidację wszelkich informacji, które zbierasz wzdłuż tych węzłów, do których musi dotrzeć (np. węzły A, D i G w moich przykładowych liczbach). Następnie wyszukuj, aż dojdziesz do następnego węzła, do którego musi dotrzeć, i zbierz tam również swoje informacje. Zapobiegnie to wykładniczemu wysadzaniu.