Алгоритми/"Похлепни" алгоритми
Код бектрекинг алгоритама које смо видели, наишли смо на алгоритме који су нашли тачку одлуке и затим вршили рекурзију преко свих опција из те тачке одлуке. Похлепан алгоритам, може да се посматра као бектрекинг алгоритам код кога је за сваку тачку одлуке „најбоља опција“ већ позната па може да се изабере без потребе за рекурзијом преко било које алтернативне опције. Назив „похлепан“ потиче од чињенице да алгоритми доносе одлуке базиране на само једном критеријуму, а не на глобалној анализи која би узела у обзир ефекат те одлуке у будућим корацима. Као што ћемо видети, таква бектрекинг анализа ће бити непотребна у случају похлепниг алгоритама, тако да значење похлепан није у смислу узроковања нечег лошег ради кратковременског добитка. За разлику од бектрекинг алгоритама, похлепни алгоритми не могу да се креирају за сваки проблем. Није сваки проблем решив користећи похлепне алгоритме. Ако посматрамо тражење решења оптимизационог проблема као пењање уз успон, похлепни алгоритми могу да се користе само за она брда код којих ће за сваку тачку најстрмији корак увек водити до врха. Похлепни алгоритми су јако ефикасни и могу бити имплементирани на релативно једноставан начин. У великом броју случајева у O(n) сложености јер ће постојати само један избор за сваку тачку. Међутим, већина покушаја да се креира похлепан алгоритам пропадну уколико се најпре не демонстрира прециза доказ коректности алгоритма. Када похлепна стратегија не успе да оптималне резултате за све улазе, премо њој се односимо као према хеуристици, а не алгоритму. Хеуристике могу бити корисне када је брзина важнија од тачних резултата (на пример, када су прихватљиви „довољно добри“ резултати).
Проблем распоређивања догађаја
[уреди]Први проблем који ћемо представити, који може да се реши употребом похлепног алгоритма је проблем распоређивања догађаја. Имамо скуп догађа који имају почетни и завршни тренутак, и треба да направимо подскуп ових догађаја такав да ни један догађај не преклапа са неким другим (да им се не преклапају времена извршавања), и да имамо максималан могући број догађаја у распореду. Следи формална представа овог проблема:
улаз: догађаји: скуп интервала где је почетни тренутак, а завршни тренутак. Решење: Скуп S Догађаја. Ограничење: Ни један догађај не сме да се преклопи са неким другим. Тј., за све интервале где је важи . Циљ: Максимизовати број распоређених догађаја, нпр., максимизовати величину скупа 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
Алгоритам одозго ће наћи највећи скуп непреклапајућих догађаја. Он игнорише детаље око рачунања скупа преклапајућих догађаја, али је потребно времена. Како алгоритам прави два рекурзивна позива самом себи, сваки са аргументом величине , и како уклањање преклапања захтева линеарно време, израз за време које је потребно за овај алгоритам је:
Што је .
Најбоље је претпоставити да уместо да бирамо само први елемент у низу, користимо неки други критеријум. Циљ је да изаберемо „прави“ елемент, тако да нам не буду потреба два рекурзивна позива. Најпре, размотримо похлепну стратегију бирања најкраћих догађаја док више не будемо могли да додајемо догађаје без преклапања. Идеја је да краћи догађаји имају мању шансу да се преклапају са осталим догађајима. Постоје случајеви овакав начин бирања догађаја даје оптималне резултате. Међутим, за неке случајеве оваква стратегија је суб-оптимална:
На слици изнад, оптимално решење је да се изабере догађај А и С, уместо само В. Можда бе уместо да бирамо најкраћи догађај требало да бирамо догађај са најмањим бројем преклапања. Ова стратегија делује директније али не успева за овај сличај:
У случају одозго, можемо да максимизирамо број догађаја бирањем A. B, C, D и Е. Међутим, догађаји са најмањим бројем преклапања су 6, 2 и 7, 3. Али бирање једног од 6, 2 и једног од 7, 3 значи да не можемо да бирамо Б, C и D, што укључује три догађаја уместо само два.
Дијкстрин алгоритам најкраће путање
[уреди]Са две трансформације (високог нивоа, псеудокод), Дијкстин алгоритам се може добити из много мање ефикасног бектрекинг алгоритма. Трик овде је доказати да трансформације одржавају коректност, али то је цео поглед у Дијкстрин алгоритам. Како бисмо видели како ради Дијкстрин алггоритам најкраће путање, погледаћемо следећи пример: Постоји почетни и крајњи чвор, са две путање између њих; једна путања има тежину 30 на првом скоку, а затим 10 на последњем скоку ка крајњем чвору, са укупном тежином 40. Друга путања има тежину 10 на првом скоку, 10 на другом скоку и 40 на последњем скоку, са укупном тежином 60. Почетном чвору се додељује дистанца нула, тако да он може да буде на почетку реда најкраће дистанце, свим осталим чворовима је додељена дистанца бесконачни или неки велики број, нпр. 32767. Ово чини да почетни чвор буде први тренутни чвор у реду. У свакој итерацији, тренутни чвор је први чвор реда најкраће путање. Он гледа на све чворове припојене тренутно чвору. За случај почетног чвора, у првој путањи наћи ће чвор са дистанцом 30, а у другој путањи, наћи ће чвор са дистанцом 10. Дистанца тренутног чвора, која је нула напочетку, се додаје дистанцама суседних чворова и дистанце од почетног чвора до сваког чвора се ажурирају, тако да ће чворови имати 30+0=30 у првојпутањи и 10+0=10 у другој путањи. Што је важно, показивач на претходни атрибут за сваки чвор се такође ажурира, тако да ће сваки чвор да показује назад на тренутни чвор, што је почетни чвор за ова два чвора. Приоритет сваког чвора се ажуира у реду приоритета користећи нову дистанцу. Овим се завршава једна итерација. Тренутни чвор се уклања из реда пре него што се испитају његови суседни чворови. У следећој итерацији, на почетку реда ће бити чвор у другој путањи, са дистанцом 10, и он има само један суседни чвор са дистанцом 10, и дистанца тог суседно чвора ће бити ажурирана са 32767 на 10 (дистанца тренутног чвора) +10 (дистанца од тренутног чвора)=20. У следећој итерацији, чвор друге путање са тежином 20 ће бити испитан, и он има један суседни скок са тежином 40 до циљног чвора, и дистанца циљног чвора се ажурира од 32767 до 20+40=60. Приоритет циљног чвора је ажуриран. У следећој итерацији, чвор из најкраће путање ће бити чвор из прве путање са дистанцом 30, и циљнии чвор још увек није уклоњен из реда. Он је такође суседан са циљним чвором са укупном дистанцом 30+10=40. Како је 40 мање од 60, претходно израчунате дистанце циљног чвора, дистанца циљног чвора се ажурира на 40, а показивач на претходни чвор циљног чвора сада показује на чвор у првој путањи. У коначној итерацији, чвор најкраће путање је циљни чвор и постоји петља. Гледајући на показиваче на претходни чвор, почевши од циљног чвора, најкраћа путања се може добити као листа ка почетном чвору. С обзиром на овај пример, која врста структуре података је потребна за чворове и алгоритам?
# 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()
Стабло минималне висине
[уреди]Похлепно тражење минималне тежине грана; ово би се могло постићи сортирањем грана у листи у растућим тежинама. Два позната алгоритма су Примов алгоритам и Крускалов алгоритам. Крускал бира следећу минималну тежину гране, уз услов да не постоји циклус у резултирајућем и ажурираном графу. Примов алгоритам бира минималну грану уз услов да је само једна грана повезана са стаблом. За оба алгоритма, чини се да највише посла има у верификовању гране да ли одговара примарном услову. У Крукаловом алгоритму, претрага и техника ознаћавања би требало да се уради на грани која је кандидат. Ово ће резултирати, у претрази било којих повезаних већ означених грана, ако смо наишли на означену грану,онда се циклус формирао. У Примовом алгоритму, грана која је кандидат би се поредила са листом тренутно изабраних грана, што би могло бити укључено у број чворова у табели симбола и ако су оба краја чворова пронађена, онда је грана која је кандидат одбијена.