Distribucijska mreža

V nalogi bomo delali s koordinatami otrok, ki jih mora obiskati Miklavž. Kot je znano, je možakar že v letih, zato namerava postaviti distribucijske centre, v katere bodo jeleni dostavili robo, on pa jo bo distribuiral od tam naprej. V nalogi mu bomo pomagali določiti čim boljšo razpostavitev teh centrov.

Koordinate so opisane s terko, na primer (3, -1), če gre za koordinate v dvodimenzionalnem prostoru, ali, morda, (4, 1, -4, 0, 12), če gre za koordinate v petdimenzionalnem prostoru. Števila dimenzij ne smete predpostaviti, tako da bo program uporaben tudi za Miklavža v kakem drugem številu dimenzij. Pač pa lahko predpostavite, da imajo vse točke, s katerimi pokličemo funkcijo, enako število dimenzij.

Testi

Testi: testi-distribucijska-mreza.py

Za oceno 5 (ogrevalna)

Napišite funkcijo razdalja(s, t), ki vrne razdaljo med točkama s in t.

>>> razdalja((0, 0), (3, 4)) 5 >>> razdalja((1, 1, 1, 1, 1, 1, 1), (2, 2, 0, 1, 0, 1, 1)) 2

Rešitev

Če bi bila (pa ni!) naloga sestavljena tako, da bi bile vse točke na ravnini, bi bilo to nekoliko preprosteje, napisali bi le

def razdalja(s, t): return sqrt((s[0] - t[0]) ** 2 + (s[1] + t[1]) ** 2)

Če je število dimenzij drugačno - sploh pa ne znano vnaprej - bomo potrebovali zanko. Takole, prosim, ne delajte:

def razdalja(s, t): v = 0 for i in range(len(s)): v += (s[i] - t[i]) ** 2 return sqrt(v)

Dovolj ste stari, da veste, da je to predolgo in nepregledno ter da nima smisla, saj je preprosteje

def razdalja(s, t): v = 0 for e, f in zip(s, t): v += (e - f) ** 2 return sqrt(v)

Po novem pa znamo tudi krajše. Funkcija mora vrniti vsoto kvadratov razlik parov koordinat.

def razdalja(s, t): return sqrt(sum((e - f) ** 2 for e, f in zip(s, t)))

Za oceno 6

Napišite funkcijo najblizji(x, s), ki prejme koordinato otroka, x, in množico s koordinat (možnih) distribucijskih centrov, s. Funkcija mora vrniti koordinato tistega distribucijskega centra, ki je najbližji otroku.

Z drugimi besedami, funkcija naj vrne tisto točko (torej terko) iz seznama terk s, ki je najbližja točki x.

>>> najblizji((9, 2), {(0, 0), (10, 0), (10, 10)}) (10, 0)

Rešitev

Preverimo torej, ali smo se naučili, kar ponavljamo že ves semester, iskanje najmanjšega (ali največjega, saj to je isto) elementa z običajno komplikacijo: vrniti moramo točko, primerjati pa njene razdalje.

No, če smo kaj veliko vadili, smo tole. Tako da bi morali rešitev stresti iz rokava:

def najblizji(x, s): naj = None for y in s: if naj is None or razdalja(x, y) < razdalja(x, naj): naj = y return naj

Z generatorji? Da, ampak. Ni preveč lepo.

def najblizji(x, s): return min((razdalja(x, e), e) for e in s)[1]

Sestavimo terke, ki vsebujejo razdaljo in točko. Poiščemo "najmanjšo terko"; ker jih najprej primerja po prvem elementu, bomo dobili terko, v kateri je točka, ki je najmanj oddaljena. Tisti [1] na koncu pa je potreben, da bomo iz te terke vzeli le točko, ne pa tudi razdalje. Če bi jo izpustili, bi testi vračali par (razdalj, točka), tega pa nočemo.

Oklevanje, češ, da ni prav lepo, izvira iz tega, da gre lepše, vendar bi se morali za to učiti o lambda-funkcijah.

def najblizji(x, s): return min(s, key=lambda e: razdalja(e, x))

