Jak prześledzić ścieżkę w przeszukiwaniu wszerz?

104

Jak prześledzić ścieżkę przeszukiwania wszerz, tak jak w poniższym przykładzie:

Jeśli szukasz klucza 11, zwróć najkrótszą listę łączącą od 1 do 11.

[1, 4, 7, 11]
python  algorithm  graph  breadth-first-search 
— Christopher Markieta
źródło
6
Właściwie było to stare zadanie, w którym pomagałem przyjacielowi kilka miesięcy temu, oparte na prawie Kevina Bacona. Moje ostateczne rozwiązanie było bardzo niechlujne, w zasadzie wykonałem kolejne przeszukiwanie wszerz, aby „przewinąć” i cofnąć. Nie chcę znaleźć lepszego rozwiązania.
— Christopher Markieta,
21
Doskonały. Rozważam powrót do starego problemu, aby znaleźć lepszą odpowiedź, która byłaby godną podziwu cechą inżyniera. Życzę powodzenia w nauce i karierze.
— Peter Rowell
1
Dzięki za pochwałę, po prostu wierzę, że jeśli się tego teraz nie nauczę, znów będę miał ten sam problem.
— Christopher Markieta,
— nbro

Odpowiedzi:

195

Najpierw powinieneś spojrzeć na http://en.wikipedia.org/wiki/Breadth-first_search .

Poniżej znajduje się szybka realizacja, w której użyłem listy do reprezentowania kolejki ścieżek.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

Innym podejściem byłoby zachowanie odwzorowania z każdego węzła na jego rodzica, a podczas inspekcji sąsiedniego węzła, zarejestrowanie jego rodzica. Po zakończeniu wyszukiwania po prostu prześledź wstecz zgodnie z mapowaniem nadrzędnym.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

Powyższe kody są oparte na założeniu, że nie ma cykli.

— qiao
źródło
2
To jest wspaniałe! Mój proces myślowy doprowadził mnie do uwierzenia w tworzenie pewnego rodzaju tabeli lub macierzy, nie nauczyłem się jeszcze o wykresach. Dziękuję Ci.
— Christopher Markieta,
Próbowałem również użyć metody śledzenia wstecznego, chociaż wydaje się to znacznie czystsze. Czy byłoby możliwe zrobienie wykresu, gdybyś wiedział tylko początek i koniec, ale nie znasz żadnego węzła pomiędzy nimi? A może nawet inne podejście poza wykresami?
— Christopher Markieta,
1
Czy można tak dostosować pierwszy algorytm, aby zwracał wszystkie ścieżki od 1 do 11 (zakładając, że jest ich więcej niż jedna)?
— Maria Ines Parnisari
1
@ l19 Gdy znajdziesz ścieżkę ( node==end), dodaj ją do innej listy, która będzie zawierać wszystkie znalezione ścieżki, a następnie continuezamiast return. Jeśli używasz odwiedzanego zestawu, aby zapobiec cyklom, nie dodawaj nigdy węzła końcowego do odwiedzanego zestawu (w przeciwnym razie tylko jedna ścieżka może mieć ten węzeł końcowy).
— Dominic K
1
Zaleca się używanie collections.deque zamiast listy. list.pop (0) ma złożoność O (n), podczas gdy deque.popleft () to O (1)
— Omar_0x80
23

Bardzo podobała mi się pierwsza odpowiedź qiao! Jedyne, czego tu brakuje, to oznaczyć wierzchołki jako odwiedzone.

Dlaczego musimy to zrobić?
Wyobraźmy sobie, że jest inny węzeł numer 13 połączony z węzłem 11. Teraz naszym celem jest znalezienie węzła 13.
Po krótkim uruchomieniu kolejka będzie wyglądać następująco:

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

Zauważ, że istnieją DWIE ścieżki z numerem węzła 10 na końcu.
Co oznacza, że ​​ścieżki z węzła numer 10 zostaną sprawdzone dwukrotnie. W tym przypadku nie wygląda to tak źle, ponieważ węzeł numer 10 nie ma żadnych dzieci .. Ale może być naprawdę zły (nawet tutaj sprawdzimy ten węzeł dwa razy bez powodu ..)
Węzeł numer 13 nie jest w te ścieżki, aby program nie powrócił przed dotarciem do drugiej ścieżki z węzłem numer 10 na końcu .. i sprawdzimy to ponownie ..

Brakuje nam tylko zestawu do oznaczania odwiedzanych węzłów i nie sprawdzania ich ponownie.
Oto kod qiao po modyfikacji:

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

Wynik programu będzie:

[1, 4, 7, 11, 13]

Bez zbędnych ponownych sprawdzeń.

— Albo Kazaz
źródło
6
Może to być przydatne do wykorzystania collections.dequedla queuejak list.pop (0) ponieść O(n)ruchów pamięci. Ponadto, ze względu na potomność, jeśli chcesz wykonać DFS, po prostu ustaw path = queue.pop()w którym przypadku zmienna queuefaktycznie zachowuje się jak a stack.
— Sudhi
11

Bardzo łatwy kod. Ciągle dołączasz ścieżkę za każdym razem, gdy odkryjesz węzeł.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))
— SeasonalShot
źródło
2
Uważam, że twój kod jest bardzo czytelny w porównaniu z innymi odpowiedziami. Dziękuję Ci bardzo!
— Mitko Rusev
8

Pomyślałem, że spróbuję to zakodować dla zabawy:

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

Jeśli chcesz cykli, możesz dodać to:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]
— Robert King
źródło
po zbudowaniu next_for_front. Kolejne pytanie, co jeśli wykres zawiera pętle? Np. Jeśli węzeł 1 miałby krawędź łączącą się z powrotem ze sobą? Co się stanie, jeśli wykres ma wiele krawędzi przechodzących między dwoma węzłami?
— robert king
1

Podoba mi się zarówno pierwsza odpowiedź @Qiao, jak i dodatek @ Or. Ze względu na nieco mniej przetwarzania chciałbym dodać do odpowiedzi Ora.

W odpowiedzi @ Or, śledzenie odwiedzonego węzła jest świetne. Możemy także zezwolić programowi na wcześniejsze zakończenie pracy niż obecnie. W pewnym momencie pętli for current_neighbourbędzie musiało być end, a kiedy to nastąpi, zostanie znaleziona najkrótsza ścieżka i program może powrócić.

Zmodyfikowałbym metodę w następujący sposób, zwróć szczególną uwagę na pętlę for

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

Wynik i wszystko inne będzie takie samo. Jednak przetworzenie kodu zajmie mniej czasu. Jest to szczególnie przydatne na większych wykresach. Mam nadzieję, że to pomoże komuś w przyszłości.

— Darie Dorlus
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.