Algorytm wykresu, aby znaleźć wszystkie połączenia między dwoma dowolnymi wierzchołkami

117

Próbuję określić najlepszy czasowo algorytm do wykonania opisanego poniżej zadania.

Mam zestaw rekordów. Dla tego zestawu rekordów mam dane połączeń, które wskazują, jak pary rekordów z tego zestawu łączą się ze sobą. Zasadniczo reprezentuje to wykres nie skierowany, z rekordami będącymi wierzchołkami, a danymi połączenia krawędziami.

Wszystkie rekordy w zestawie zawierają informacje o połączeniu (tj. Nie ma żadnych osieroconych rekordów; każdy rekord w zestawie łączy się z jednym lub kilkoma innymi rekordami w zestawie).

Chcę wybrać dowolne dwa rekordy z zestawu i móc pokazać wszystkie proste ścieżki między wybranymi rekordami. Przez „proste ścieżki” rozumiem ścieżki, które nie mają powtarzających się zapisów na ścieżce (tj. Tylko ścieżki skończone).

Uwaga: dwa wybrane rekordy zawsze będą różne (tj. Wierzchołek początkowy i końcowy nigdy nie będą takie same; bez cykli).

Na przykład:

    Jeśli mam następujące rekordy:
        A, B, C, D, E.

    a następujący przedstawia połączenia: 
        (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E),
        (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E)

        [gdzie (A, B) oznacza, że ​​rekord A łączy się z rekordem B]

Gdybym wybrał B jako mój rekord początkowy i E jako rekord końcowy, chciałbym znaleźć wszystkie proste ścieżki przez połączenia rekordów, które łączyłyby rekord B z rekordem E.

   Wszystkie ścieżki łączące B z E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

To jest przykład, w praktyce mogę mieć zestawy zawierające setki tysięcy rekordów.

Robert Groves
źródło
Połączenia nazywane są cyklami , a ta odpowiedź ma dla Ciebie wiele informacji.
elhoim
3
Powiedz, czy chcesz mieć skończoną listę połączeń bez pętli, czy nieskończony strumień połączeń ze wszystkimi możliwymi pętlami. Por. Odpowiedź Blorgbearda.
Charles Stewart
czy ktoś może w tym pomóc ??? stackoverflow.com/questions/32516706/…
tejas3006

Odpowiedzi:

116

Wydaje się, że można to osiągnąć, przeszukując wykres najpierw w głąb. Przeszukiwanie w głąb znajdzie wszystkie niecykliczne ścieżki między dwoma węzłami. Ten algorytm powinien być bardzo szybki i skalowany do dużych wykresów (struktura danych wykresu jest rzadka, więc zużywa tylko tyle pamięci, ile potrzebuje).

Zauważyłem, że wykres, który wskazałeś powyżej, ma tylko jedną krawędź, która jest kierunkowa (B, E). Czy to była literówka, czy naprawdę jest to wykres skierowany? To rozwiązanie działa niezależnie. Przepraszam, że nie mogłem tego zrobić w C, jestem trochę słaby w tej dziedzinie. Spodziewam się jednak, że będziesz w stanie przetłumaczyć ten kod Java bez większych problemów.

Graph.java:

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

Search.java:

import java.util.LinkedList;

public class Search {

    private static final String START = "B";
    private static final String END = "E";

    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().depthFirst(graph, visited);
    }

    private void depthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            depthFirst(graph, visited);
            visited.removeLast();
        }
    }

    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

Wyjście programu:

B E 
B A C E 
B A C F E 
B F E 
B F C E 
Casey Watson
źródło
5
Należy pamiętać, że nie jest to przejście wszerz. Z szerokością najpierw odwiedzasz wszystkie węzły w odległości 0 od korzenia, potem te z odległością 1, potem 2 itd.
mweerden
14
Prawidłowo, to jest DFS. BFS musiałby użyć kolejki, kolejkując węzły poziomu (N + 1) do przetworzenia po wszystkich węzłach poziomu N. Jednak do celów PO będzie działać BFS lub DFS, ponieważ nie określono preferowanej kolejności sortowania ścieżek.
Matt J
1
Casey, od wieków szukałem rozwiązania tego problemu. Niedawno zaimplementowałem ten DFS w C ++ i działa świetnie.
AndyUK
6
Wadą rekurencji jest to, że jeśli będziesz mieć głęboki wykres (A-> B-> C -> ...-> N), możesz mieć StackOverflowError w java.
Rrr
1
Dodałem iteracyjną wersję w C # poniżej.
batta
23

