Ostrzeżenie
Ta strona pozostaje tu ze względów historycznych i może zawierać nieaktualne lub błędne informacje.
Notatki o zmianach: 2/22/98, 3/2/98, 12/4/00: W tej wersji tego eseju poprawiono kilka błędów w kodzie. 6/10/19: Wycofaniefind_shortest_pathjako „prawie optymalnego”. 8/11/19: Poprawka przypadkowego użyciafind_graph()zamiastfind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Grafy to sieci składające się z węzłów połączonych krawędziami lub łukami. W grafach skierowanych połączenia między węzłami mają kierunek i nazywane są łukami; w grafach nieskierowanych połączenia nie mają kierunku i nazywane są krawędziami. Omawiamy głównie grafy skierowane. Algorytmy w grafach obejmują znajdowanie ścieżki między dwoma węzłami, znajdowanie najkrótszej ścieżki między dwoma węzłami, określanie cykli w grafie (cykl to niepusta ścieżka od węzła do samego siebie), znajdowanie ścieżki, która dociera do wszystkich węzłów (słynny „problem podróżującego komiwojażera”) itd. Czasami węzły lub łuki grafu mają wagi lub koszty z nimi związane, a nas interesuje znalezienie najtańszej ścieżki.
Istnieje spora literatura na temat algorytmów grafowych, które są ważną częścią matematyki dyskretnej. Grafy mają również wiele praktycznych zastosowań w algorytmach komputerowych. Oczywiste przykłady można znaleźć w zarządzaniu sieciami, ale przykłady obfitują w wielu innych dziedzinach. Na przykład, relacje caller-callee w programie komputerowym mogą być postrzegane jako graf (gdzie cykle wskazują na rekurencję, a nieosiągalne węzły reprezentują martwy kod).
Niewiele języków programowania zapewnia bezpośrednie wsparcie dla grafów jako typów danych, a Python nie jest wyjątkiem. Jednak grafy można łatwo zbudować z list i słowników. Na przykład, oto prosty graf (nie mogę używać rysunków w tych kolumnach, więc zapisuję łuki grafu):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Ten graf ma sześć węzłów (A-F) i osiem łuków. Można go przedstawić za pomocą następującej struktury danych Pythona:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Jest to słownik, którego kluczami są węzły grafu. Dla każdego klucza odpowiadająca mu wartość jest listą zawierającą węzły, które są połączone bezpośrednim łukiem z tego węzła. To jest tak proste, jak to tylko możliwe (jeszcze prostsze jest to, że węzły mogłyby być reprezentowane przez liczby zamiast nazw, ale nazwy są wygodniejsze i można je łatwo dostosować do przenoszenia większej ilości informacji, takich jak nazwy miast).
Zapiszmy prostą funkcję do wyznaczania ścieżki między dwoma węzłami. Jako argumenty przyjmuje ona graf oraz węzły początkowy i końcowy. Zwraca listę węzłów (w tym węzły początkowe i końcowe) składających się na ścieżkę.Jeśli nie można znaleźć żadnej ścieżki, zwraca Brak. Ten sam węzeł nie wystąpi więcej niż raz na zwróconej ścieżce (tj. nie będzie ona zawierać cykli). Algorytm używa ważnej techniki zwanej backtracking: próbuje każdej możliwości po kolei, aż znajdzie rozwiązanie.
def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None
Przykładowy przebieg (z użyciem powyższego grafu):
>>> find_path(graph, 'A', 'D') >>>
Druga instrukcja 'if’ jest konieczna tylko w przypadku, gdy istnieją węzły, które są wymienione jako punkty końcowe łuków, ale same nie mają wychodzących łuków i w ogóle nie są wymienione w grafie. Takie węzły mogłyby być również zawarte w grafie, z pustą listą wychodzących łuków, ale czasami wygodniej jest tego nie wymagać.
Zauważ, że chociaż użytkownik wywołuje find_path() z trzema argumentami, to wywołuje on siebie z czwartym argumentem: ścieżką, która już została przemierzona.Domyślną wartością tego argumentu jest pusta lista, ”, co oznacza, że żadne węzły nie zostały jeszcze przemierzone. Argument ten jest używany do unikania cykli (pierwsze 'if’ wewnątrz pętli 'for’). Argument 'ścieżka’ nie jest modyfikowany: przypisanie „ścieżka = ścieżka + ” tworzy nową listę. Gdybyśmy zamiast tego napisali „path.append(start)”, zmodyfikowalibyśmy zmienną 'path’ w wywołującym, z katastrofalnymi rezultatami. (Używając tupli, moglibyśmy być pewni, że tak się nie stanie, kosztem konieczności napisania „path = path + (start,)”, ponieważ „(start)” nie jest tuplem singletonowym — jest to po prostu wyrażenie nawiasowe.)
Prosto jest zmienić tę funkcję, aby zwracała listę wszystkich ścieżek (bez cykli) zamiast pierwszej ścieżki, którą znajdzie:
def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
Próbny przebieg:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Inny wariant znajduje najkrótszą ścieżkę:
def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest
Próbny przebieg:
>>> find_shortest_path(graph, 'A', 'D') >>>
Te funkcje są tak proste, jak tylko się da. Jednak są one prawie optymalne (dla kodu napisanego w Pythonie). W kolejnym felietonie Python Patterns postaram się przeanalizować ich szybkość działania i poprawić ich wydajność, kosztem większej ilości kodu.
UPDATE: Eryk Kopczyński zwrócił uwagę, że te funkcje nie są optymalne. Wręcz przeciwnie, „ten program działa w czasie wykładniczym, podczas gdy find_shortest_path może być wykonany w czasie liniowym przy użyciu BFS . Co więcej, liniowy BFS jest prostszy:”
# Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)
Zauważ, że zwraca on ścieżkę w dziwnym formacie, np., 'B'], 'D']. W szczególności,len(find_shortest_path(graph, 'A', 'D'))da nieprawidłową odpowiedź (2, ponieważ zewnętrzna lista ma długość 2). Dzieje się tak, ponieważ append jest wykonywany jako, next]zamiastdist+. Druga metoda użyłaby quadratictime i pamięci, ale nadal powinna być w porządku dla stosunkowo małych wykresów; w przeciwnym razie łatwo jest przekształcić listę w poprawny format.
Innym wariantem byłoby dodanie więcej abstrakcji danych: utworzenie klasy reprezentującej wykresy, której metody implementują różne algorytmy. Podczas gdy to odwołuje się do pragnienia programowania strukturalnego, nie czyni kodu bardziej wydajnym (wręcz przeciwnie). Ułatwia natomiast dodawanie różnych etykiet do węzłów i łuków oraz dodawanie algorytmów, które biorą te etykiety pod uwagę (np. znajdowanie najkrótszej trasy między dwoma miastami na mapie). To również będzie tematem kolejnego felietonu.