RACUNALNIŠ TVO Problem najbližjih tock •is ■i' ■i' Igor Pesek V prispevku bomo predstavili problem najbližjih tock v množici P z n > 2 točkami. Rešitev problema je uporabna, ko moramo, denimo, odkriti oz. določiti, kateri dve osebi stojita najbližje ena drugi (otroška igra), pa tudi kateri dve letali sta si najbližje (preprečitev nesreče v letalskem prometu). Problem bomo opisali natančneje. Osebe bodo postale točke, igrišče pa bo postalo premiča, ravnina ali prostor. Poiskati torej želimo najbližji točki v množiči danih točk P, ki ležijo v N-dimenzional-nem prostoru. Najbližji v našem primeru pomeni običajno evklidsko razdaljo, kjer je razdalja med točkama v ravnini p1 = (x1,y1) in p2 = (x2,y2) enaka distpiP2 = ^(x1 - x2)2 + (yi - y2)2. Grafična ponazoritev problema je prikazana na sliki 1. SLIKA 1. Množica tock v ravnini www.dmfa.si Pregled vseh možnih razdalj Problema se lahko lotimo s preiskovanjem vseh možnih razdalj med točkami. V eni dimenziji, na premici, tako pregledamo (n) parov točk in med njimi določimo najbližji par. Ce podane točke naraščajoče uredimo, lahko preiskovanje pohitrimo, saj moramo pregledati le pare točk pi in pi+1 za i = 1,...,n - 1 in med njimi določiti najbližjega. Takšno preiskovanje zahteva linearni čas, vendar moramo upoštevati še čas za urejanje množiče točk. V ravnini in višjih dimenzijah nam ta razmislek ne pomaga, zato moramo izračunati razdalje za približno O(n2) parov točk. Iskanje s pomočjo strategije deli in vladaj Problem lahko hitreje rešimo s pomočjo strategije deli in vladaj, ki smo jo v Preseku že predstavili. Pri tej strategiji se problem običajno rešuje s pomočjo rekurzivnih kličev v treh korakih; kar bomo predstavili za primer, ko točke ležijo v ravnini. Deli. Poiščemo navpično premičo L, ki deli mno-žičo točk na dva dela PieVo in Pdesno ■ Ta sta po velikosti enaka oz. v primeru lihega števila točk v P je v Pievo ena točka več. Pri tem so vse točke iz Pievo levo od črte L in točke iz Pdesno desno od črte L. Primer razdelitve s premičo L je prikazan na sliki 2. Vladaj. Izvedemo dva rekurzivna kliča; s prvim poiščemo najbližji par točk v Pievo in z drugim kličem najbližji par točk v Pdesno. Vsak klič vrne najkrajšo razdaljo dievo oz. ddesno dane množiče, kot je prikazano na sliki 3. V rekurzivnem kliču pazimo, da v primeru števila točk dane množiče |P| < 3 za določitev najkrajše razdalje pregledamo vse možne razdalje. Sedaj določimo d, ki je enak ■ d = min(dievo, ddesno)- Združi. Najbližji par točk je sedaj bodisi par z razdaljo d, ki smo jo določili z enim od rekurzivnih PRESEK 43 (2015/2016) 1 27 RAČU N A L NIŠTVO Plevo Pde. SLIKA 2. Razdelitev na dve množici s premico L SLIKA 4. Navpični trak širine 2d klicev, bodisi par tock, kjer ena tocka leži v Pievo in ena tocka v Pdesn0- Le-teh z rekurzivnimi klici nismo zajeli. Vseh parov tock iz različnih množic nam ni potrebno preveriti. Zakaj ne? Išcemo namrec takšen par, katerega razdalja je krajša od d. Zadostuje torej da preverimo samo pare tock, kjer sta obe tocki para znotraj navideznega navpicnega traku T, ki sega za razdaljo d na vsako stran od premice L. Skupaj je torej T širok 2d, kot je prikazano na sliki 4. Zakaj je to dovolj? Ce želimo najti krajšo razdaljo od d, je iskanje dlje od teh premic nesmiselno, ker bo razdalja zagotovo vecja od d. V najslabšem primeru ena od tock leži na premici L, tocka iz druge množice pa je najvec za d oddaljena od prve tocke. Torej nas vse tocke, ki ležijo izven traku T, ne zanimajo in jih za ta korak v celoti pozabimo. Sledi pregled vseh parov tock, ki ležijo znotraj traku T. Ta korak lahko tudi pohitrimo. Kako? Tocke uredimo narašcajoce ^dd e. po y-koordinati, kar nam pomaga pri preiskovanju, saj sedaj zadostuje, da pregledamo samo tocke, ki tudi v navpicni smeri niso oddaljene za vec kot d od preiskovane tocke. Primer je prikazan na sliki 5. Pregledamo vse tocke znotraj traku T; ce obstaja takšen dT < d, potem smo našli novo najkrajšo razdaljo, sicer je najkrajša razdalja tista, ki smo jo dobili z enim od rekurzivnih klicev. V nadaljevanju je predstavljen algoritem za iskanje najbližjega para tock. Nekatere funkcije v algoritmu so prepušcene bralcu, da jih napiše sam. NajblizjiTocki (P, P_x ,n) if |P_x| <= 3: NajkrajsaRazdalja(P_x) //pregledamo vse pare Deli(P_x, P_levo, P_desno, L, n) d_levo = NajblizjiTocki(P, P_levo, n) d_desno = NajblizjiTocki(P, P_desno, n) d = min(d_levo, d_desno) //pregledamo vse tocke znotraj traku T P_t = Dol oči TockeNaTraku(P_x, L, d) Uredi Po_Y_Koordi nati(P_t) d_t = PoisciNajkrajsoRazdaljo(P_t, d) return min(d, d_t) d L L L www.presek.si SLIKA 3. Rezultat rekurzivnih klicev 28 PRESEK 43 (2015/2016)1 31 RACUNALNIŠ TVO • » • d i • d t • d SLIKA 5. Področje iskanja v navpičnem traku T Zaključek Algoritem za iskanje najbližjega para po strategiji deli in vladaj ima časovno zahtevnost O(n ■ log n), kar je precejšnja izboljšava v primerjavi z metodo preiskovanja vseh razdalj med pari točk, ki ima časovno zahtevnost O(n2). Predstavili smo delovanje algoritma v ravnini (N = 2), vendar se takoj postavi vprašanje, kaj pa v 3D prostoru (N = 3) ali kakšnem večdimenzionalnem prostoru (N > 3). Izkaže se, da algoritem deluje tako, da navpična premiča ni več premiča ampak ravnina oz. natančneje, delilna premica L je vedno prostor z eno dimenzijo manj, kot je N. Literatura [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest in C. Stein, Introduction to Algorithms, MIT Press, 2009. _XXX www.dmfa.si www.obzornik.si www.presek.si Barvni sudoku •4/ -i' •i' V 8 X 8 kvadratkov moraš vpisati začetna naravna števila od 1 do 8 tako, da bo v vsaki vrstiči, v vsakem stolpču in v kvadratkih iste barve (pravokotnikih 2 X 4) nastopalo vseh 8 števil. 3 O □ m > a. < m > m * £ -» a 3 7 4 8 4 5 3 1 5 8 4 5 4 1 7 7 4 2 1 8 E L 9 17 8 Z S 1 S 2 L 8 E 4 7 9 9 L S 17 Z 7 E 1 8 L 8 E 4 9 Z 5 4 8 Z L S L 9 E Z L 8 17 1 3 S 9 Z 9 E 5 L 8 4 L 8 4 7 L 9 S 3 Z XXX L PRESEK 43 (2015/2016) 1 29