Internetowy Słownik Algorytmów i Struktur Danych Narodowego Instytutu Standardów i Technologii (NIST) wymienia ten problem jako „ wszystkie proste ścieżki” i zaleca przeszukiwanie w głąb . CLRS dostarcza odpowiednie algorytmy.

Sprytny technika przy użyciu sieci Petriego znajduje się tutaj

Michael Dorfman
źródło
2
Czy możesz mi pomóc z lepszym rozwiązaniem? DFS działa wiecznie : stackoverflow.com/q/8342101/632951
Pacerier,
Zauważ, że łatwo jest wymyślić wykresy, dla których DFS jest bardzo nieefektywny, mimo że zestaw wszystkich prostych ścieżek między dwoma węzłami jest mały i łatwy do znalezienia. Na przykład, rozważmy graf bezkierunkowy, w którym węzeł początkowy A ma dwóch sąsiadów: węzeł docelowy B (który nie ma sąsiadów innych niż A) i węzeł C, który jest częścią w pełni połączonej kliki n + 1 węzłów. Mimo że z punktu A do B jest tylko jedna prosta droga, naiwny DFS zmarnuje O ( n !) Czas bezużytecznie eksplorując klikę. Podobne przykłady (jedno rozwiązanie, DFS wymaga czasu wykładniczego) można znaleźć również wśród DAG.
Ilmari Karonen
NIST mówi: „Ścieżki można wyliczyć za pomocą przeszukiwania w głąb”.
chomp
13

Oto pseudokod, który wymyśliłem. Nie jest to żaden szczególny dialekt pseudokodu, ale powinien być na tyle prosty do naśladowania.

Każdy chce to rozebrać.

  • [p] to lista wierzchołków reprezentujących bieżącą ścieżkę.

  • [x] to lista ścieżek spełniających kryteria

  • [s] jest wierzchołkiem źródłowym

  • [d] jest wierzchołkiem docelowym

  • [c] to bieżący wierzchołek (argument do procedury PathFind)