Funkciji min smo dali poiskati "najmanjšo" točko iz s, pri čemer naj jih primerja po "ključu" razdalja. Da smo fiksirali en argument (x), smo uporabili lambdo, česar še ne poznamo in pri Programiranju 1 niti ne bomo spoznali.

Ko se boste nekateri na drugi stopnji učili o funkcijskih jezikih, pa boste znali to "fiksiranje" izvesti še krajše.

def najblizji(x, s): return min(s, key=partial(razdalja, x))

Temu, kar smo uporabili, se reče currying, po logiku Haskllu Curryju. Iz funkcije razdalja smo s partial(razdalja, x), naredili novo funkcijo, ki je enaka funkciji razdalja, le da en argument že ima.

Tega vam ni potrebno znati. Napisal sem kot zgled, da obstajajo v jezikih (predvsem v takšnih, ki nima spremenljivk, temveč vezave in, še pomembneje, so v njih funkcije "prvorazredni objekti", kar pomenim, da se da z njimi delati vse, kar se da delati z drugimi rečmi, recimo števili in nizi) še precej naprednejši koncepti od teh, mehanskih, ki se jih učimo tu. Če jih obvladate, postanejo programi precej enostavnejši (primerjajte prvo in zadnjo funkcijo), ne da bi bili zaradi tega bolj zapleteni. Če, seveda, te reči obvladate dovolj, da znate brati takšne programe.

Tule je še nekaj, kar je - samostojno? morda ne - odkrilo veliko študentov.

def najblizji(x, s): t = {} for e in s: t[e] = razdalja(x, e) return min(j, key=j.get)

Vse avtorje takšnih rešitev bi z veseljem vprašal (in eno leto sem naredil nekaj podobnega), ali vedo, kaj njihov program pravzaprav dela. Ne počnite tega. Če ne veste, kako deluje, ne uporabite. Če prepišete rešitev, ki je niti ne razumete, se niste naučili ničesar. Domačo nalogo - ki je priložnost, da se urite v programiranju, kar je nekaj, kar boste potrebovali - ste vrgli stran. Norčujete se iz sebe, iz asistentov, iz mene.

Če že morate, pa napišite

def najblizji(x, s): t = {e: razdalja(x, e) for e in s} return min(t, key=t.get)

da se ne bom spraševal, kako lahko nekdo razume vezane metode in jih pošilja kot argumente funkcijam, izpeljanega slovarja pa ne zna sestaviti.

Za oceno 7

Miklavž, kot je znano, ne gradi hiš, temveč skriva distribucijske centre po podstrešjih hiš, v kateri živijo otroci. V tem koraku bomo predpostavili, da imamo neko množico otrok s koordinatami, zbranimi v s. Zanimalo nas bo, pri katerem od teh otrok se mu najbolj splača postaviti distribucijski center. Z drugimi besedami, radi bi poiskali otroka, ki stanuje najbolj na najbolj "osrednjem" mestu.

Najprej napišite funkcijo pop_razdalja(x, s), ki vrne poprečno razdaljo med otrokom x in vsemi otroki iz s. Pri tem je x spet terka (koordinate otroka) in s množica s koordinatami (terkami) vseh otrok.

>>> pop_razdalja((1, 1), {(0, 0), (10, 0), (10, 10)}) 7.732506920622789

Točka (1, 1) je od (0, 0) oddaljena za 1.4142135623730951 (koren iz 1 ** 2 + 1 ** 2), od (10, 0) je oddaljena za 9.055385138137417 (koren iz 9 ** 2 + 1 ** 2), od (10, 10) pa za 12.727922061357855 (koren iz 9 ** 2 + 2 ** 2). Poprečje teh treh števil je 7.732506920622789.

Napišite tudi funkcijo center(s), ki vrne tisto točko iz s, katere poprečna razdalja do ostalih točk iz s je najmanjša.

Namig: center(s) naj pokliče pop_razdalja(x, s) za vsako točko x iz s in si zapomni (ter vrne) tisti x, pri katerem je pop_razdalja vrnila najmanjšo vrednost. To, da naloga pravi "do ostalih točk" naj te ne vznemirja, saj bo prispevek te točke (če jo boš pustil v s) tako ali tako vedno enak.

>>> center({(0, 0), (10, 0), (0, 10), (10, 10), (5, 4)}) (5, 4)

