Załóżmy, że mamy skierowany wykres i dwa węzły A i B . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego:
Czy istnieją co najmniej dwie ścieżki między i B o tej samej długości?
Co powiesz na złożoność? Czy mogę to rozwiązać w czasie wielomianowym?
Chciałbym dodać nowe ograniczenie na wykresie, być może problem jest bardziej rozwiązywalny. W macierzy przylegania każda kolumna nie jest pusta. Tak więc każdy węzeł ma co najmniej jedną strzałkę na wejściu, a także co najmniej jeden węzeł jest podłączony do siebie. Więc jeśli węzeł jest węzłem, to ( i , i ) jest krawędzią na wykresie.
complexity-theory
graph-theory
time-complexity
graphs
Paolo Parisen T.
źródło
źródło
Odpowiedzi:
Rozważmy wykres , chcemy wiedzieć, czy istnieją dwie różne ścieżki od A do B o tej samej długości. Co robić? Proste: koduj dwie ścieżki w jednym. Zdefiniuj wykres G ′ z wierzchołkami V × V × { 0 , 1 } . Zrobić krok w G ' tworząc dwa niezależne kroki w G . Dodatkowy bit informuje, czy dwie ścieżki już się od siebie oddzieliły.sol ZA b G′ V×V×{0,1} G′ G
Formalnie istnieje krawędź w G ′ iff i → i ′ , j → j ′ w G i e ′ = e ∨ ( i , i ′ ) ≠ ( j , j ′ ) .(i,j,e)→(i′,j′,e′) G′ i→i′ j→j′ G e′=e∨(i,i′)≠(j,j′)
Algorytm sprawdza, czy istnieje ścieżka do ( B , B , 1 ) w G ′ , czyli O ( V 4 ) , czy coś w rodzaju O ( ( V + E ) 2 ) .(A,A,0) (B,B,1) G′ O(V4) O((V+E)2)
Jeśli zgodzisz się, że ten algorytm jest poprawny, to w konsekwencji ścieżka w ma długość co najwyżej 2 n 2 , dlatego potencjalne „kolizje ścieżki” muszą wystąpić najpóźniej na tej długości. Z tej obserwacji można uzyskać algorytm O ( V ω log V ) , gdzie ω jest złożonością mnożenia macierzy (zapytaj, czy potrzebujesz spoilera ...).G′ 2n2 O(VωlogV) ω
Mocno czuję, że istnieje algorytm , który wykorzystuje więcej struktury problemu.O(V+E)
źródło
Prawdopodobnie mam odpowiedź na ten problem, ale nie jestem pewien, czy to działa.
Nie jest ważne, aby „znaleźć” dwie ścieżki, jedyną ważną rzeczą jest „wiedzieć”, czy istnieją, czy nie. Nie sądzę, że jest to NP całkowity problem.
Więc, weź macierz sąsiedztwa . Możemy łatwo założyć, że jest wypełniony wartością 0,1. (0 = brak krawędzi; 1 = istnieje krawędź) Użyjmy następującej algebry z 3 wartościami (0,1,2), gdzie wszystko działa jak zwykle oprócz: 2 + <something> = 2 ; 2 ∗ <cokolwiek większego niż 0> = 2A 2+<something>=2 2∗<whatever greater than 0>=2
Tak więc, jeśli istnieją dwie ścieżki o tej samej długości od oczekuję, że istnieje wartość p taka, że ( A p ) i , j = 2 .i,j p (Ap)i,j=2
Niech jest liczbą wierzchołków na wykresie (lub, powiedzmy, że A ma wymiar n × n ). Nie znam wartości p , ale jeśli iteruję A , mnożąc się przez co najwyżej n 2, powinienem znaleźć odpowiedź. (więc p < n 2 ) (sens polega na tym, że sprawdzam A , następnie sprawdzam A 2 , następnie sprawdzam A 3 i tak dalej ...)n A n×n p A n2 p<n2 A A2 A3
oto moja argumentacja:
Zatrzymuję się na iteracji, gdy znalazłem .(Ap)i,j=2
czy się mylę?
źródło