Załóżmy, że istnieje skuteczny sposób wyszukiwania sąsiednich wierzchołków (wiersz 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 wierzchołek [s], [d]

     4 PathFind (wierzchołek [c])
     5 Dodaj [c] na końcu listy [p]
     6 Dla każdego wierzchołka [v] sąsiadującego z [c]
     7 Jeśli [v] jest równe [d], to
     8 Zapisz listę [p] w [x]
     9 W przeciwnym razie, jeśli [v] nie znajduje się na liście [p]
    10 PathFind ([v])
    11 Następna dla
    12 Usuń ogon z [p]
    13 Powrót
Robert Groves
źródło
Czy możesz rzucić trochę światła na krok 11 i krok 12
użytkownik bozo
Linia 11 oznacza po prostu blok końcowy, który idzie z pętlą For, która rozpoczyna się w linii 6. Linia 12 oznacza usunięcie ostatniego elementu listy ścieżek przed powrotem do dzwoniącego.
Robert Groves
Jakie jest początkowe wywołanie PathFind - czy przekazujesz wierzchołek źródłowy [y]?
użytkownik bozo
W tym przykładzie tak, ale pamiętaj, że możesz nie chcieć pisać prawdziwego kodu, który odwzorowuje jeden do jednego za pomocą tego pseudokodu. Ma to raczej na celu zilustrowanie procesu myślowego niż dobrze zaprojektowany kod.
Robert Groves
8

Ponieważ istniejąca nierekurencyjna implementacja DFS podana w tej odpowiedzi wydaje się być zepsuta, pozwólcie, że przedstawię taką, która faktycznie działa.

Napisałem to w Pythonie, ponieważ uważam, że jest dość czytelny i niezakłócony szczegółami implementacji (i ponieważ zawiera przydatne yieldsłowo kluczowe do implementacji generatorów ), ale powinno być dość łatwe do przeniesienia na inne języki.

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

Ten kod utrzymuje dwa równoległe stosy: jeden zawierający wcześniejsze węzły w bieżącej ścieżce i jeden zawierający bieżący indeks sąsiadów dla każdego węzła w stosie węzłów (abyśmy mogli wznowić iterację przez sąsiadów węzła, gdy go wycofamy stos). Równie dobrze mogłem użyć pojedynczego stosu par (węzeł, indeks), ale pomyślałem, że metoda z dwoma stosami byłaby bardziej czytelna i być może łatwiejsza do wdrożenia dla użytkowników innych języków.

Ten kod używa również oddzielnego visitedzestawu, który zawsze zawiera bieżący węzeł i wszystkie węzły na stosie, aby umożliwić mi efektywne sprawdzenie, czy węzeł jest już częścią bieżącej ścieżki. Jeśli zdarzy się, że Twój język ma strukturę danych „uporządkowanego zestawu”, która zapewnia zarówno wydajne operacje push / pop podobne do stosu, jak i wydajne zapytania członkostwa, możesz użyć tego dla stosu węzłów i pozbyć się oddzielnego visitedzestawu.

Alternatywnie, jeśli używasz niestandardowej mutowalnej klasy / struktury dla swoich węzłów, możesz po prostu przechowywać flagę logiczną w każdym węźle, aby wskazać, czy został odwiedzony jako część bieżącej ścieżki wyszukiwania. Oczywiście ta metoda nie pozwoli ci przeprowadzić równolegle dwóch wyszukiwań na tym samym wykresie, jeśli z jakiegoś powodu chcesz to zrobić.

Oto kod testowy demonstrujący działanie funkcji podanej powyżej:

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

Uruchomienie tego kodu na podanym przykładowym wykresie daje następujące dane wyjściowe:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

Zauważ, że chociaż ten przykładowy graf jest nieukierunkowany (tj. Wszystkie jego krawędzie idą w obie strony), algorytm działa również dla dowolnie ukierunkowanych grafów. Na przykład usunięcie C -> Bkrawędzi (przez usunięcie Bz listy sąsiadów C) daje takie same wyniki, z wyjątkiem trzeciej ścieżki ( A -> C -> B -> D), która nie jest już możliwa.


Ps. Łatwo jest skonstruować wykresy, dla których proste algorytmy wyszukiwania, takie jak ten (i inne podane w tym wątku), działają bardzo słabo.

Na przykład rozważmy zadanie znalezienia wszystkich ścieżek od A do B na grafie niekierowanym, gdzie węzeł początkowy A ma dwóch sąsiadów: węzeł docelowy B (który nie ma innych sąsiadów niż A) i węzeł C będący częścią kliki. z n +1 węzłów, na przykład:

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

Łatwo zauważyć, że jedyna ścieżka między A i B jest bezpośrednia, ale naiwny DFS uruchomiony z węzła A zmarnuje O ( n !) Czas bezużytecznie eksplorując ścieżki wewnątrz kliki, mimo że jest oczywiste (dla człowieka), że żadna z tych ścieżek nie może prowadzić do B.

Można również konstruować DAG o podobnych właściwościach, np. Poprzez połączenie węzła początkowego A węzła docelowego B i dwóch innych węzłów C 1 i C 2 , z których oba łączą się z węzłami D 1 i D 2 , z których oba łączą się z E 1 i E 2 i tak dalej. Dla n warstw węzłów ułożonych w ten sposób naiwne poszukiwanie wszystkich ścieżek od A do B zakończy się marnowaniem O (2 n ) czasu na zbadanie wszystkich możliwych ślepych uliczek, zanim się poddaje.

Oczywiście dodanie krawędzi do węzła docelowego B z jednym z węzłów w klika (inne niż C) lub od ostatniej warstwy DAG, by utworzyć wykładniczo dużą liczbę możliwych ścieżek z A do B, a czysto lokalny algorytm wyszukiwania nie jest w stanie z góry powiedzieć, czy znajdzie taką krawędź, czy nie. Zatem w pewnym sensie niska wrażliwość wyników takich naiwnych wyszukiwań wynika z braku świadomości globalnej struktury wykresu.

Chociaż istnieją różne metody przetwarzania wstępnego (takie jak iteracyjne eliminowanie węzłów liści, wyszukiwanie separatorów wierzchołków pojedynczych węzłów itp.), Których można by użyć do uniknięcia niektórych z tych „ślepych zaułków w czasie wykładniczym”, nie znam żadnych ogólnych sztuczka z przetwarzaniem wstępnym, która może je wyeliminować we wszystkich przypadkach. Ogólnym rozwiązaniem byłoby sprawdzenie na każdym etapie wyszukiwania, czy węzeł docelowy jest nadal osiągalny (za pomocą wyszukiwania podrzędnego) i cofnięcie się wcześniej, jeśli tak nie jest - ale niestety, to znacznie spowolniłoby wyszukiwanie (w najgorszym przypadku proporcjonalnie do wielkości wykresu) dla wielu wykresów, które nie zawierają takich patologicznych ślepych zaułków.

Ilmari Karonen
źródło
1
Właśnie tego szukam, dziękuję :)
arslan
Dziękujemy za nierekurencyjne rozwiązanie DFS. Zwróć uwagę, że ostatnia linia wypisywania wyniku zawiera błąd składni, a powinien być for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path)), printbrak nawiasu.
David Oliván Ubieto
1
@ DavidOlivánUbieto: To kod Pythona 2, dlatego nie ma nawiasów. :)
Ilmari Karonen
5

