Varoitus
Tämä sivu pysyy täällä historiallisista syistä, ja se saattaa sisältää vanhentunutta tai virheellistä tietoa.
Muutoksen huomiot: 2/22/98, 3/2/98, 12/4/00: Tässä esseen versiossa on korjattu useita virheitä koodissa. 6/10/19:find_shortest_path:n peruuttaminen ”lähes optimaaliseksi”. 8/11/19: Korjaus vahingossa käytetystäfind_graph():stäfind_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
:n sijasta Graafit ovat verkkoja, jotka koostuvat solmuista, joita yhdistävät särmät tai kaaret. Suuntaamattomissa graafeissa solmujen välisillä yhteyksillä on suunta, ja niitä kutsutaan kaariksi; suuntaamattomissa graafeissa yhteyksillä ei ole suuntaa, ja niitä kutsutaan reunoiksi. Keskustelemme pääasiassa suunnatuista graafeista. Graafeihin liittyviä algoritmeja ovat muun muassa polun etsiminen kahden solmun välillä, lyhimmän polun etsiminen kahden solmun välillä, syklien määrittäminen graafissa (sykli on ei-tyhjä polku solmusta itseensä), sellaisen polun etsiminen, joka tavoittaa kaikki solmut (kuuluisa ”kiertävän myyntimiehen ongelma”) ja niin edelleen. Joskus graafin solmuihin tai kaarteisiin liittyy painoja tai kustannuksia, ja olemme kiinnostuneita löytämään halvimman polun.
Graafialgoritmeista on paljon kirjallisuutta, ja ne ovat tärkeä osa diskreettiä matematiikkaa. Graafeilla on myös paljon käytännön käyttöä tietokonealgoritmeissa. Ilmeisiä esimerkkejä löytyy verkkojen hallinnasta, mutta esimerkkejä on runsaasti monilla muillakin aloilla. Esimerkiksi tietokoneohjelman kutsujien ja kutsuttavien väliset suhteet voidaan nähdä graafina (jossa syklit kuvaavat rekursiota ja tavoittamattomat solmut kuollutta koodia).
Harvinaiset ohjelmointikielet tukevat suoraan graafeja tietotyyppinä, eikä Python ole poikkeus. Graafeja on kuitenkin helppo rakentaa listoista ja sanakirjoista. Esimerkiksi tässä on yksinkertainen graafi (en voi käyttää piirroksia näissä sarakkeissa, joten kirjoitan graafin kaaret):
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
Tässä graafissa on kuusi solmua (A-F) ja kahdeksan kaarta. Se voidaan esittää seuraavalla Python-tietorakenteella:
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
Tämä on sanakirja, jonka avaimet ovat graafin solmut. Kunkin avaimen vastaava arvo on lista, joka sisältää solmut, joihin on suora kaari kyseisestä solmusta. Tämä on suunnilleen niin yksinkertaista kuin vain voi olla (vielä yksinkertaisemmin solmut voitaisiin esittää numeroin nimien sijaan, mutta nimet ovat kätevämpiä ja ne voidaan helposti tehdä kantamaan enemmän tietoa, kuten kaupunkien nimiä).
Kirjoitetaan yksinkertainen funktio, jolla määritetään polku kahden solmun välillä. Se ottaa argumentteina graafin sekä alku- ja loppusolmut. Se palauttaa listan solmuista (mukaan lukien alku- ja loppusolmut), jotka muodostavat polun.Jos polkua ei löydy, se palauttaa None. Sama solmu ei esiinny useammin kuin kerran palautetussa polussa (eli se ei sisällä syklejä). Algoritmi käyttää tärkeää tekniikkaa nimeltä backtracking: se kokeilee jokaista mahdollisuutta vuorollaan, kunnes se löytää ratkaisun.
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
Esimerkki ajosta (käyttäen yllä olevaa graafia):
>>> find_path(graph, 'A', 'D') >>>
Toinen ”if”-lause on tarpeellinen vain siinä tapauksessa, että on olemassa solmuja, jotka on merkitty kaarien päätepisteiksi, mutta joilla itsellään ei ole lähteviä kaaria ja joita ei ole merkitty graafiin lainkaan. Tällaiset solmut voisivat myös sisältyä graafiin tyhjällä listalla lähtevistä kaarista, mutta joskus on kätevämpää olla vaatimatta tätä.
Huomaa, että vaikka käyttäjä kutsuu find_path():aa kolmella argumentilla, se kutsuu itseään neljännellä argumentilla: polku, joka on jo kuljettu.Tämän argumentin oletusarvo on tyhjä lista, ”, mikä tarkoittaa, että solmuja ei ole vielä kuljettu. Tätä argumenttia käytetään syklien välttämiseksi (ensimmäinen ’if’ ’for’-silmukan sisällä). Argumenttia ’path’ ei muuteta: osoitus ”path = path + ” luo uuden listan. Jos olisimme sen sijaan kirjoittaneet ”path.append(start)”, olisimme muuttaneet muuttujaa’path’ kutsujassa, mikä olisi johtanut katastrofaalisiin tuloksiin. (Tupleja käyttämällä olisimme voineet olla varmoja, että näin ei tapahtuisi, mutta olisimme joutuneet kirjoittamaan ”path = path + (start,)”, koska ”(start)” ei ole singleton-tuple – se on vain suluissa oleva lauseke.)
Tätä funktiota on helppo muuttaa niin, että se palauttaa listan kaikista poluista (ilman syklejä) ensimmäisen löytämänsä polun sijasta:
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
Näyteajo:
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
Toinen muunnos löytää lyhimmän polun:
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
Näyteajo:
>>> find_shortest_path(graph, 'A', 'D') >>>
Nämä funktiot ovat suunnilleen niin yksinkertaisia kuin olla voi. Silti ne ovat lähesoptimaalisia (Pythonilla kirjoitetulle koodille). Toisessa Python Patterns-kolumnissa yritän analysoida niiden suoritusnopeutta ja parantaa niiden suorituskykyä, vaikka se maksaakin enemmän koodia.
UPDATE: Eryk Kopczyński huomautti, että nämä funktiot eivät ole optimaalisia. Päinvastoin, ”tämä ohjelma toimii eksponentiaalisessa ajassa,kun taas find_shortest_path voidaan tehdä lineaarisessa ajassa käyttämällä BFS:ää . Lisäksi lineaarinen BFS on yksinkertaisempi:”
# 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)
Huomaa, että tämä palauttaa polun oudossa muodossa, esim., 'B'], 'D']. Erityisestilen(find_shortest_path(graph, 'A', 'D'))antaa väärän vastauksen (2, koska ulomman listan pituus on 2). Tämä johtuu siitä, että append tehdään, next]eikädist+. Toinen menetelmä käyttäisi neliöaikaa ja muistia, mutta sen pitäisi silti olla hyvä suhteellisen pienille graafeille;muutoin lista on helppo muuttaa oikeaan muotoon.
Toinen variaatio olisi lisätä enemmän datan abstraktiota: luoda luokka graafien esittämistä varten, jonka metodit toteuttavat eri algoritmit. Vaikka tämä vetoaa strukturoidun ohjelmoinnin haluun, se ei tee koodista yhtään tehokkaampaa (päinvastoin). Se helpottaa kuitenkin erilaisten merkintöjen lisäämistä solmukohtiin tai kaarteisiin ja sellaisten algoritmien lisäämistä, jotka ottavat nämä merkinnät huomioon (esim. lyhimmän reitin löytäminen kahden kaupungin välillä kartalta). Tämäkin on toisen kolumnin aiheena.