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.