Oto logicznie lepiej wyglądająca wersja rekurencyjna w porównaniu z drugim piętrem.

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }   
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {        
    if (currentNode.equals(END)) { 
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);    
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

Wyjście programu

B A C E 

B A C F E 

B E

B F C E

B F E 
Haibin Liu
źródło
4

Rozwiązanie w kodzie C. Opiera się na systemie plików DFS, który wykorzystuje minimalną ilość pamięci.

#include <stdio.h>
#include <stdbool.h>

#define maxN    20  

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{   
    int sp;
    char    node[maxN];
};   

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;   
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}    

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;    

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =       
    {
        {'b', 'a'}, 
        {'b', 'e'}, 
        {'b', 'd'}, 
        {'f', 'b'}, 
        {'a', 'c'},
        {'c', 'f'}, 
        {'c', 'e'},
        {'f', 'e'},               
    };

char    srcNode = 'b', dstN = 'e';      

int reachTime;  

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN) 
        {
            continue;   
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;   
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;   
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);  

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}
Leon Chang
źródło
2

To może być późno, ale oto ta sama wersja C # algorytmu DFS w Javie z Casey do przechodzenia dla wszystkich ścieżek między dwoma węzłami przy użyciu stosu. Czytelność jest lepsza w przypadku rekurencji, jak zawsze.

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }
Oto przykładowy wykres do przetestowania:

    // Przykładowy wykres. Liczby to identyfikatory krawędzi
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------
batta
źródło
1
doskonale - o tym, jak zastąpiłeś rekurencję iteracją opartą na stosie.
Siddhartha Ghosh
Nadal tego nie rozumiem, co to jest neighbours.Reverse()? Czy to jest List<T>.Reverse ?
Sprawdziłem tę nierekurencyjną wersję, ale wygląda na to, że nie jest poprawna. wersja rekurencyjna jest w porządku. może po zmianie na nierekurencyjną,
pojawił
@alim: Zgoda, ten kod jest po prostu uszkodzony. (Nie usuwa poprawnie węzłów z odwiedzanego zestawu podczas cofania, a obsługa stosu również wydaje się być zepsuta. Próbowałem sprawdzić, czy można to naprawić, ale w zasadzie wymagałoby to całkowitego przepisania). dodał odpowiedź z poprawnym, działającym rozwiązaniem nierekurencyjnym (w Pythonie, ale powinno być stosunkowo łatwe do przeniesienia na inne języki).
Ilmari Karonen,
@llmari Karonen, Nice, mam zamiar sprawdzić, świetna robota.
arslan
1