V gornjem primeru imamo pet točk - štiri so oglišča štirikotnika, peta pa je približno na sredi. Ker je le-ta v poprečju najmanj oddaljena od drugih, funkcija vrne le-to.

Rešitev

Pri poprečnih razdaljah tokrat res ne bomo izgubljali besed: vsoto razdalij delimo z njihovim številom.

def pop_razdalja(x, s): return sum(razdalja(x, si) for si in s) / len(s)

Center je podoben tistemu, kar smo reševali v nalogi za oceno 6: tam smo iskali točko z najmanjšo razdaljo do določene točke, tu iščemo točko z najmanjšo poprečno razdaljo do skupine točk.

Vseeno bomo zastavili malenkost drugače.

def center(s): naj_x = naj_r = None for x in s: r = pop_razdalja(x, s) if naj_x is None or r < naj_r: naj_x = x naj_r = r return naj_x

Razlika je v tem, da smo si prej, v nalogi za oceno 6 zapomnili le "najboljšo" točko in vsakič sproti računali razdaljo do nje, tu pa si zapomnimo tudi poprečno razdaljo, da je ne bi bilo potrebno vedno znova računati.

Mimogrede, tudi min, ki jo lahko pokličemo, namesto da se ubijamo s svojo funkcijo, se obnaša ekonomično in z vsako točko le enkrat pokliče pop_razdalja.

Spremenimo pop_razdalja tako, da bo štela, kolikokrat je bila poklicana.

def pop_razdalja(x, s): global stevec stevec += 1 return sum(razdalja(x, si) for si in s) / len(s)

(Vem, da sem prepovedal uporabo in predvsem spreminjanje globalnih spremenljivk, ampak tole je za diagnostično rabo. ;)

Zdaj napišimo eno od krajših različic iskanja najmanjšega elementa (nič hudega, če je ne razumemo povsem).

def center(s): return min(s, key=partial(pop_razdalja, s=s))

Pokličimo jo.

stevec = 0 center({(0, 0), (10, 0), (0, 10), (10, 10), (5, 5)}) print(stevec)

Program izpiše 5, kar pomeni, da se funkcija pop_razdalja res pokliče za vsako točko le po enkrat.

Za oceno 8

Miklavž, ko je znano, gradi hiše, v katerih postavlja distribucijske centre. S tem ni težav, ker so te hiše nevidne. Hišo bo postavil v točki, ki je najbolj "na sredi" - v težišču.

Napišite funkcijo tezisce(s), ki vrne težišče točk v s. Težišče je točka, ki jo dobiš tako, da izračunaš poprečno koordinato x, koordinato y, koordinato z ... in tako naprej vseh točk v s.

>>> tezisce({(0, 0), (10, 0), (10, 10)}) (6.666666666666667, 3.3333333333333335)

Prva številka je poprečje koordinat x, (0 + 10 + 10) / 3. Druga je poprečje koordinat y (0 + 0 + 10) / 3. Funkcija mora seveda delovati tudi za več dimenzij in več točk.

Rešitev

Tale je bila kar nadležna. V te namene navadno uporabljamo primerne knjižnice (recimo numpy, v katerem bi nalogo rešili z numpy.sum(tocke, axis=0) / len(tocke)).

Da bo reč preglednejša, najprej pripravimo le funkcijo, ki sešteje dva vektorji (ali točki, če hočete).

def sestej_vektorja(s, t): u = [] for e, f in zip(s, t): u.append(e + f) return u

Ali, krajše:

def sestej_vektora(s, t): return [e + f for e, f in zip(s, t)]

Zdaj pa težišče. Če ne znamo dobiti dimenzije prve točke (malo sem vas zafrknil z množicami ;), v začetku postavimo vsoto na None in prvo točko le shranimo, namesto da bi jo prišteli.

def tezisce(s): vsota = None for e in s: if vsota is None: vsota = e else: vsota = sestej_vektorja(vsota, e) for i in range(len(vsota)): vsota[i] /= len(s) return tuple(vsota)

Zadnji del, deljenje, je neroden. Seveda znamo boljše:

def tezisce(s): vsota = None for e in s: if vsota is None: vsota = e else: vsota = sestej_vektorja(vsota, e) return tuple(e / len(s) for e in vsota)

