Jak ustalić, czy dwa węzły są połączone?

Question

Obawiam się, że może to działać w przypadku problemu NP-Complete. Mam nadzieję, że ktoś może mi dać odpowiedź, czy tak jest, czy nie. I szukam więcej odpowiedzi niż tylko tak lub nie. Chciałbym wiedzieć dlaczego. Jeśli można powiedzieć: „To jest w zasadzie ten problem«x», który jest/nie jest NP-zupełny. (Link wikipedia)”

(Nie to nie jest praca domowa)

Czy istnieje sposób, aby ustalić, czy dwa punkty są połączone na arbitralnym wykresie bezkierunkowym. na przykład, następujące

Well 
    | 
    | 
    A 
    | 
    +--B--+--C--+--D--+ 
    |  |  |  | 
    |  |  |  | 
    E  F  G  H 
    |  |  |  | 
    |  |  |  | 
    +--J--+--K--+--L--+ 
        | 
        | 
        M 
        | 
        | 
        House 

Punkty A chociaż M (nie „I”) są punkty kontrolne (jak zawór w przewodzie gazowym), które mogą być otwarte lub zamknięte. '+' Są węzłami (jak rury T), i domyślam się, że Studnia i Dom również są węzłami.

Chciałbym wiedzieć, czy zamykam arbitralny punkt kontrolny (np. C), czy Studnia i Dom są nadal połączone (inne punkty kontrolne również mogą być zamknięte). Np. Jeśli B, K i D są zamknięte, nadal mamy ścieżkę przez A-E-J-F-C-G-L-M, a zamknięcie C spowoduje odłączenie Studni i Domu. Oczywiście; jeśli tylko D było zamknięte, zamknięcie tylko C nie odłącza domu.

Innym sposobem na umieszczenie tego jest C most/krawędź/przesmyk?

Mogę traktować każdy punkt kontrolny jako wagę na wykresie (0 dla otwartych lub 1 dla zamkniętych); a następnie znajdź najkrótszą ścieżkę między Studnią a Domem (wynik> = 1 wskazuje, że zostały one rozłączone) Istnieje wiele sposobów na zwarcie algorytmu znalezienia najkrótszej ścieżki (np. odrzucenie ścieżki po osiągnięciu 1, zatrzymanie przeszukując, gdy mamy JAKĄKOLWIEK ścieżkę, która łączy Studnię i Dom itp.) I oczywiście, mogę też wprowadzić sztuczne ograniczenie liczby skoków, które należy sprawdzić przed poddaniem się:

Ktoś musiał sklasyfikować ten rodzaj problem przed, po prostu brakuje nazwy

Answer 1

Zobacz http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, Twój na e stop shop dla wszystkich problemów związanych z wykresem. Wierzę, że twój problem jest w rzeczywistości rozwiązalny w kwadratowym czasie.

Answer 2

nie NP-zupełny rozwiązał ze znanego rozwiązania -. Dijkstra's Algorithm

Answer 3

Dla mnie wygląda na to, że jesteś gotowy na rozwiązanie, ale możliwe, że źle zrozumiałem problem. Jeśli masz ochotę powiedzieć, i podać zamknięte krawędzie 1 jako wagę, możesz po prostu zastosować algorytm Dijkstry, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. To powinno rozwiązać twój problem w O (E * lg (V))

Answer 4

Problem znalezienia najkrótszej ścieżki nie jest NP-zupełny. Nazywa się Problem Najkrótszej Ścieżki (oryginalnie) i istnieje algorithms do rozwiązywania wielu różnych jego odmian.

Problem określenia, czy dwa węzły są połączone, nie jest również NP-zupełny. Możesz użyć pierwszego wyszukiwania w głąb, zaczynając od dowolnego węzła, aby określić, czy jest on połączony z drugim węzłem.

Answer 5

Twój opis wydaje się wskazywać, że interesuje Cię tylko to, czy dwa węzły są połączone, nie znajdując najkrótszej ścieżki.

Znalezienie jeśli dwa węzły są połączone jest stosunkowo proste:

Create two sets of nodes: toDoSet and doneSet 
Add the source node to the toDoSet 
while (toDoSet is not empty) { 
    Remove the first element from toDoList 
    Add it to doneList 
    foreach (node reachable from the removed node) { 
    if (the node equals the destination node) { 
     return success 
    } 
    if (the node is not in doneSet) { 
     add it to toDoSet 
    } 
    } 
} 

return failure. 

przypadku korzystania z tabeli mieszania lub coś podobnego do toDoSet i doneSet, wierzę, że jest to algorytm liniowy.

Należy zauważyć, że ten algorytm jest w zasadzie częścią znacznika zbierania śmieci z oznaczaniem i odejmowaniem.

Answer 6

Do tego problemu nie potrzebujesz algorytmu Dijkstry, ponieważ używa on sterty, która nie jest potrzebna i wprowadza współczynnik log (N) do złożoności. To jest po prostu pierwsze szukanie - nie włączaj zamkniętych krawędzi jako krawędzi.

Answer 7

Zakładając, że masz macierz sąsiedztwa:

bool[,] adj = new bool[n, n]; 

Gdzie bool [i, j] = true, jeśli istnieje otwarta droga między I i J oraz bool [i, j] = False.

