Algoritmi/"Pohlepni" algoritmi
Kod bektreking algoritama koje smo videli, naišli smo na algoritme koji su našli tačku odluke i zatim vršili rekurziju preko svih opcija iz te tačke odluke. Pohlepan algoritam, može da se posmatra kao bektreking algoritam kod koga je za svaku tačku odluke „najbolja opcija“ već poznata pa može da se izabere bez potrebe za rekurzijom preko bilo koje alternativne opcije. Naziv „pohlepan“ potiče od činjenice da algoritmi donose odluke bazirane na samo jednom kriterijumu, a ne na globalnoj analizi koja bi uzela u obzir efekat te odluke u budućim koracima. Kao što ćemo videti, takva bektreking analiza će biti nepotrebna u slučaju pohlepnig algoritama, tako da značenje pohlepan nije u smislu uzrokovanja nečeg lošeg radi kratkovremenskog dobitka. Za razliku od bektreking algoritama, pohlepni algoritmi ne mogu da se kreiraju za svaki problem. Nije svaki problem rešiv koristeći pohlepne algoritme. Ako posmatramo traženje rešenja optimizacionog problema kao penjanje uz uspon, pohlepni algoritmi mogu da se koriste samo za ona brda kod kojih će za svaku tačku najstrmiji korak uvek voditi do vrha. Pohlepni algoritmi su jako efikasni i mogu biti implementirani na relativno jednostavan način. U velikom broju slučajeva u O(n) složenosti jer će postojati samo jedan izbor za svaku tačku. Međutim, većina pokušaja da se kreira pohlepan algoritam propadnu ukoliko se najpre ne demonstrira preciza dokaz korektnosti algoritma. Kada pohlepna strategija ne uspe da optimalne rezultate za sve ulaze, premo njoj se odnosimo kao prema heuristici, a ne algoritmu. Heuristike mogu biti korisne kada je brzina važnija od tačnih rezultata (na primer, kada su prihvatljivi „dovoljno dobri“ rezultati).
Problem raspoređivanja događaja uredi
Prvi problem koji ćemo predstaviti, koji može da se reši upotrebom pohlepnog algoritma je problem raspoređivanja događaja. Imamo skup događa koji imaju početni i završni trenutak, i treba da napravimo podskup ovih događaja takav da ni jedan događaj ne preklapa sa nekim drugim (da im se ne preklapaju vremena izvršavanja), i da imamo maksimalan mogući broj događaja u rasporedu. Sledi formalna predstava ovog problema:
ulaz: događaji: skup intervala gde je početni trenutak, a završni trenutak. Rešenje: Skup S Događaja. Ograničenje: Ni jedan događaj ne sme da se preklopi sa nekim drugim. Tj., za sve intervale gde je važi . Cilj: Maksimizovati broj raspoređenih događaja, npr., maksimizovati veličinu skupa S.
Najpre ćemo početi sa bektreking rešewem problema:
// event-schedule -- "заказује" што више могуће не-конфликтних догађаја
function event-schedule(events array of s[1..n], j[1..n]): set
if n == 0: return fi
if n == 1: return {events[1]} fi
let event := events[1]
let S1 := union(event-schedule(events - set of conflicting events), event)
let S2 := event-schedule(events - {event})
if S1.size() >= S2.size():
return S1
else
return S2
fi
end
Algoritam odozgo će naći najveći skup nepreklapajućih događaja. On ignoriše detalje oko računanja skupa preklapajućih događaja, ali je potrebno vremena. Kako algoritam pravi dva rekurzivna poziva samom sebi, svaki sa argumentom veličine , i kako uklanjanje preklapanja zahteva linearno vreme, izraz za vreme koje je potrebno za ovaj algoritam je:
Što je .
Najbolje je pretpostaviti da umesto da biramo samo prvi element u nizu, koristimo neki drugi kriterijum. Cilj je da izaberemo „pravi“ element, tako da nam ne budu potreba dva rekurzivna poziva. Najpre, razmotrimo pohlepnu strategiju biranja najkraćih događaja dok više ne budemo mogli da dodajemo događaje bez preklapanja. Ideja je da kraći događaji imaju manju šansu da se preklapaju sa ostalim događajima. Postoje slučajevi ovakav način biranja događaja daje optimalne rezultate. Međutim, za neke slučajeve ovakva strategija je sub-optimalna:
Na slici iznad, optimalno rešenje je da se izabere događaj A i S, umesto samo V. Možda be umesto da biramo najkraći događaj trebalo da biramo događaj sa najmanjim brojem preklapanja. Ova strategija deluje direktnije ali ne uspeva za ovaj sličaj:
U slučaju odozgo, možemo da maksimiziramo broj događaja biranjem A. B, C, D i E. Međutim, događaji sa najmanjim brojem preklapanja su 6, 2 i 7, 3. Ali biranje jednog od 6, 2 i jednog od 7, 3 znači da ne možemo da biramo B, C i D, što uključuje tri događaja umesto samo dva.
Dijkstrin algoritam najkraće putanje uredi
Sa dve transformacije (visokog nivoa, pseudokod), Dijkstin algoritam se može dobiti iz mnogo manje efikasnog bektreking algoritma. Trik ovde je dokazati da transformacije održavaju korektnost, ali to je ceo pogled u Dijkstrin algoritam. Kako bismo videli kako radi Dijkstrin alggoritam najkraće putanje, pogledaćemo sledeći primer: Postoji početni i krajnji čvor, sa dve putanje između njih; jedna putanja ima težinu 30 na prvom skoku, a zatim 10 na poslednjem skoku ka krajnjem čvoru, sa ukupnom težinom 40. Druga putanja ima težinu 10 na prvom skoku, 10 na drugom skoku i 40 na poslednjem skoku, sa ukupnom težinom 60. Početnom čvoru se dodeljuje distanca nula, tako da on može da bude na početku reda najkraće distance, svim ostalim čvorovima je dodeljena distanca beskonačni ili neki veliki broj, npr. 32767. Ovo čini da početni čvor bude prvi trenutni čvor u redu. U svakoj iteraciji, trenutni čvor je prvi čvor reda najkraće putanje. On gleda na sve čvorove pripojene trenutno čvoru. Za slučaj početnog čvora, u prvoj putanji naći će čvor sa distancom 30, a u drugoj putanji, naći će čvor sa distancom 10. Distanca trenutnog čvora, koja je nula napočetku, se dodaje distancama susednih čvorova i distance od početnog čvora do svakog čvora se ažuriraju, tako da će čvorovi imati 30+0=30 u prvojputanji i 10+0=10 u drugoj putanji. Što je važno, pokazivač na prethodni atribut za svaki čvor se takođe ažurira, tako da će svaki čvor da pokazuje nazad na trenutni čvor, što je početni čvor za ova dva čvora. Prioritet svakog čvora se ažuira u redu prioriteta koristeći novu distancu. Ovim se završava jedna iteracija. Trenutni čvor se uklanja iz reda pre nego što se ispitaju njegovi susedni čvorovi. U sledećoj iteraciji, na početku reda će biti čvor u drugoj putanji, sa distancom 10, i on ima samo jedan susedni čvor sa distancom 10, i distanca tog susedno čvora će biti ažurirana sa 32767 na 10 (distanca trenutnog čvora) +10 (distanca od trenutnog čvora)=20. U sledećoj iteraciji, čvor druge putanje sa težinom 20 će biti ispitan, i on ima jedan susedni skok sa težinom 40 do ciljnog čvora, i distanca ciljnog čvora se ažurira od 32767 do 20+40=60. Prioritet ciljnog čvora je ažuriran. U sledećoj iteraciji, čvor iz najkraće putanje će biti čvor iz prve putanje sa distancom 30, i ciljnii čvor još uvek nije uklonjen iz reda. On je takođe susedan sa ciljnim čvorom sa ukupnom distancom 30+10=40. Kako je 40 manje od 60, prethodno izračunate distance ciljnog čvora, distanca ciljnog čvora se ažurira na 40, a pokazivač na prethodni čvor ciljnog čvora sada pokazuje na čvor u prvoj putanji. U konačnoj iteraciji, čvor najkraće putanje je ciljni čvor i postoji petlja. Gledajući na pokazivače na prethodni čvor, počevši od ciljnog čvora, najkraća putanja se može dobiti kao lista ka početnom čvoru. S obzirom na ovaj primer, koja vrsta strukture podataka je potrebna za čvorove i algoritam?
# author , copyright under GFDL
class Node :
def __init__(self, label, distance = 32767 ):
# користи инициализатор дељење мапе
# , adjacency_distance_map = {} ):
self.label = label
self.adjacent = {} # ово је мапа растојања, са кључевима (чворовима), и вредностима растојања суседа
self.distance = distance # ово је ажурирано растојање од почетног чвора, коришћено као приоритет чвора
self.shortest_previous = None # ово је последње најкраће растојање суседног чвора
# логика је да последње додато растојање суседног чвора буде евидентирано, за било које растојање од истог тог додатог чвора
def add_adjacent(self, local_distance, node):
self.adjacent[node]=local_distance
print "adjacency to ", self.label, " of ", self.adjacent[node], " to ", \
node.label
def get_adjacent(self) :
return self.adjacent.iteritems()
def update_shortest( self, node):
new_distance = node.adjacent[self] + node.distance
#DEBUG
print "for node ", node.label, " updating ", self.label, \
" with distance ", node.distance , \
" and adjacent distance ", node.adjacent[self]
updated = False
# мапа растојања чвора даје растојање суседног чвора за овај чвор
# ново растојање за путању до овог (self)чвора је суседно растојање плус растојање другог чвора
if new_distance < self.distance :
# ако је најкраће растојање, онда евидентирати то растојање и поставити претходни чвор као тај чвор
self.distance = new_distance
self.shortest_previous= node
updated = True
return updated
MAX_IN_PQ = 100000
class PQ:
def __init__(self , sign = -1 ):
self.q = [None ] * MAX_IN_PQ # make the array preallocated
self.sign = sign # a negative sign is a minimum priority queue
self.end = 1 # this is the next slot of the array (self.q) to be used ,
self.map = {}
def insert( self, priority, data):
self.q[self.end] = (priority, data)
# sift up after insert
p = self.end
self.end = self.end + 1
self.sift_up(p)
def sift_up(self, p):
# p је позиција тренутног чвора
# q[p][0] је приоритет, q[p][1] is the item or nodeје елемент или чвор
# док год постоји родитељ ( p >= 1) , приоритет родитеља је мањи од приоритета тренутног чвора
while p / 2 != 0 and self.q[p/2][0]*self.sign < self.q[p][0]*self.sign:
# заменити места родитељу и тренутном чвору, и поставити позицију тренутног чвора као позицију родитеља
tmp = self.q[p]
self.q[p] = self.q[p/2]
self.q[p/2] = tmp
self.map[self.q[p][1]] = p
p = p/2
self.map[self.q[p][1]] = p
return p
def remove_top(self):
if self.end == 1 :
return (-1, None)
(priority, node) = self.q[1]
# поставити крај хипа на врх хипа и шифтовати га доле до суседног хипа
# након што је врх хипа уклоњен. ово узима log2(N) време, где је N величина хипа.
self.q[1] = self.q[self.end-1]
self.end = self.end - 1
self.sift_down(1)
return (priority, node)
def sift_down(self, p):
while 1:
l = p * 2
# ако је позиција левог детеа већа од величине хипа,
# онда лево и десно дете не постоје
if ( l > self.end) :
break
r= l + 1
# изабрано дете треба да има највећи приоритет
t = l
if r < self.end and self.q[r][0]*self.sign > self.q[l][0]*self.sign :
t = r
print "checking for sift down of ", self.q[p][1].label, self.q[p][0], " vs child ", self.q[t][1].label, self.q[t][0]
# ако изабрани чвор са највећим приоритетом има већи приоритет од тренутног чвора
if self.q[t] [0] * self. sign > self.q [p] [0] * self.sign :
# заменити места тренутном чвору са тим чвором који је дете и ажурирати мапирање од чвора који је дете на његову нову позицију
tmp = self. q [ t ]
self. q [ t ] = self.q [ p ]
self. q [ p ] = tmp
self.map [ tmp [1 ] ] = p
p = t
else: break # обуставити замену места ако дете са највећим приоритетом има мањи приоритет од тренутног чвора
# након шифовања, ажурирати позицију тренутног чвора.
self.map [ self.q[p][1] ] = p
return p
def update_priority(self, priority, data ) :
p = self. map[ data ]
print "priority prior update", p, "for priority", priority, " previous priority", self.q[p][0]
if p is None :
return -1
self.q[p] = (priority, self.q[p][1])
p = self.sift_up(p)
p = self.sift_down(p)
print "updated ", self.q[p][1].label , p, "priority now ", self.q[p][0]
return p
class NoPathToTargetNode ( BaseException):
pass
def test_1() :
st = Node('start', 0)
p1a = Node('p1a')
p1b = Node('p1b')
p2a = Node('p2a')
p2b = Node('p2b')
p2c = Node('p2c')
p2d = Node('p2d')
targ = Node('target')
st.add_adjacent ( 30, p1a)
#st.add_adjacent ( 10, p2a)
st.add_adjacent ( 20, p2a)
#p1a.add_adjacent(10, targ)
p1a.add_adjacent(40, targ)
p1a.add_adjacent(10, p1b)
p1b.add_adjacent(10, targ)
# тестирање алтернативе
#p1b.add_adjacent(20, targ)
p2a.add_adjacent(10, p2b)
p2b.add_adjacent(5,p2c)
p2c.add_adjacent(5,p2d)
#p2d.add_adjacent(5,targ)
#бирање алтернативне путање
p2d.add_adjacent(15,targ)
pq = PQ()
# st.distance је 0, али друга имају почетно растојање 32767
pq.insert( st.distance, st)
pq.insert( p1a.distance, p1a)
pq.insert( p2a.distance, p2a)
pq.insert( p2b.distance, p2b)
pq.insert(targ.distance, targ)
pq.insert( p2c.distance, p2c)
pq.insert( p2d.distance, p2d)
pq.insert(p1b.distance, p1b)
node = None
while node != targ :
(pr, node ) = pq.remove_top()
#debug
print "node ", node.label, " removed from top "
if node is None:
print "target node not in queue"
raise
elif pr == 32767:
print "max distance encountered so no further nodes updated. No path to target node."
raise NoPathToTargetNode
# ажурирати растојање од почетног чвора користећи растојање овог чвора до свих суседних чворова, и ажурирати његов приоритет ако је
# краће растојање пронађено за суседни чвор ( .update_shortest(..) враћа true ).
# ово је похлепни део Дијаксртиновог алгоритма, увек похлепан за најкраћа растојања која користе ред са приоритетом.
for adj_node , dist in node.get_adjacent():
#debug
print "updating adjacency from ", node.label, " to ", adj_node.label
if adj_node.update_shortest( node ):
pq.update_priority( adj_node.distance, adj_node)
print "node and targ ", node, targ , node <> targ
print "length of path", targ.distance
print " shortest path"
#креирати обрнуту листу од циљног чвора, кроз најкараће путање чворова до почетног чвора
node = targ
path = []
while node <> None :
path.append(node)
node = node. shortest_previous
for node in reversed(path): # нова верзија итератора од list.reverse()
print node.label
if __name__ == "__main__":
test_1()
Stablo minimalne visine uredi
Pohlepno traženje minimalne težine grana; ovo bi se moglo postići sortiranjem grana u listi u rastućim težinama. Dva poznata algoritma su Primov algoritam i Kruskalov algoritam. Kruskal bira sledeću minimalnu težinu grane, uz uslov da ne postoji ciklus u rezultirajućem i ažuriranom grafu. Primov algoritam bira minimalnu granu uz uslov da je samo jedna grana povezana sa stablom. Za oba algoritma, čini se da najviše posla ima u verifikovanju grane da li odgovara primarnom uslovu. U Krukalovom algoritmu, pretraga i tehnika oznaćavanja bi trebalo da se uradi na grani koja je kandidat. Ovo će rezultirati, u pretrazi bilo kojih povezanih već označenih grana, ako smo naišli na označenu granu,onda se ciklus formirao. U Primovom algoritmu, grana koja je kandidat bi se poredila sa listom trenutno izabranih grana, što bi moglo biti uključeno u broj čvorova u tabeli simbola i ako su oba kraja čvorova pronađena, onda je grana koja je kandidat odbijena.