Algorytm znalezienia różnych ścieżek z A do B na ciężarze, skierowanej, cykliczne wykresie

Question

Załóżmy, że mamy DIRECTED, WAŻONY i Cyclic wykres.

Załóżmy, opiszemy tylko w ścieżkach z całkowitej masy poniżej MAX_WEIGHT

co jest najbardziej odpowiedni (lub występuje) algorytm, aby znaleźć numer oddzielnych ścieżek między węzłami A i B o łącznej wadze mniejszej niż MAX_WEIGHT?

P.S: To nie jest moja praca domowa. Tylko osobisty, niekomercyjny projekt.

Answer 1

Jeżeli liczba węzłów i MAX_WEIGHT nie są zbyt duże (i wszystkie wagi są liczbami całkowitymi), można użyć programowania dynamicznego

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes]; 

zainicjować 0, z wyjątkiem num_of_paths[0][start] = 1;. Roztwór jest sumą num_of_paths[w][target], 0 <= w <= MAX_WEIGHT.

Answer 2

Prosta rekursja. Masz to w wykładniczym czasie. Oczywiście nie dopuszcza się cykli zerowych.

funkcja Noe (węzeł N limit wagi W)

1. nr. ścieżki wynosi zero, jeśli wszystkie wychodzące krawędzie mają masę> W

2. inaczej nie. ścieżki to suma liczb ścieżki uzyskanych przez sumę (noe (C1, W-W1), noe (C2, W-W2), ... noe (Cn, W-Wn)), gdzie C1 ... Cn są węzły podłączone do N, dla których W-Wi nie jest ujemne, gdzie Wi jest masą łączącej krawędzi, napisane w twoim ulubionym języku.

Powinno istnieć bardziej skuteczne rozwiązanie, zgodnie z algorytmem Dijkstry, ale myślę, że wystarczy to do pracy domowej.

Answer 3

Problemu bardziej ogólnego przypadku K-Disjoint Path In directed planar graphs, a nie stałe K.

K rozłączne ścieżki problem dla skierowanych płaskich wykresach jest następująco:

podane: skierowanego płaskiej wykres G = (V ; E) i k par (r ; s); ....; (r _k; s _k) wierzchołków G;

znaleźć: k parami wierzchołek-rozłącznych skierowane ścieżek P ; ...; P _K G, gdzie P _i biegnie od R _i Do S i (i = 1, ...., K).

w K-rozłączne ścieżki można narysować łuk ze wszystkich s _i do B, a także łuk od A do wszystkich r _i przez ten sposób stworzyć wykres G”z G.

Teraz, jeśli możesz rozwiązać swój problem w G 'w P możesz rozwiązać k-rozłączną ścieżkę w G, So P = NP.

Ale jeśli czytasz powiązaną pracę, daje to pewien pomysł na ogólny wykres (rozwiązanie k-rozłącznej ścieżki ze stałym k) i możesz go użyć, aby uzyskać dobre przybliżenie.

Również jest bardziej skomplikowany algorytm, który rozwiązuje ten problem w P (dla stałej k) w ogólnych wykresach. ale w sumie to nie jest łatwe (to jest Seymour).

Twoim najlepszym wyborem jest obecnie użycie algorytmów brutalnej siły.

Edit: Ponieważ MAXWEIGHT jest niezależny do wielkości wejściowej (twój rozmiar wykres) To nie ma wpływu na ten problem, także dlatego, że jest NP-trudny do undirected nieważone wykresu, nadal po prostu można go zawrzeć jest NP-trudny .