Abstract. We construct a readable, compact and efficient implementation of Dijkstra’s shortest path algorithm and Fibonacci heaps using Constraint Handling Rules (CHR), which is increasingly used as a high-level rule-based general-purpose programming lang
Thedecrinsoperationcallsdecr/5iftheitemisontheheapandthenewkeyissmallerthantheoriginal.Iftheitemisontheheapbutthenewkeyislarger,itdoesnothing;theitemisinsertedifitisnotontheheap.
doi_d@item(I,O,R,P,M),decr_or_ins(I,K)<=>K<O|decr(I,K,R,P,M).
doi_nop@item(I,O,_,_,_)\decr_or_ins(I,K)<=>K>=O|true.
doi_insert@decr_or_ins(I,K)<=>insert(I,K).
Whenakeyisdecreased,wemayhavefoundanewminimum:
d_min@decr(I,K,_,_,_)==>min(I,K).
Decreasingthekeyofarootcannotcauseaviolationoftheheaporder:
d_root@decr(I,K,R,0,_)<=>item(I,K,R,0,u).
Ifthenewkeyisnotsmallerthantheparent’skey,thereisalsonoproblem:
d_ok@item(P,PK,_,_,_)\decr(I,K,R,P,M)<=>K>=PK|item(I,K,R,P,M).
Otherwise,wecuttheviolatingnodeandmakeitanewroot.Theoriginalparentismarkedtoindicatethatithaslostachild.
d_prob@decr(I,K,R,P,M)<=>item(I,K,R,0,u),mark(P).
Toobtainthedesiredtimecomplexity,wehavetomakesurethatwhena(non-root)nodelosestwoofitschildrenthroughcuts,itgetscutaswell.Thisiscalledacascadingcut.Nodesaremarkedtokeeptrackofwheretomakecascadingcuts.Themarkconstraintdecreasestherankofanodeandmarksitifnecessary.Arootnodeisnevermarked,anunmarkednodebecomesmarked,andanalreadymarkednodeiscutanditsparentismarked(cascadingcut):
m_rt@mark(I),item(I,K,R,0,_)<=>item(I,K,R-1,0,u).
m_u@mark(I),item(I,K,R,P,u)<=>item(I,K,R-1,P,m).
m_m@mark(I),item(I,K,R,P,m)<=>item(I,K,R-1,0,u),mark(P).
Thisconcludesthealgorithm.Figure2liststhefullCHRprogram.Foroptimization,apragmapassivecompilerdirectivewasaddedtorulec2r,themrulewasaddedandthesamerulewasreformulatedwithoutguard.
4TimeComplexity
ToobtainthedesiredO(m+nlogn)timecomplexity,wedependonsomeCHRimplementationproperties,similartotheassumptionsinSection6.2of[20].Speci cally,werequireconstraintstorestoallowconstanttimeinsertion,deletion,andlook-uponarbitraryargumentpositions.
4.1E ciencyofconstraintstores
Wehaveaddedtypeandmodedeclarationstoallowtheuseofmoree cientconstraintstoredatastructures,satisfyingtheaboveassumption.Optionalmodedeclarationswere rstintro-ducedin[20].Weusetheextendedconstraintdeclarationsyntaxproposedin[22],aslistedinFigures1and2.Sinceallstoredconstraintsare(declared)ground,allowingconstanttimelook-upsusinghash-tablesconstraintstores,theK.U.LeuvenCHRsystem[19]realizesalloftheaboveproperties.
Thecrucialargumentpositionsforwhichconstanttimelook-upsarenecessaryarethe rstargumentofedge/3,the rstargumentofdistance/2,andthe rstandfourthargumentofitem/5.Constanttimelook-upsontheseargumentscanbeimplementedusinghash-tablecon-straintstores.Wecanimprovetheconstantfactorsoftheconstraintstoreoperationsbyusing
Dijkstra’s algorithm wi... 16页 免费 Dijkstra... Meeting 11 October 4, 2005 Fibonacci Heaps The...cost applied to an initially empty Fibonacci heap...
Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....
Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....
热门文档