Varning
Denna sida finns här av historiska skäl och kan innehålla föråldrad eller felaktig information.
Ändringsanmärkningar: Denna version av uppsatsen rättar till flera fel i koden. 19/6/19: Tillbakadragande avfind_shortest_pathsom ”nästan optimal”. 8/11/19: Korrigerar oavsiktlig användning avfind_graph()istället förfind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
Grafer är nätverk som består av noder som är sammankopplade med kanter eller bågar. I indirekta grafer har förbindelserna mellan noder en riktning och kallas bågar; i oriktade grafer har förbindelserna ingen riktning och kallas kanter. Vi diskuterar främst riktade grafer. Algoritmer i grafer omfattar att hitta en väg mellan två noder, att hitta den kortaste vägen mellan två noder, att bestämma cykler i grafen (en cykel är en icke-tom väg från en nod till sig själv), att hitta en väg som når alla noder (det berömda ”traveling salesman-problemet”), och så vidare. Ibland har noderna eller bågarna i grafen vikter eller kostnader förknippade med dem, och vi är intresserade av att hitta den billigaste vägen.
Det finns en omfattande litteratur om algoritmer för grafer, som är en viktig del av den diskreta matematiken. Grafer har också mycket praktisk användning i datoralgoritmer. Tydliga exempel finns inom förvaltningen av nätverk, men det finns många exempel inom många andra områden. Till exempel kan förhållandet mellan anropare och mottagare i ett datorprogram ses som en graf (där cykler indikerar rekursion och oåtkomliga noder representerar dödkod).
Få programmeringsspråk ger direkt stöd för grafer som datatyp, och Python är inget undantag. Grafer kan dock lätt byggas upp av listor och ordlistor. Här är till exempel en enkel graf (jag kan inte använda ritningar i dessa kolumner, så jag skriver ner grafens bågar):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Denna graf har sex noder (A-F) och åtta bågar. Den kan representeras av följande Python-datastruktur:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Detta är en ordbok vars nycklar är noderna i grafen. För varje nyckel är motsvarande värde en lista som innehåller de noder som är anslutna med en direkt båge från denna nod. Detta är ungefär så enkelt som det kan bli (ännu enklare skulle noderna kunna representeras av siffror i stället för namn, men namn är bekvämare och kan lätt göras så att de kan innehålla mer information, t.ex. stadsnamn).
Låt oss skriva en enkel funktion för att bestämma en väg mellan två noder. Den tar en graf och start- och slutnoderna som argument. Den returnerar en lista över noder (inklusive start- och slutnoderna) som utgör stigen.Om ingen stig kan hittas returnerar den None. Samma nod får inte förekomma mer än en gång på den återgivna vägen (dvs. den får inte innehålla cykler). Algoritmen använder en viktig teknik som kallas backtracking: den prövar varje möjlighet i tur och ordning tills den hittar en lösning.
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
Ett exempel på körning (med grafen ovan):
>>> find_path(graph, 'A', 'D') >>>
Den andra ”if”-angivelsen är nödvändig endast för det fall att det finns noder som är listade som slutpunkter för bågar, men som inte har utgående bågar själva, och som inte är listade i grafen överhuvudtaget. Sådana noder kan också finnas med i grafen, med en tom lista över utgående bågar, men ibland är det bekvämare att inte kräva detta.
Bemärk att medan användaren anropar find_path() med tre argument, anropar den sig själv med ett fjärde argument: den sökväg som redan har genomkorsats.Standardvärdet för detta argument är den tomma listan ”, vilket betyder att inga noder har genomkorsats ännu. Detta argument används för att undvika cykler (det första ”if” i ”for”-slingan). Argumentet ’path’ ändras inte: tilldelningen ”path = path + ” skapar en ny lista. Om vi hade skrivit ”path.append(start)” i stället skulle vi ha ändrat variabeln ”path” i anroparen, med katastrofala följder. (Genom att använda tupler kunde vi ha varit säkra på att detta inte skulle hända, till priset av att vi måste skriva ”path = path + (start,)” eftersom ”(start)” inte är en singleton tupel – det är bara ett parentesuttryck.)
Det är enkelt att ändra den här funktionen så att den returnerar en lista med alla sökvägar (utan cykler) istället för den första sökvägen som hittas:
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
En provkörning:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
En annan variant hittar den kortaste sökvägen:
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
Provkörning:
>>> find_shortest_path(graph, 'A', 'D') >>>
De här funktionerna är ungefär så enkla som de kan bli. Ändå är de nästan optimala (för kod skriven i Python). I en annan Python Pattern-krönika kommer jag att försöka analysera deras körhastighet och förbättra deras prestanda, till priset av mer kod.
UPPDATERING: Eryk Kopczyński påpekade att dessa funktioner inte är optimala. Tvärtom: ”Detta program körs på exponentiell tid, medan find_shortest_path kan göras på linjär tid med hjälp av BFS . Dessutom är en linjär BFS enklare:”
# 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)
Notera att detta returnerar sökvägen i ett konstigt format, t.ex., 'B'], 'D']. Särskiltlen(find_shortest_path(graph, 'A', 'D'))ger det felaktiga svaret (2, eftersom den yttre listan har längden 2). Detta beror på att append görs som, next]i stället fördist+. Den andra metoden skulle använda kvadratisk tid och minne, men bör ändå vara bra för relativt små grafer; annars är det lätt att omvandla listan till rätt format.
En annan variant skulle vara att lägga till mer dataabstraktion: skapa en klass som representerar grafer, vars metoder implementerar de olika algoritmerna. Även om detta tilltalar önskan om strukturerad programmering gör det inte koden mer effektiv (tvärtom). Det gör det dock lättare att lägga till olika etiketter till noderna eller bågarna och att lägga till algoritmer som tar hänsyn till dessa etiketter (t.ex. för att hitta den kortaste vägen mellan två städer på en karta). Detta kommer också att bli föremål för en annan kolumn.