public bool pathExists(int[,] adj, int start, int end) 
{ 
    List<int> visited = new List<int>(); 
    List<int> inprocess = new List<int>(); 
    inprocess.Add(start); 

    while(inprocess.Count > 0) 
    { 
    int cur = inprocess[0]; 
    inprocess.RemoveAt(0); 
    if(cur == end) 
     return true; 
    if(visited.Contains(cur)) 
     continue; 
    visited.Add(cur); 
    for(int i = 0; i < adj.Length; i++) 
     if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i)) 
     inprocess.Add(i); 
    } 
    return false; 
} 

Oto rekurencyjną wersję algorytmu powyżej (napisany w Ruby):

def connected? from, to, edges 
    return true if from == to 
    return true if edges.include?([from, to]) 
    return true if edges.include?([to, from]) 

    adjacent = edges.find_all { |e| e.include? from } 
        .flatten 
        .reject { |e| e == from } 

    return adjacent.map do |a| 
    connected? a, to, edges.reject { |e| e.include? from } 
    end.any? 
end 

Answer 8

Dijkstra jest przesada !! Po prostu użyj szerokości pierwszego wyszukiwania od A, aby wyszukać węzeł, do którego chcesz dotrzeć. Jeśli nie możesz go znaleźć, nie jest podłączony. Złożoność to O (nm) dla każdego wyszukiwania, które jest mniejsze niż Dijkstra.

Nieco związany jest problem z maksymalnym przepływem/minięciem. Sprawdź, może to być istotne dla twojego problemu.

Answer 9

Jeśli wszystko, czego potrzebujesz, to ustalenie, czy 2 węzły są podłączone, możesz zamiast nich używać zestawów, które są szybsze niż algorytmy wykresów.

1. Podziel cały wykres na krawędzie. Dodaj każdą krawędź do zestawu.
2. W następnej iteracji narysuj krawędzie między 2 zewnętrznymi węzłami krawędzi wykonanej w kroku 2. Oznacza to dodanie nowych węzłów (wraz z odpowiadającymi im zestawami) do zestawu, z którego pochodzi oryginalna krawędź. (w zasadzie scalanie)
3. Powtarzaj 2, aż 2 węzły, których szukasz, są w tym samym zestawie. Konieczne będzie również sprawdzenie po kroku 1 (na wypadek gdyby sąsiednie 2 węzły).

Początkowo węzły będzie każdy w swoim zestawie,

o o1 o o o o o o2 
\/ \/ \/ \/
o o  o o  o o  o o 
    \ /  \ /
    o o o o   o o o o 
     \    /
     o o1 o o o o o o2 

Ponieważ algorytm rozwija i łączy zestawy, względnie połówki wejście.

W powyższym przykładzie szukałem, czy istnieje ścieżka między o1 i o2. Tę ścieżkę znalazłem dopiero na końcu po scaleniu wszystkich krawędzi. Niektóre wykresy mogą mieć oddzielne komponenty (odłączone), co oznacza, że ​​nie będzie można mieć jednego zestawu na końcu. W takim przypadku można użyć tego algorytmu do testowania połączenia, a nawet policzyć liczbę składników na wykresie. Liczba komponentów to liczba zestawów, które możesz uzyskać po zakończeniu algorytmu.

Możliwym wykres (na drzewie powyżej):

o-o1-o-o-o2 
    | | 
    o o 
     | 
     o 

Answer 10

Każdy algorytm najkrótszej ścieżki wykres będzie przesadą, jeśli wszystko, co potrzebne jest do znalezienia, jeśli węzeł jest podłączony do drugiego. Dobra biblioteka Javy, która to zapewnia, to JGraphT. To użycie jest bardzo proste, oto przykładem wykresu Integer:

public void loadGraph() { 
    // first we create a new undirected graph of Integers 
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class); 

    // then we add some nodes 
    graph.addVertex(1); 
    graph.addVertex(2); 
    graph.addVertex(3); 
    graph.addVertex(4); 
    graph.addVertex(5); 
    graph.addVertex(6); 
    graph.addVertex(7); 
    graph.addVertex(8); 
    graph.addVertex(9); 
    graph.addVertex(10); 
    graph.addVertex(11); 
    graph.addVertex(12); 
    graph.addVertex(13); 
    graph.addVertex(14); 
    graph.addVertex(15); 
    graph.addVertex(16); 

    // then we connect the nodes 
    graph.addEdge(1, 2); 
    graph.addEdge(2, 3); 
    graph.addEdge(3, 4); 
    graph.addEdge(3, 5); 
    graph.addEdge(5, 6); 
    graph.addEdge(6, 7); 
    graph.addEdge(7, 8); 
    graph.addEdge(8, 9); 
    graph.addEdge(9, 10); 
    graph.addEdge(10, 11); 
    graph.addEdge(11, 12); 
    graph.addEdge(13, 14); 
    graph.addEdge(14, 15); 
    graph.addEdge(15, 16); 

    // finally we use ConnectivityInspector to check nodes connectivity 
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph); 

    debug(inspector, 1, 2); 
    debug(inspector, 1, 4); 
    debug(inspector, 1, 3); 
    debug(inspector, 1, 12); 
    debug(inspector, 16, 5); 
} 

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) { 
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2))); 
} 

Ten lib oferuje również wszystkie najkrótsze ścieżki, jak również algorytmy.