Podobny problem rozwiązałem ostatnio, zamiast wszystkich rozwiązań interesowało mnie tylko najkrótsze.

Użyłem wyszukiwania iteracyjnego „najpierw wszerz”, które wykorzystywało kolejkę statusu ”, z których każdy zawierał rekord zawierający bieżący punkt na wykresie i ścieżkę prowadzącą do niego.

zaczynasz od pojedynczego rekordu w kolejce, który ma węzeł początkowy i pustą ścieżkę.

Każda iteracja po kodzie zdejmuje pozycję z nagłówka listy i sprawdza, czy jest to rozwiązanie (otrzymany węzeł to ten, który chcesz, jeśli tak, to skończymy), w przeciwnym razie konstruuje nowy element kolejki z węzłami łączącymi się z bieżącym węzłem i zmienione ścieżki oparte na ścieżce poprzedniego węzła, z nowym skokiem dołączonym na końcu.

Teraz możesz użyć czegoś podobnego, ale kiedy znajdziesz rozwiązanie, zamiast się zatrzymywać, dodaj to rozwiązanie do swojej „listy znalezionych” i kontynuuj.

Musisz śledzić listę odwiedzonych węzłów, aby nigdy nie cofać się do siebie, w przeciwnym razie masz nieskończoną pętlę.

jeśli chcesz trochę więcej pseudokodu, napisz komentarz lub coś, a ja rozwinę.


źródło
6
Myślę, że jeśli interesuje Cię tylko najkrótsza ścieżka, to Algorytm Dijkstry jest „rozwiązaniem” :).
vicatcu
1

Myślę, że powinieneś opisać swój prawdziwy problem, który za tym stoi. Mówię to, ponieważ prosisz o coś efektywnego czasowo, ale odpowiedź na problem wydaje się rosnąć wykładniczo!

Dlatego nie spodziewałbym się lepszego algorytmu niż czegoś wykładniczego.

Wycofywałbym się i przeglądał cały wykres. Aby uniknąć cykli, po drodze zapisuj wszystkie odwiedzane węzły. Kiedy wrócisz, odznacz węzeł.

Korzystanie z rekursji:

static bool[] visited;//all false
Stack<int> currentway; initialize empty

function findnodes(int nextnode)
{
if (nextnode==destnode)
{
  print currentway 
  return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
  findnodes(n);
visited[nextnode]=false; 
pop from currenteay
}

Czy to źle?

edit: Aha, i zapomniałem: Powinieneś wyeliminować wywołania rekurencyjne, wykorzystując ten stos węzłów

Jason Plank
źródło
Mój prawdziwy problem jest dokładnie taki, jak opisałem, tylko ze znacznie większymi zestawami. Zgadzam się, że wydaje się, że rośnie wykładniczo wraz z rozmiarem zestawu.
Robert Groves
1

Podstawową zasadą jest to, że nie musisz martwić się o wykresy - jest to standardowy problem znany jako problem z łącznością dynamiczną. Istnieją następujące typy metod, z których można uzyskać węzły są połączone lub nie:

  1. Szybkie wyszukiwanie
  2. Szybka Unia
  3. Ulepszony algorytm (połączenie obu)

Oto kod C, który próbowałem z minimalną złożonością czasową O (log * n) Oznacza to, że dla 65536 listy krawędzi wymaga 4 wyszukiwań, a dla 2 ^ 65536 wymaga 5 wyszukiwań. Udostępniam swoją implementację z algorytmu: Algorithm Course z Uniwersytetu Princeton

WSKAZÓWKA: Możesz znaleźć rozwiązanie Java z linku udostępnionego powyżej z odpowiednimi wyjaśnieniami.

/* Checking Connection Between Two Edges */

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

/*
  Data structure used

vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/

/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);

int main() //Main Function
{ 
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;


printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
    printf("File does not exist");
    exit(1);
}
while (1)
{
    if (first == 0) //getting no. of vertices
    {
        ch = getc(fp);
        if (temp == 0)
        {
            fseek(fp, -1, 1);
            fscanf(fp, "%s", &ch1);
            fseek(fp, 1, 1);
            temp = 1;
        }
        if (isdigit(ch))
        {
            size = atoi(ch1);
            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size  
            sz = (int*) malloc(size * sizeof(int));
            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]
        }
        if (ch == '\n')
        {
            first = 1;
            temp = 0;
        }
    }
    else
    {
        ch = fgetc(fp);
        if (isdigit(ch))
            temp = temp * 10 + (ch - 48);   //calculating value from ch
        else
        {
            /* Validating the file  */

            if (ch != ',' && ch != '\n' && ch != EOF)
            {
                printf("\n\nUnkwown Character Detected.. Exiting..!");

                exit(1);
            }
            if (ch == ',')
                node1 = temp;
            else
            {
                node2 = temp;
                printf("\n\n%d\t%d", node1, node2);
                if (node1 > node2)
                {
                    temp = node1;
                    node1 = node2;
                    node2 = temp;
                }

                /* Adding the input nodes */

                if (!connected(vertex, node1, node2))
                    add(vertex, sz, node1, node2);
            }
            temp = 0;
        }

        if (ch == EOF)
        {
            fclose(fp);
            break;
        }
    }
}