Druga možnost je, da nekako pridemo do dimenzije točk. Ena možnost je, da dobimo točko tako, da jo vzamemo iz množice - a brž porinemo nazaj vanjo.

tocka = s.pop() s.add(tocka)

Lahko pa čez množico naženemo zanko in jo takoj prekinemo.

for tocka in s: break

Zdaj, ko imamo točko, bomo z [0] * len(tocka) sestavili primerno dolg seznam ničel in raje seštevali vanj.

def tezisce(s): for tocka in s: break vsota = [0] * len(tocka) for e in s: vsota = sestej_vektorja(vsota, e) return tuple(e / len(s) for e in vsota)

Če bi znali kaj več, bi napisali

def tezisce(s): return tuple(sum(x) / len(x) for x in zip(*s))

Za oceno 9

Zdaj pa predpostavimo, da je Miklavž že vzpostavil distribucijske centre. Vsakemu otroku bo prinesel robo iz tistega distribucijskega centra, ki je otroku najbližji.

Napiši funkcijo razdeli(xs, s), ki prejme dve množici točk. Prva, xs, je množica koordinat distribucijskih centrov. Druga, s, je množica koordinat otrok. Funkcija naj vrne slovar, katerega ključi so točke iz xs, vrednosti pa podmnožice točk iz s. Funkcija naj za vsako točko iz s (otroka) odkrije, katera od točk izmed xs (distribucijski center) ji je najbližja in jo da v pripadajoči element slovarja.

Recimo, da bi funkcijo poklicali z

razdeli({(0, 0), (10, 0), (10, 10)}, {(11, 2), (9, 9), (1, -1), (11, 9), (0, 2)})

V tem primeru mora funkcija vrniti slovar

{(0, 0): {(1, -1), (0, 2)}, (10, 0): {(11, 2)}, (10, 10): {(9, 9), (11, 9)} }

Še en primer:

razdeli({(5, 5), (5, 10), (15, 5), (40, 50)}, {(5, 5), (4, 5), (5, 9), (6, 11), (-20, -20), (16, 5)}) >>> {(5, 5): {(5, 5), (4, 5), (-20, -20)}, (5, 10): {(5, 9), (6, 11)}, (15, 5): {(16, 5)}, (40, 50): set()}

Funkcija je morala razdeliti otroke {(5, 5), (4, 5), (5, 9), (6, 11), (-20, -20), (16, 5)} med distribucijske centre {(5, 5), (5, 10), (15, 5), (40, 50)}. Ne spreglejte, recimo, da je (-20, -20) sicer daleč od vsega, vendar pač najbližja točki (5, 5). Še bolj ne spreglejte, da je center (40, 50) tako daleč, da nima nobenega oskrbovanca, saj so vsi otroci bližji kakemu drugemu centru.

Zdaj pa naredimo obratno: predpostavimo, da so otroci razdeljeni v množice in za vsako množico moramo poiskati idealno lokacijo distribucijskega centra. Napiši funkcijo poisci_centre(ss), ki prejme seznam množic točk in vrne množico njihovih optimalnih centrov (takšnih, kot jih vrača funkcija center, po encenter za vsako množico iz ss).

>>> poisci_centre([{(0, 0), (10, 0), (0, 10), (10, 10), (5, 5)}, {(0, 0), (4, 5), (10, 0), (0, 10), (10, 10)}, {(0, 0), (10, 0), (10, 10)}, {(42, 42)}]), {(5, 5), (4, 5), (10, 0), (42, 42)}

Center prve množice je (5, 5), center druge je (4, 5) in tako naprej.

Rešitev

Pri razdeli bi lahko uporabili slovarje s privzetimi vrednostmi - a tokrat naredimo malo drugače. Kaj bodo ključi tega slovarja, že vemo: vsi centri, xs. Sestavili bomo torej slovar, katerega ključi bodo centri, vrednosti pa prazne množice, {x: set() for x in xs}.

Nato le gremo prek vseh točk in vsako dodelimo najbližjemu centru, pri čemer si pomagamo s funkcijo najblizji.

def razdeli(xs, s): mnozice = {x: set() for x in xs} for o in s: mnozice[najblizji(o, xs)].add(o) return mnozice

