Spet razdalje med kraji
Testi
testi-spet-razdalje-med-kraji.py
Naloga
Naslednje funkcije bodo delale s seznami krajev, ki bodo podani tako kot v prejšnji domači nalogi. Recimo tako:
kraji = [
('Brežice', 68.66, 7.04),
('Lenart', 85.20, 78.75),
('Rateče', -65.04, 70.04),
('Ljutomer', 111.26, 71.82)
]
Ogrevali se bomo tokrat kar sproti. Začnimo kar z obvezno nalogo.
Obvezna naloga
Napisati bo potrebno prgišče funkcij.
Napiši funkcijo razdalja(x1, y1, x2, y2), ki sprejme koordinati dveh točk,
(x1, y1) in (x2, y2) ter vrne evklidsko razdaljo med njima.
>>> razdalja(10, 20, 13, 24)
5.0
Napiši funkcijo koordinate(kraj, kraji), ki prejme ime kraja in seznam vseh
krajev ter vrne koordinate podanega kraja.
>>> x, y = koordinate("B", [("A", 42, 55), ("B", 13, 22), ("C", 0, 0)])
>>> x
13
>>> y
22
Napiši funkcijo oddaljenost(kraj1, kraj2, kraji), ki prejme imeni dveh
krajev in seznam vseh krajev ter vrne razdaljo med njima. Funkcija ne sme
iskati krajev in računati razdalj med njimi, temveč mora uporabljati gornji
funkciji koordinate in razdalja.
>>> oddaljenost("B", "A", [("A", 42, 55), ("B", 13, 22), ("C", 0, 0)])
43.93176527297759
Napiši funkcijo najblizji(kraj, kraji), ki prejme ime kraja in seznam vseh
krajev ter vrne tisti kraj s seznama, ki je najbližji podanemu kraju.
>>> najblizji("B", [("A", 42, 55), ("B", 13, 22), ("C", 0, 0)])
'C'
Rešitev
Računanje razdalje je malo lažje celo od prve domače naloge.
from math import *
def razdalja(x1, y1, x2, y2):
return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
Funkcija prejme štiri argumente in z njimi ravnamo po Pitagorovem nasvetu.
Druga naloga je običajni vzorec iskanja: for, znotraj njega if, znotraj
njega return.
def koordinate(kraj, kraji):
for ime, x, y in kraji:
if ime == kraj:
return x, y
Pri zanki for ravnamo modro, če element seznama - ki je trojka - kar takoj
razpakiramo. Druge različice, kot, recimo
def koordinate(kraj, kraji):
for trojka in kraji:
ime, x, y = trojka
if ime == kraj:
return x, y
ali celo
def koordinate(kraj, kraji):
for trojka in kraji:
if trojka[0] == kraj:
return trojka[1], trojka[2]
so definitivno manj pregledne.
Kaj se zgodi, če iskanega kraja ni? V tem primeru funkcija nikoli ne pride do
returna in tako ne vrne ničesar, oziroma, točneje, vrne None.
Za oddaljenost le pokličemo, kar smo naprogramirali zgoraj.
def oddaljenost(kraj1, kraj2, kraji):
x1, y1 = koordinate(kraj1, kraji)
x2, y2 = koordinate(kraj2, kraji)
return razdalja(x1, y1, x2, y2)
Poberemo koordinate prvega kraja, koordinate drugega kraja in ju damo funkciji
razdalja, da izračuna razdaljo.
Zadnja funkcija je spet precej običajno početje: iskanje najmanjšega elementa.
def najblizji(kraj, kraji):
najbl = naj_razdalja = None
x1, y1 = koordinate(kraj, kraji)
for kraj2, x2, y2 in kraji:
if kraj2 != kraj:
r = razdalja(x1, y1, x2, y2)
if najbl == None or r < naj_razdalja:
najbl, naj_razdalja = kraj2, r
return najbl
V začetku z najbl = naj_razdalja = None zabeležimo, da nismo videli še
nobenega kraja. Z x1, y1 = koordinate(kraj, kraji) izračunamo in si zapomnimo
koordinati prvega kraja, da jih ne bomo računali vsakič posebej.
Zdaj gremo prek vseh krajev. Zanimajo nas le taki, ki niso enaki trenutnemu.
Za takšne izračunamo razdaljo, r = razdalja(x1, y1, x2, y2). Če doslej nismo
videli še nobenega kraja (najbl == None) ali pa je tale kraj bližji od
najbližjega doslej (r < naj_razdalja), si zapomnimo trenutni najbližji kraj
in razdaljo do njega (najbl, naj_razdalja = kraj2, r), da ga lahko potem
vrnemo (return najbl).
Dodatna naloga
Če želiš (treba pa ni - vendar ti lahko pride prav), napiši funkcijo
brez_kraja(kraj, kraji), ki prejme ime kraja in seznam krajev ter vrne nov
seznam krajev, ki je enak originalnemu, le brez podanega kraja.
>>> brez_kraja("B", [("A", 42, 55), ("B", 13, 22), ("C", 0, 0)])
[("A", 42, 55), ("C", 0, 0)]
Za "pravo nalogo" pa napiši funkcijo veriga(kraj, kraji), ki prejme, uh, isto,
in vrne seznam imen krajev, ki ga dobimo takole: predstavljaj si popotnika, ki
stoji v kraju kraj. Med kraji poišče najbližji kraj in gre tja. Nato
poišče najbližji kraj, v katerem še ni bil, in gre tja. To ponavlja, dokler
takole ne obišče vseh krajev.
Če si napisal funkcijo brez_kraja in si primerno spreten, bo funkcija
veriga dolga pet vrstic (+ glava funkcije), ne da bi moral pri tem uporabiti
karkoli, česar se še nismo učili.
Rešitev
Rešitev je prijetno kratka:
def brez_kraja(kraj, kraji):
novi = []
for ime, x, y in kraji:
if ime != kraj:
novi.append((ime, x, y))
return novi
def veriga(kraj, kraji):
v = []
while kraj:
v.append(kraj)
kraj, kraji = najblizji(kraj, kraji), brez_kraja(kraj, kraji)
return v
Funkcija brez_kraja ni nič posebnega, splača pa se jo pripraviti zato, da je
ta koda ločena od ostale in ne dela zmede v "pravi" funkciji. Iti mora,
preprosto, prek originalnega seznama in vse kraje, katerih ime ni enako tistemu,
ki ga želimo zbrisati, dodajati v novi seznam.
Funkcija veriga je šokantno preprosta. V v bomo zlagali zaporedje krajev.
V kraj bo trenutni kraj; ko krajev zmanjka, bo v njem None, zato lahko
zapišemo while kraj (None je namreč neresničen). Zdaj ponavljamo tole:
v v dodamo trenutni kraj, nato pa kraj zamenjamo z najbližjim krajem in
kraji s seznamom brez trenutnega kraja. Za zadnji dve stvari je pomembno, da
ju naredimo hkrati. Če najprej zamenjamo trenutni kraj, ga ne bomo mogli
pobrisati s seznama krajev. Če najprej pobrišemo trenutni kraj s seznama, pa ne
bomo mogli najti njegovih koordinat, ki jih potrebujemo za iskanje najbližjega
kraja.
Zelo dodatna naloga
Zdaj pa še malo drugače: imamo celo vojsko popotnikov. Svojo pot začne v poljubnem kraju - recimo v Brežicah. Vojska se razgleda, kateri kraj je najbližji kraj - v tem primeru Krško - in ga osvoji. Nato se vojska razgleda, kateri kraj je najbližji kraj, v katerega bi lahko šla. Izkaže se da v Brestanico, namreč iz Krškega (če bi bil kakšen kraj bližji Brežicam, kot je Brestanica Krškemu, pa bi šla tja). Zdaj imamo vojsko v treh krajih. Spet pogleda kateri kraj je najbližji že osvojenim in ugotovi, da so to Radeče, ki so kar blizu Brestanice... In tako naprej.
Funkcija vojska(kraji) dobi seznam krajev in vrne seznam parov "prehodov"
med kraji, recimo
[('Brežice', 'Krško'), ('Krško', 'Brestanica'), ('Brestanica', 'Radeče'),
('Radeče', 'Laško'), ('Laško', 'Celje'), ('Celje', 'Žalec'),
('Celje', 'Šentjur'), ('Žalec', 'Velenje'), ('Velenje', 'Šoštanj'),
('Žalec', 'Trbovlje'), ('Šoštanj', 'Slovenj Gradec'),...
in tako naprej.
Rešitev te naloge je v nekem smislu unikatna: ne glede na to, v katerem kraju vojska začne, bo morala prehoditi enako razdaljo. Po drugi strani pa lahko tudi za isti začetni kraj obstajajo različne enako dobre rešitve.
Rešitev
Tudi to je preprostejše, kot se zdi.
def najblizji_par(kraji1, kraji2):
naj_par = naj_razdalja = None
for kraj1, x1, y1 in kraji1:
for kraj2, x2, y2 in kraji2:
r = razdalja(x1, y1, x2, y2)
if not naj_par or r < naj_razdalja:
naj_par = (kraj1, x1, y1), (kraj2, x2, y2)
naj_razdalja = r
return naj_par
def vojska(kraji):
obiskani = [kraji[0]]
neobiskani = kraji[1:]
pari = []
while neobiskani:
kraj1, kraj2 = najblizji_par(obiskani, neobiskani)
pari.append((kraj1[0], kraj2[0]))
obiskani.append(kraj2)
neobiskani.remove(kraj2)
return pari
Pomožna funkcija tokrat poišče najbližji par krajev iz dveh seznamov. Imamo torej dve zanki eno znotraj druge: za vsak kraj iz prvega seznama pogledamo vse kraje iz drugega. Ostalo je rutinsko iskanje najmanjšega elementa.
Druga funkcija vzdržuje dva seznama: seznam krajev, ki smo jih že obiskali in krajev, ki jih še nismo. V prvega bomo v začetku dali kar prvi kraj iz seznama vseh krajev, v drugega pa vse ostale.
Dokler obstaja kak neobiskan kraj, poiščemo najbližji par
kraj1, kraj2 = najblizji_par(obiskani, neobiskani). Po tem bo kraj1 eden od
že obiskanih, kraj2 pa najbližji neobiskani kraj. Med pare dodamo ta par.
kraj2 dodamo k obiskanim in odstranimo iz neobiskanih.
Problem, ki smo ga reševali, se imenuje iskanje najmanjšega vpetega drevesa. Postopek, ki smo ga uporabili, ni najboljši: njegovo trajanje narašča s kubom števila krajev: za dvakrat večje število krajev potrebuje osemkrat toliko časa, za desetkrat večje pa desetkrat toliko časa. Problem je mogoče rešiti tudi veliko hitreje. Kogar zanima: Wikipedija je tvoj prijatelj.