do
{
    printf("\n\n==== check if connected ===");
    printf("\nEnter First Vertex:");
    scanf("%d", &node1);
    printf("\nEnter Second Vertex:");
    scanf("%d", &node2);

    /* Validating The Input */

    if( node1 > size || node2 > size )
    {
        printf("\n\n Invalid Node Value..");
        break;
    }

    /* Checking the connectivity of nodes */

    if (connected(vertex, node1, node2))
        printf("Vertex %d and %d are Connected..!", node1, node2);
    else
        printf("Vertex %d and %d are Not Connected..!", node1, node2);


    printf("\n 0/1:  ");

    scanf("%d", &temp);

} while (temp != 0);

free((void*) vertex);
free((void*) sz);


return 0;
}

void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
    vertex[i] = i;
    sz[i] = 0;
}
}
int root(int *vertex, int i)    //obtaining the root
{
while (i != vertex[i])
{
    vertex[i] = vertex[vertex[i]];
    i = vertex[i];
}
return i;
}

/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);

/* Adding small subtree in large subtree  */

if (sz[i] < sz[j])
{
    vertex[i] = j;
    sz[j] += sz[i];
}
else
{
    vertex[j] = i;
    sz[i] += sz[j];
}

}

/* Time Complexity for Search -->lg* n */

int connected(int *vertex, int p, int q) //Checking of  connectivity of nodes
{
/* Checking if root is same  */

if (root(vertex, p) == root(vertex, q))
    return 1;

return 0;
}
Avinash
źródło
Wydaje się, że nie rozwiązuje to problemu. OP chce znaleźć wszystkie proste ścieżki między dwoma węzłami, a nie tylko sprawdzić, czy ścieżka istnieje.
Ilmari Karonen,
1

znajdź_ścieżki [s, t, d, k]

To pytanie jest stare i już na nie odpowiedział. Jednak żaden nie pokazuje być może bardziej elastycznego algorytmu do osiągnięcia tego samego. Więc wrzucę kapelusz do ringu.

Osobiście find_paths[s, t, d, k]przydaje mi się algorytm postaci , gdzie:

  • s jest węzłem początkowym
  • t jest węzłem docelowym
  • d to maksymalna głębokość wyszukiwania
  • k to liczba ścieżek do znalezienia

Korzystanie z nieskończoności w języku programowania dla dik zapewni Ci wszystkie ścieżki§.

§ oczywiście jeśli używasz skierowanego wykresu i chcesz, aby wszystko było nieukierunkowane ścieżki pomiędzys i ttrzeba będzie uruchomić to w obie strony:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

