Chcę znaleźć wszystkie możliwe ścieżki w skierowanym grafie cyklicznym. Napisałem program, który to robi, ale zauważyłem, że jeśli liczba węzłów wzrośnie powyżej 40 lub 50, zaczyna to trwać nieskończenie długo.

Teoretycznie mówiąc, ile ścieżek jest możliwych dla skierowanego cyklicznego grafu składającego się z N węzłów. Czy to jak silnia (N) czy coś takiego? Czy możesz zgadnąć następujący przykład ze 119 węzłami. Oczywiście pętle przechodzę tylko raz, więc można zignorować ścieżki cykliczne.

Obraz graficzny

4
pythonic 30 sierpień 2012, 19:59

2 odpowiedzi

Najlepsza odpowiedź

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.

3
Claudiu 30 sierpień 2012, 20:14

Możesz spróbować następujących rzeczy:

  • Znajdź węzły na swoim wykresie, które są częścią każdej ścieżki. Aby to zrobić, kolejno usuwaj węzły z wykresu. Takim węzłem jest każdy węzeł, którego usunięcie uniemożliwia znalezienie ścieżki. Twój wykres powinien mieć ich dużo.
  • Nie mogę tego udowodnić, ale powinno być możliwe znalezienie kolejności, w której te węzły pojawiają się na każdej ścieżce.
  • Podziel wykres na porcje, które składają się z dwóch kolejnych wymuszonych węzłów i wszystkich węzłów między nimi
  • Oblicz liczbę ścieżek dla każdej porcji
  • Oblicz iloczyn wszystkich zliczeń ścieżek, aby uzyskać pełną liczbę. Pamiętaj, aby używać czegoś takiego jak GMP, aby uniknąć przepełnienia liczb
0
fuz 30 sierpień 2012, 22:03