| << 2.1 Sorteerimine | Sisukord | 2.3 Mida edasi õppida? >> |
Tunni läbimisel:
- Tean mis on graaf
- Oskan teisendada kaardiülesannet graafiks
- Tean mis on graafi sügavuti ja laiuti läbimine
- Tean mis on külgnevusjärjend ja kuidas graafi külgnevusjärjendina kirja panna
- Oskan graafi läbida
- Tean kuidas lisada graafile märgendeid
2.3 Graafid
Selleks, et lahendada keerulisemaid probleeme tuleb esmalt välja mõelda, kuidas neid lihtsustada. Üheks selliseks probleemiks on lühima tee leidmise probleem. Nimelt on meil tarvis sõita tundmatus riigis ühest linnast teise, nii et selleks kuluks kõige vähem aega. Et ülesanne oleks natuke lihtsam ütleme, et aeg on võrdne teepikkusega ning meil on olemas ka kaart. Suurepärane, nüüd peame me me ainult otsustama, millistest linnadest me peame läbi sõitma, et jõuda sihtkohta. Kuidas sina seda teeksid?
Tegemist on tegelikult tüüpülesandega, mida võib kasutada väga paljude probleemide lahendamiseks. Teede asemel võivad olla näiteks torud ja kilomeetrite asemel võivad olla hinnad, ning ülesandeks võib olla rajada kõige odavam torustik kahe linna vahele.
Nagu sa ilmselt taipasid, siis niidi abil kaardi peal teepikkuseid mõõta pole arvuti abil kuigi lihtne ülesanne. Küll aga võime öelda, et linnade vahelised teepikkused on kaardi peal kirjas. See aga ei tähenda, et ülesanne triviaalseks muutub, sest kui need linnad asuvad üksteisest veidi kaugemal, peame me ikkagi otsustama, milliseid linnasid meil läbida tuleb.
Selleks, et seda ülesannet algoritmi abil lahendada peame me selle esmalt sobival kujul kirja panema. Kaardi sisse skanneerimine meid hästi ei aita, sest töötlemiseks on vaja juba tehisnägemist, mille algoritmid on oluliselt keerulisemad. Küll aga saame oma ülseande kujutada graafina.
Definitsioon:
Graaf - matemaatiline struktuur, mis koosneb hulkadest V ja E. Hulga V elemente nimetame graafi tippudeks ning hulga E elemente nimetame servadeks. Iga graafi serv on seejuures alati ühendatud täpselt kahe tipuga.
Graafiliselt võib graafi kujutada kui joonistust punktidest, mis on ühendatud omavahel joontega. Punktid vastavad graafi tippudele ja jooned vastavad servadele. Järgneval joonisel on kujutatud üks võimalik graaf, pane tähele, see võib sisaldada ka:
- tsükleid ja
- omavahel ühendamata osasid.
Graafile võib tippudele ja kaartele võib anda ka tähistused. Näiteks tipu keskele võib kirjutada linnade nimed ja kaarte kohale kirjutada nende poolt tähistatavate teede pikkused.
Ülesanne 1
Koosta eesti kaardi suurimaid linnu kujutav graaf. Kui kaks linna on omavahel otse teega ühendatud, siis märgi nende vahele kaar. Kaartele pole vaja nimesid anda, küll aga märgi tippudele linnade nimed. Suuremateks linnadeks võid valida näiteks järgnevad linnad: Tallinn, Rakvere, Jõhvi, Narva, Jõgeva, Paide, Haapsalu, Kärdla, Kuressaare, Pärnu, Tartu, Valga ja Võru (Ülesande lihtsustamiseks pole siin loetletud mitmeid suuremaid Eesti linnu, soovi korral võite lisada oma graafile ka muid meelepäraseid linnu, näiteks oma kodulinna). Siin on pilt Eesti kaardist:
Minu tehtud graaf näeb välja selline:
- Sinu graaf võib välja näha ilusam või hoopis teistsugune, ülesande eesmärk ei olnud geograafia teadmiseid kontrollida, vaid õpetada sind probleeme graafina kujutama.
- Nagu sa näed ei asu minu graafil linnad nende geograafilise koha peal ning see on täiesti OK, graafid ongi selleks, et neid saaks järjestada täpselt nii nagu sulle paremini sobib.
- Kui sinu graafil on Kärdla ja Kuressaare eraldi, siis see on ka OK, minu graafil on meretee samuti tee ;)
Graafide kujutamine arvutis
Enamikes programmeerimiskeeltes, sealhulgas Pythonis, pole sisseehitatud andmetüüpi graafide hoidmiseks. Seevastu saab seda kenasti teha kasutades järjendeid ja sõnastikke. Ühte sellist viisi nimetatakse külgenvusjärjendiks, järgnevalt on toodud näide graafist nind sellele vastavast külgnevusjärjendist.
Külgnevusjärjend koosneb sõnastikust, mis paneb igale graafi tipule vastavusse järjendi teistest graafi tippudest, mis on selle tipuga kaare kaudu ühendatud. Näiteks kui tipu A ja tipu B vahel on kaar, siis asub tipp A tipule B vastavas järjendis, ning vastupidi. Kuna kõik need järjendid asuvad sõnastikus, siis on selle andmestruktuuri abil lihtne leida kõiki tipu naabreid.
Ülesanne 2
Koosta funktsioon, mis saab ette külgnevusjärjendina kujutatud graafi ja ühe tipu ning tagastab kõik selle tipu naabrid. Näiteks tipu A naabriteks on tipud B ja C
- See ülesanne ongi täpselt nii lihtne nagu see tundub. Külgnevusjärjendist tuleb üles otsida õige tipp ning väljastada kõik tipud talle vastavast järjendist.
Graafi läbimine
Kui me tahame näiteks leida oma koostatud graafi põhjal teed Tallinnast Pärnusse, või kontrollida, kas selline tee üldse leidub, siis on meil vaja meetodit selle graafi läbi vaatamiseks. Kaks tuntumat graafide läbivaatamise viisi on:
- Sügavuti läbimine - minnakse kõigepealt esimeses võimalikus suunas nii kaugele kui võimalik, ilma ei peaks juba eelnevalt läbitud tippu uuesti külastama. Kui enam kuhugi edasi minna pole võimalik, siis minnakse tagasi viimase teehargnemise juurde ja proovitakse minna teises suunas.
- Laiuti läbimine - kõigepealt vaadatakse algustippu, siis vaadatakse läbi alguspunkti naabrid. Seejärjel vaadatakse läbi kõik alguspunkti naabrite naabrid jne. Varem läbitud tippe enam uuesti ei külastata.
Ülesanne 3
Koosta algoritm, mis saab ette graafi ning kaks tippu: algustipu ja lõpptipu. Algoritm läbib selle graafi kasutades kas laiuti või sügavuti otsingut ning annab teada, kas algustipust on võimalik lõpptippu liikuda. NB! Kahest pakutud meetodist on sügavuti otsingut lihtsam realiseerida, sest seda saab teha näiteks rekursiooni abil.
- Sügavuti otsinguts peab rekursioon meeles, millises tippus parajasti ollakse ning rekursiooni sammus minnakse kõikidesse veel läbimata tippudesse, kuhu sellest tipust minna saab.
- Selleks, et meeles pidada, millistes tippudes juba käidud on, soovitan rekursiivsesse funktsiooni kaasa panna järjend nendest tippudest. Alguses on see järjend tühi, aga igal rekursiooni sammul lisatakse sinna läbi vaadatud tipp juurde.
- Rekursiooni baasiks on olurkod, kui vaadeldavast tipust enam kuhugi edasi minna ei saa.
Selleks, et lahendada kahe linna vahelise lühima tee leidmise ülesanne on tarvis graafi kaartele lisada teede pikkused. Selleks võid külgnevusjärjendis lisada kõigile tippudele, kuhu lähtetipust saab minna ka teepikkused näiteks niimoodi:
Lühima teepikkuse ülesannet saad lahendada lisaülesandes.
Lisaülesanded
- Kujuta ülesandes 1 koostatud Eesti kaart külgnevusjärjendina.
- Ühte levinud algoritmi kahe linna vahelise lühima tee leidmiseks nimetatakse Dijkstra algoritmiks. Loe selle algoritmi kohta ja proovi seda realiseerida.
- Kui on tarvis vedada torustikku erinevate linnade vahel, siis enamasti ei ole tarvis vedada ainult kahe linna vahel, vaid on tarvis leida selline ühendusviis, mis ühendaks omavahel kõik linnad ning selle jaoks kuluks minimaalselt materjali. Sellise ühenduse leidmiseks kasutatakse |Prim'i algoritmi. Loe selle algoritmi kohta ja proovi seda realiseerida.
Kui tahad veel teada, milliseid algoritme õppida, või kust nende kohta infot leida, siis järgmises osas on toodud erinevaid algoritme, mida võid iseseisvalt proovida.
Mõisted:
- Graaf - matemaatiline struktuur, mis koosneb hulkadest V ja E. Hulga V elemente nimetame graafi tippudeks ning hulga E elemente nimetame servadeks. Iga graafi serv on seejuures alati ühendatud täpselt kahe tipuga.
- Sügavuti läbimine - minnakse kõigepealt esimeses võimalikus suunas nii kaugele kui võimalik, ilma ei peaks juba eelnevalt läbitud tippu uuesti külastama. Kui enam kuhugi edasi minna pole võimalik, siis minnakse tagasi viimase teehargnemise juurde ja proovitakse minna teises suunas.
- Laiuti läbimine - kõigepealt vaadatakse algustippu, siis vaadatakse läbi alguspunkti naabrid. Seejärjel vaadatakse läbi kõik alguspunkti naabrite naabrid jne. Varem läbitud tippe enam uuesti ei külastata.
Viited:
| << 2.1 Sorteerimine | Sisukord | 2.3 Mida edasi õppida? >> |