Funkcja pomocnika

Osobiście lubię rekurencję, chociaż czasami może to być trudne, w każdym razie najpierw zdefiniujmy naszą funkcję pomocniczą:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Główna funkcja

Z tego powodu podstawowa funkcja jest trywialna:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

Najpierw zwróćmy uwagę na kilka rzeczy:

  • powyższy pseudokod to mash-up języków - ale najbardziej przypominający Pythona (ponieważ właśnie w nim kodowałem). Ścisłe kopiowanie i wklejanie nie będzie działać.
  • [] jest listą niezainicjowaną, zamień ją na odpowiednik dla wybranego języka programowania
  • paths_found jest omijany odniesienie . Jest jasne, że funkcja rekurencyjna nic nie zwraca. Zajmij się tym odpowiednio.
  • tutaj graphprzyjmuje jakąś formę hashedstruktury. Istnieje wiele sposobów implementacji wykresu. Tak czy inaczej, graph[vertex]wyświetla listę sąsiednich wierzchołków w a skierowanym wykresie - odpowiednio dostosuj.
  • przy założeniu, że zostały wstępnie przetworzone, aby usunąć „sprzączki” (pętle własne), cykle i wielokrotne krawędzie
SumNeuron
źródło
0

Oto myśl z góry mojej głowy:

  1. Znajdź jedno połączenie. (Przeszukiwanie w głąb jest prawdopodobnie dobrym algorytmem do tego celu, ponieważ długość ścieżki nie ma znaczenia).
  2. Wyłącz ostatni segment.
  3. Spróbuj znaleźć inne połączenie z ostatniego węzła przed poprzednio wyłączonym połączeniem.
  4. Idź do 2, aż nie będzie więcej połączeń.
Ryan Fox
źródło
Ogólnie to nie zadziała: jest całkiem możliwe, że dwie lub więcej ścieżek między wierzchołkami ma tę samą ostatnią krawędź. Twoja metoda mogłaby znaleźć tylko jedną z takich ścieżek.
Ilmari Karonen,
0

O ile wiem, rozwiązania podane przez Ryana Foxa ( 58343 , Christiana ( 58444 ) i Ciebie ( 58461 )) są prawie tak dobre, jak to tylko możliwe. nie wszystkie ścieżki. Na przykład z krawędziami(A,B) , (A,C), (B,C), (B,D)a (C,D)dostaniesz ścieżki ABDi ACD, ale nie ABCD.

mweerden
źródło
mweerden, Przejście wszerz wszerz, które przedstawiłem, znajdzie WSZYSTKIE ścieżki, unikając jednocześnie cykli. W przypadku określonego wykresu implementacja poprawnie znajduje wszystkie trzy ścieżki.
Casey Watson
Nie przeczytałem do końca twojego kodu i założyłem, że korzystałeś z przejścia wszerz (ponieważ tak powiedziałeś). Jednak po bliższej analizie po Twoim komentarzu zauważyłem, że w rzeczywistości tak nie jest. W rzeczywistości jest to niezapomniana wędrówka w głąb, taka jak Ryan, Christian i Robert.
mweerden
0

Znalazłem sposób na wyliczenie wszystkich ścieżek, w tym nieskończonych zawierających pętle.

http://blog.vjeux.com/2009/project/project-shortest-path.html

Znajdowanie ścieżek i cykli atomowych

Definition

Chcemy znaleźć wszystkie możliwe ścieżki prowadzące z punktu A do punktu B. Ponieważ w grę wchodzą cykle, nie można po prostu przejść i wyliczyć ich wszystkich. Zamiast tego będziesz musiał znaleźć ścieżkę atomową, która nie zapętla się i jak najmniejsze możliwe cykle (nie chcesz, aby cykl się powtarzał).

Pierwsza definicja ścieżki atomowej, którą przyjąłem, to ścieżka, która nie przechodzi dwukrotnie przez ten sam węzeł. Jednak okazało się, że nie wykorzystuje wszystkich możliwości. Po chwili zastanowienia doszedłem do wniosku, że węzły nie są ważne, ale krawędzie są! Tak więc ścieżka atomowa to ścieżka, która nie przechodzi dwukrotnie przez tę samą krawędź.

