Materjalid koostas ja kursuse viib läbi
Tartu Ülikooli arvutiteaduse instituudi programmeerimise õpetamise töörühm
| < eelmine | 8. OSA sisukord | järgmine > |
8.3 Silmaring. Navigeerimine
NAVIGEERIMINE
Sõna navigeerimine tuleb ladina keelest, kus navis tähendab laeva ning agere tähendab juhtimist. (Allikas: https://www.britannica.com/technology/navigation-technology)
Nii vanasti kui ka nüüd peetakse navigeerimise all silmas sõiduki juhtimist kasutades navigatsioonivahendeid - vahendeid, mis aitavad määrata asukohta ja kurssi. Tänapäevased vahendid püüavad endisaegsetest rohkem abi pakkuda. Näiteks võivad nad pakkuda (mingis mõttes) sobivaimat marsruuti.
Nii mõnedki meist harjunud autoga sõitma nii, et (paber)kaarti kaasas ei olegi. Meie sõitu suunab armatuurlaual asuv GPS seade või hoopis telefon. Oleme harjunud seda seadet usaldama - ta näitab meile teed sinna, kuhu minna tahame. Aga kuidas ta selle tee meie jaoks leiab? Mismoodi ta meid õigeks ajaks õigesse kohta juhatab? Kas me ikka julgeme seda seadet enda juhtimisel usaldada? Kuidas see kõik programmeeritud on?
Viimasel ajal on igasuguseid navigeerimisrakendusi üsna palju täiustatud. Näiteks telefonirakendus Waze toimib ainult kasutajate tagasiside najal. Kui keegi sõidab, märgib ta kaardile erinevaid ohte ja õnnetusi käsitsi või kui mitmed rakenduse kasutajad läbivad teatud teelõike aeglaselt, oskab see rakendus uue tee arvutada, vältides aeglasemaid teelõike. Antud peatüki eesmärk ongi põgusalt vaadata, kuidas navigeerimisrakendused erinevaid teekondi valivad.
VAATAME KAARTI
Soovime sõita näiteks Tartust Jõgevale. Selleks pakub navigeerimisrakendus meile kaht eri pikkusega teelõiku, millest ta on ühe välja valinud, kuna see on tema arvates kiirem. Kuidas ta teab, kumb kiirem on? Võtame appi matemaatika.
Kirjeldame olukorda joonise abil. Lihtsustame reaalset olukorda järgmiselt. Igal teelõigul on määratud piirkiirus:
- punane - 100 km/h
- must - 70 km/h
- hall - 50 km/h
Hetkel on võimalik Tartust Jõgevale minna kaht teed pidi.
- Ühe pikkuseks on 45 km + 4 km = 49 km,
- teise tee pikkuseks on 40 km + 20 km + 4 km = 64 km.
Teine tee on pealtnäha palju pikem, kuid arvesse tuleb võtta ka teeolusid. Esimese tee puhul on auto keskmiseks kiiruseks 70 km/h. Teise tee esimesel osal on keskmiseks kiiruseks 100 km/h, teisel osal 50 km/h ning kolmandal 70 km/h.
Kumb tee on kiirem Tartust Jõgevale sõitmiseks?
Esiteks leiame iga teelõigu läbimiseks kuluva aja.
- Kiiruse leidmiseks on olemas valem:
, kus v - kiirus, s - teepikkus, t - aeg- Antud valemist tuletame kuluva aja:
Liidame mõlema teekonna teelõikude ajad kokku ja võrdleme neid:
Lahendus:
- I teelõigu läbimiseks kulub
- II teelõigu läbimiseks kulub
Seega tuleks kiiruse huvides valida just esimene marsruut. Analoogiliselt leiab arvuti kiireima marsruudi ka siis, kui võimalikke teekondi on tuhandeid või isegi miljoneid.
NÄIDE I
Järgmistes programminäidetes kasutame järjendeid ehk liste (andmetüüp, milles saab korraga hoida mitut väärtust) ning for-tsüklit, mida me varasemalt käsitlenud pole. Samas leidub ka juba tuttavat nagu funktsioonid ja while-tsükkel. Antud programmid on lihtsalt uudistamiseks ning testiküsimusi nende kohta ei ole. Püüdke siiski konteksti ja kommentaaride järgi aru saada, mida tehakse ja miks seda vaja on.
Esiteks koostame kahekordsed järjendid mõlema teekonna jaoks. Järjend koosneb teejuppide järjenditest, kus esimesel kohal on teepikkus kilomeetrites ning teisel kohal lubatud kiirus kilomeetrites tunnis. Näiteks tee, mis koosneb kolmest teelõigust (muutuja rada1) on esimese teelõigu pikkus 40 km ja lubatud kiirus 100 km/h (järjendi esimene element [40, 100]), teise teelõigu pikkus 20 km ja 50 km/h (järjendi teine element [20, 50]) jne.
rada1 = [[40, 100], [20, 50], [4, 70]] rada2 = [[45, 70], [4, 70]]
Defineerime funktsiooni aja arvutamiseks kiiruse ja teepikkuse järgi.
def aeg (s, v): # Argumendid: teepikkus ja kiirus
if s > 0 and v > 0: # Teepikkus ja kiirus on positiivsed suurused
t = float(s) / float(v) * 60 # Teisendame ujukomarvudeks ja minutitesse
return t
else:
print ("Teepikkus ja aeg peavad olema positiivsed arvud!")
Leiame mõlema teekonna läbimiseks kuluva aja. Esimese teekonna läbimiseks kuluva aja arvutamine (kasutame while-tsüklit):
kuluv_aeg_1 = 0
i = 0
while i < len(rada1): # Kestab nii kaua kuni kõik järjendi elemendid on läbitud
x = aeg(rada1[i][0], rada1[i][1]) # Kasutades varasemalt defineeritud alamprogrammi 'aeg', leiame igal teelõigul kuluva aja
kuluv_aeg_1 = kuluv_aeg_1 + x # Liidame teelõikude ajad kokku
i = i + 1
kuluv_aeg_1 = int(kuluv_aeg_1) # Teisendame täisarvuks
Leiame sarnaselt ka teise teekonna jaoks kuluva aja (seekord kasutame vahelduseks for-tsüklit, huvi korral proovige seda ka ise mõnes programmis kasutada).
kuluv_aeg_2 = 0
for i in range(len(rada2)):
x = aeg (rada2[i][0], rada2[i][1])
kuluv_aeg_2 = kuluv_aeg_2 + x # Liidame ajad kokku
kuluv_aeg_2 = int(kuluv_aeg_2) # Teisendame täisarvuks
Nüüd võrdleme aegasid. Väljastame ekraanile, kumb teekond on kiirem ning kui palju selle läbimiseks aega kulub.
if kuluv_aeg_1 == kuluv_aeg_2:
print("Mõlemat teed pidi jõuab kohale sama kiiresti, aega kulub " + str(kuluv_aeg_1) + " minutit.")
elif kuluv_aeg_1 < kuluv_aeg_2:
print("Esimene tee on kiirem, aega kulub " + str(kuluv_aeg_1) + " minutit.")
else:
print("Teine tee on kiirem, aega kulub " + str(kuluv_aeg_2) + " minutit.")
NÄIDE II
Mis juhtub, kui võimalikke teid tuleb juurde? Vaatleme järgmist teede joonist:
Ülesanne: Mitu erinevat võimalust on nüüd Tartust Jõgevale sõitmiseks?
- Tartu - B - Jõgeva
- Tartu - D - Jõgeva
- Tartu - B - D - Jõgeva
- Tartu - D - B - Jõgeva
Seega ühe tee lisamisega tekkis juurde kaks võimalust. Kõige kiirema tee leidmiseks kasutame esimeses näites selgitatud arvutuskäiku. Kõik erinevad teekonnad me juba leidsime, nüüd tuleb nende läbimiseks kuluvad ajad eraldi välja arvutada ning seejärel neid võrrelda.
Leia erinevate teekondade läbimiseks kuluvad ajad esimese näiteprogrammi järgi. Kas programmi saaks kuidagi “ilusamaks” teha?
Vihje: Defineeri veel üks funktsioon:
def kuluvaeg (rada):
i = 0
kuluv_aeg = 0
while i < len(rada):
x = aeg(rada[i][0], rada[i][1])
kuluv_aeg = kuluv_aeg + x
i = i + 1
kuluv_aeg = int(kuluv_aeg) # Teisendame täisarvuks
return kuluv_aeg
Edasimõtlemiseks: kuidas küsida võimalikke teekondi kasutajalt?
KÖNIGSBERGI SILDADE PROBLEEM
Eestist mitte väga kaugel asub umbes Tallinna-suurune linn, mis aastasadu kandis nime Königsberg, aga pärast II maailmasõda sai nimeks Kaliningrad.
Vanasti oli Pregeli (Pregolja) jõel seitse silda.
Turistide seas kerkis küsimus: kas on võimalik üle kõigi sildade jalutada nii, et iga silda ületatakse täpselt üks kord ning jõutakse lõpuks alguspunkti tagasi?
Legendaarne matemaatik Leonhard Euler tõestas aastal 1736, et neid sildu ei olegi niiviisi võimalik läbida. Sellega pandi alus matemaatika harule, mille nimeks tänapäeval on graafiteooria. Graafiteooria on teadus, mis uurib graafe - skeeme-graafikuid, millel vaadeldakse objektide omavahelisi seoseid.
Selliseid lihtsamaid graafe leidub näiteks nuputamisülesannetes, kus tuleb ühe joonega kujundeid valmis joonistada (näiteks ühe joonega ümbrik). Selliseid mänge on ka nutiseadmetel ja arvutis mängimiseks. Graafiteooria abil saab tõestada näiteks huvitava fakti, et kui majal on üks välisuks, siis selles majas peab leiduma vähemalt üks ruum, kuhu viib paaritu arv uksi.
Tänapäeval on graafiteooria väga aktuaalne nii matemaatikas kui arvutiteaduses. Näiteks saab graafidega kujutada erinevaid suhtlusvõrgustikke, andmevooge, keerukaid kaarte ja palju muud. Kui tekib selle teema vastu suurem huvi, siis rohkem infot leiab näiteks siit.
Materjali koostasid Kerri Gertrud Vestberg ja Mari-Liis Jaansalu. Kohendatud kursuse korraldajate poolt.
| < eelmine? | 8. OSA sisukord | järgmine > |