Pri iskanju centrov pa res ne bomo zapletali s čimerkoli drugim kot z izpeljano množico.

def poisci_centre(ss): return {center(s) for s in ss}

Za oceno 10

Zdaj pa bomo končali nalogo: za dane koordinate otrok bomo določili optimalne lokacije distribucijskih centrov.

Napiši funkcijo nacrtuj(s, k), ki kot argument dobi seznam koordinat vseh otrok, s in število distribucijskih centrov, ki jih bo Miklavž postavil, k ter določi optimalne distribucijske centre takole. Najprej postavi distribucijske centre kar na podstrešja prvih k otrok. Za vsakega od teh distribucijskih centrov določi, katere množice otrok mu pripadajo (torej, kateri otroci so določenemu centru bližji kot kateremukoli drugemu). Na ta način dobi množice otrok; vendar nihče ne zagotavlja, da bo distribucijski center, okrog katerega smo nabrali določeno množico, tudi optimalni distribucijski center za to množico. Zato v naslednjem koraku popravimo distribucijske centre: za vsako množico otrok izračunamo nove, boljše centre. Zdaj, ko imamo boljše centre, ponovno razdelimo vse otroke med te, nove centre. Tako smo spet dobili (nove) množice otrok, a centri, na podlagi katerih smo jih določili, spet niso nujno najboljši. Zato v naslednjem koraku spet izračunamo boljše centre, potem spet preračunamo množice in tako naprej...

Z drugimi besedami, funkcija naredi tole:

• vzame prvih k točk iz s; tem točkam recimo "centri" (čeprav niso)
• ponavlja:
• s funkcijo razdeli razporedi vse točke k najbližjim centrom;
• s funkcijo poisci_centre poišče centre skupin, ki jih je naredil v prejšnjem koraku. Ti centri bodo zdaj novi centri, s katerimi bo ponovil vse skupaj.

Ponavljanje naj se konča takrat, ko se množica centrov ne spreminja več.

Funkcija naj vrne slovar, katerega ključi so koordinate distribucijskih centrov, pripadajoče vrednosti pa vsi otroci, ki jih oskrbuje posamezni center.

>>> otroci = [ (0, 0), (1, 0), (0, 1), (0, 5), (0, 6), (0, 7), (5, 0), (5, 1), (5, 2)] >>> nacrtuj(otroci, 3) {(0, 0): {(0, 0), (1, 0), (0, 1)}, (0, 6): {(0, 5), (0, 6), (0, 7)}, (5, 1): {(5, 0), (5, 1), (5, 2)}})

Rešitev

Nalogo za oceno 10 je bilo težje opisati kot sprogramirati.

def nacrtuj(s, k): centri = s[:k] scentri = None while centri != scentri: scentri = centri clustri = razdeli(centri, s) centri = poisci_centre(clustri.values()) return clustri

Najprej poglejmo zanko: vse skupaj ponavljamo, dokler se centri spreminjajo. Zato v vsakem koraku najprej shranimo trenutne centre (scentri = centri), nato izračunamo nov razpored, kdo bo oskrbovan iz katerega centra (clustri = razdeli(centri, s)) in na podlagi teh skupin določimo nove centra (centri = poisci_centre(clustri.values())).

V pogoju zanke preverjamo ali so stari centri enaki novim. Da bi to delovalo tudi v prvem krogu, bomo pred zanko postavili scentri = None. Ker bodo centri in scentri v začetku očitno različni, se bo zanka vsaj enkrat izvedla.

Medtem ko se tisti, ki v programiranju še niso posebej doma, ukvarjajo z osnovnejšimi problemi, se morate tisti, ki rešujete naloge za višje ocene, počasi začeti učiti tudi elegance.

Dodatne naloge

Spremeni rešitve za oceni 9 in 10 tako, da centrov ne bosta določali s funkcijo center temveč s funkcijo tezisce - torej skladno z drugim scenarijem, po katerem Miklavž gradi nove hiše.

Ugotovi, kaj si pravkar sprogramiral in čemu ta reč služi. ;) Zgodbica o Miklavžu je v resnici le metafora za nek splošnejši in zelo uporaben postopek.