Ta definicja jest przydatna, działa również dla cykli: atomowy cykl punktu A to atomowa ścieżka, która biegnie od punktu A i kończy się do punktu A.

Realizacja

Atomic Paths A -> B

Aby uzyskać całą ścieżkę zaczynającą się od punktu A, będziemy rekurencyjnie przechodzić przez wykres od punktu A.Podczas przechodzenia przez dziecko utworzymy link child -> parent, aby poznać wszystkie krawędzie, które już przekroczyłem. Zanim przejdziemy do tego dziecka, musimy przejść przez tę połączoną listę i upewnić się, że określona krawędź nie została już przejęta.

Kiedy dotrzemy do punktu docelowego, możemy zapisać znalezioną ścieżkę.

Freeing the list

Problem pojawia się, gdy chcesz zwolnić połączoną listę. Zasadniczo jest to drzewo połączone łańcuchem w odwrotnej kolejności. Rozwiązaniem byłoby podwójne połączenie tej listy i po znalezieniu wszystkich atomowych ścieżek uwolnienie drzewa od punktu początkowego.

Ale sprytnym rozwiązaniem jest użycie liczenia referencji (zainspirowane Garbage Collection). Za każdym razem, gdy dodajesz łącze do rodzica, dodajesz jeden do jego liczby odwołań. Następnie, gdy dojdziesz do końca ścieżki, cofasz się i jesteś wolny, podczas gdy liczba odniesień wynosi 1. Jeśli jest wyższa, po prostu usuwasz jedną i zatrzymujesz się.

Atomic Cycle A

Szukanie atomowego cyklu A jest tym samym, co szukanie atomowej ścieżki od A do A. Jest jednak kilka optymalizacji, które możemy zrobić. Po pierwsze, kiedy docieramy do punktu docelowego, chcemy zapisać ścieżkę tylko wtedy, gdy suma kosztów krawędzi jest ujemna: chcemy tylko przejść przez cykle absorpcyjne.

Jak widzieliście wcześniej, podczas poszukiwania atomowej ścieżki przechodzi się przez cały wykres. Zamiast tego możemy ograniczyć obszar wyszukiwania do silnie połączonego komponentu zawierającego A. Znalezienie tych komponentów wymaga prostego przejścia grafu za pomocą algorytmu Tarjana.

Łączenie ścieżek i cykli atomowych

W tym momencie mamy wszystkie ścieżki atomowe, które biegną od A do B i wszystkie cykle atomowe każdego węzła, które zostały nam pozostawione do zorganizowania wszystkiego, aby uzyskać najkrótszą ścieżkę. Od teraz będziemy się uczyć, jak znaleźć najlepszą kombinację cykli atomowych na ścieżce atomowej.

Vjeux
źródło
To nie wydaje się odpowiadać na zadane pytanie.
Ilmari Karonen,
0

Jak umiejętnie opisali niektórzy z innych plakatów, problem w skrócie polega na wykorzystaniu algorytmu przeszukiwania w głąb do rekurencyjnego przeszukiwania grafu pod kątem wszystkich kombinacji ścieżek między komunikującymi się węzłami końcowymi.

Sam algorytm rozpoczyna się od węzła początkowego, który mu podasz, bada wszystkie jego linki wychodzące i postępuje, rozszerzając pierwszy węzeł potomny drzewa wyszukiwania, które się pojawi, przeszukując coraz głębiej, aż do znalezienia węzła docelowego lub do momentu napotkania węzła która nie ma dzieci.

Wyszukiwanie jest następnie cofane, wracając do ostatniego węzła, którego jeszcze nie zakończyło.

Całkiem niedawno pisałem na ten temat na blogu , zamieszczając przykładową implementację C ++ w procesie.

AndyUK
źródło
0

Dodając do odpowiedzi Casey Watson, oto kolejna implementacja Java. Inicjowanie odwiedzonego węzła z węzłem początkowym.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }
Jamshed Katta
źródło