Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellGraphSearchAproblem:WehaveagraphG=(V,E)andanodes∈V.
Writeu→vifnodeuisreachableinonestep.
"visasuccessorofu".
Ifthegraphisdirectedu→vmeansu=←eandv=→eforsomee∈EIfthegraphisundirectedu→vmeans{u,v}=←→eforsomee∈EWriteu→vtomeanthereisapathfromutov,i.
e.
visreachablefromu.
I.
e.
thereisasequenceofoneormorenodes[v0,v1,.
.
.
,vn]suchthatu=v0→v1→.
.
.
→vn=vTypesetNovember11,20161Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellReachability:GivenagraphGandanodes,ndallnodesreachablefroms.
UsethefollowingcolourschemeHBlacknodes.
Foundandprocessed.
(Handled)WGreynodes.
Foundbutnotprocessedyet.
(Workset)Whitenodes.
Notyetfound.
The'ood'strategy.
Coloursgreyandallothernodeswhite.
Untiltherearenogreynodes:Pickagreynodeu.
Colourublack.
Colourallofu'swhitesuccessorsgrey.
Whentherearenomoregreynodes,allblacknodesarereachableandallwhitenodesarenot.
Invariants:LI1:Allblackorgreynodesarereachable.
LI2:Allsuccessorsofablacknodeareblackorgrey.
LI3:sisblackorgrey.
IfLI2,andLI3aretrueand,furthermore,nonodeisgrey,thenallnodesreachablefromsmustbeblack.
IfLI1,LI2,andLI3aretrueandnonodeisgrey,theblacknodesareexactlythenodesreachablefroms.
TypesetNovember11,20162Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellTheoodalgorithmforreachabilityInputs:agraphG=(V,E)andanodesOutput:asetHVPreconditions∈VPostconditionH={v∈V|s→v}H:=//Handled(black)nodesvarW:={s}//Workset(greynodes)invariantLI1:Allnonwhitenodesarereachable:v∈H∪W·s→vLI2:Ifuisblack,allitssuccessorshavebeenfound:u∈H,v∈V·(u→v)(v∈H∪W)LI3:sisgreyorblack:s∈H∪WLI4:H∩W=whileW=dovalu∈W//letubeanyvalueinWW:=W{u};H:=H∪{u}forv|u→vdoifv/∈H∪WthenW:=W∪{v}endifendforendwhileTypesetNovember11,20163Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellDoesitworkRecalltheinvariantisLI1:Allnodesfoundarereachablev∈H∪W·s→vLI2:Ifuhasbeenhandled,allitssuccessorshavebeenfoundu∈H,v∈V·(u→v)(v∈H∪W)LI3:sisgreyorblacks∈H∪W.
LI4:H∩W=Weneedtoshow:Termination:|V||H|isavariant.
Theinvariantisestablished:Exercise.
Theinvariantispreserved:ExerciseThepostconditionH={v∈V|s→v}isestablishedbytheloopterminating:FromLI1andW=,v∈H·s→vandsoH{v∈V|s→v}Itremainstoshow{v∈V|s→v}H.
·Letvbeanyreachablenodes→v·So,thereisapaths=v0→v1→.
.
.
→vn=v·ByLI3andW=,sisinH.
·ByLI2andW=,u∈H,v∈V·(u→v)v∈H·So,byinduction,eachviisinHandv∈HQEDTypesetNovember11,20164Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellLeavingatrailofbreadcrumbsWewillmarkeachnodereachedwiththenodethatwasusedtoreachit.
LI5:Foranyblackorgreynodeuthereisapathfroms,s=π(.
.
.
π(≥0u)π(π(u))→π(u)→uallnodesofwhich,apartfrompossiblythelast,areblack.
Useafunctionvaluedstatevariableπ:V→V∪{null}(πforπarent).
Whenanodeturnsgrey,updateπTheoodalgorithmforreachabilitywithpathsforv←Vdoπ(v):=nullendforH:=varW:={s}{Inv:LI1andLI2andLI3andL4andLI5}whileW=dovalu∈W//letubeanyvalueinWW:=W{u}H:=H∪{u}forv|u→vdoifv/∈H∪WthenW:=W∪{v};π(v):=uendifendforendwhileTheπfunctiondenesatreewithsatitsroot.
IthastheresultofclassifyingeachreachableedgeasaTreeedge.
TreeedgesformatreedenedbyπBackedge.
Fromdescendanttoancestor.
Forwardedge.
Fromancestortodescendant.
(Otherthantreeedges.
)Crossedge.
AllothersTypesetNovember11,20165Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellTrackingthecolourTomakeexpressionslikev/∈H∪Wfaster,wecantrackthecolourofeachnodewithanarraycolourwithalinkinginvariantthat,forallv∈V,(colour(v)=greyv∈W)∧(colour(v)=blackv∈H)∧(colour(v)=whitev/∈H∪W)Hisnolongerneeded.
Wisstillusefulforndingthenextnodetoprocess.
LI1:v·colour(v)∈{grey,black}s→vLI2:u,v·colour(u)=black∧(u→v)colour(v)∈{grey,black}LI3:colour(s)∈{grey,black}LI4:v·colour(v)=greyv∈WTheoodalgorithmforreachabilitywithcolourarrayforv←Vdoπ(v):=nullcolour(v):=whiteendforvarW:={s}colour(s):=grey{Inv:LI1andLI2andLI3andL4andLI5}whileW=dovalu∈W//letubeanyvalueinWW:=W{u}colour(u):=blackforv|u→vdoifcolour(v)=whitethenW:=W∪{v};colour(v):=greyπ(v):=uendifendforendwhileTypesetNovember11,20166Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellDatareningWWecankeeptrackofthesetofgreynodeswithanykindofcollectiondatastructure:Set,FIFOqueue,stack.
AFIFOqueueQReplaceWwithaFIFOqueueQLI4becomesv·colour(v)=greyQ.
contains(v)Nodesarevisitedina"breadth"rstorder.
Nodesclosertosarehandledearlier.
Eachpathfoundhasasfewedgesaspossible.
Breadthrstsearchforv←Vdoπ(v):=nullcolour(v):=whiteendforvarQ:Queue:=newQueueQ.
add(s)colour(s):=grey{Inv:LI1andLI2andLI3andL4andLI5}whileQ.
isEmptydovalu:=Q.
remove()colour(u):=blackforv|u→vdoifcolour(v)=whitethenQ.
add(v);colour(v):=greyπ(v):=uendifendforendwhileTypesetNovember11,20167Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellEfciencyAtthispoint,wecanseethat,ifwecanquicklyndthesuccessorsofanode,thenprocessingeachedgeisΘ(1).
Eachedgeisprocessedtwice.
HenceΘ(|V|+|E|).
Anadjacencylistrepresentationforthegraphwilldothetrick.
TypesetNovember11,20168Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellALIFOstackSLI4becomesv·colour(v)=greyS.
contains(v)Ifagreynodeisfoundasecond(etc)time,itismovedtothetopofthestack.
Depth-rstsearchforv←Vdoπ(v):=nullcolour(v):=whiteendforvarS:Stack:=newStackS.
push(s)colour(s):=grey{Inv:LI1andLI2andLI3andL4andLI5}whileS.
isEmptydovalu:=S.
pop()colour(u):=blackforv|u→vdoifcolour(v)=blackthen//Notechange!
ifcolour(v)=greythen//Movevtothetopofthestack.
S.
remove(v)endifS.
push(v);colour(v):=greyπ(v):=u//Ifvisgrey,overwritesearlierassignment!
endifendforendwhileWeneedtoimplementthestacksothatanarbirarynodecanberemovedinconstanttime.
Adoubly-linkedlistimplementedwitharrayswilldoit.
TypesetNovember11,20169Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellThisisadepth-rstsearch.
Itfollowspathsleadingawayfromsasfaraspossiblebeforebacktrackingtondotherpaths.
TypesetNovember11,201610Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellDijkstra'salgorithmLet'srevisitthebreadthrstsearchBreadthrstsearchforv←Vdoπ(v):=nullcolour(v):=whiteendforvarQ:Queue:=newQueueQ.
add(s);colour(s):=grey{Inv:LI1andLI2andLI3andL4andLI5}whileQ.
isEmptydovalu:=Q.
remove()colour(u):=blackforv|u→vdoifcolour(v)=whitethenQ.
add(v);colour(v):=greyπ(v):=uendifendforendwhileThisndstheshortestpathfromstoeachreachablenode,countingeachedgeascosting1.
Supposethateachedgeeisassociatedwithanonnegativedistancew(←e,→e).
Wewanttondtheshortestpathfromstoeachreachablenode.
Applicationsareubiquitous,e.
g.
inrobotics,navigation,andplanning.
Lett(u)bethelengthoftheshortestpathfromstou.
t(u)=minp|sp→udistance(p)wheresp→umeansthatpisapathfromstouanddistance([u0,e0,u1,e1,.
.
.
,en1,un])=Σi∈{0,.
.
n}w(ui,ui+1)TypesetNovember11,201611Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellUsearrayitemd(v)totrackthedistanceoftheshortestpathfromstovhandledsofar.
(I.
e.
,thateitherconsistsofallblacknodes,orisallblackexceptforthenalitem.
)Sincewestopassoonasallreachablenodesareblack,weneedDI1:Foreachblacknode,v,d(v)=t(v).
Toensurethatthegreynodewiththesmallestdvaluealsohasthetruedistance,weneedDI2:Foreachgreynode,v,d(v)isthedistanceofsomepathfromstov.
WedatareneWwithapriorityqueuePQ.
Apriorityqueueassociateseachitemwithapriorityvalue.
PQ.
add(v,x)addsnodevwithpriorityxorupdatesthepriorityofvtox.
PQ.
removeLeast()removesandreturnsanodewiththelowestpriority.
InvariantsaboutPQLI4:v·colour(v)=greyPQ.
contains(v)DI3:ThepriorityofeachnodevonPQisd(v).
TypesetNovember11,201612Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellDI1:Foreachblacknode,v,d(v)=t(v).
DI2:Foreachgreynode,v,d(v)isthedistanceofsomepathfromstov.
DI3:ThepriorityofeachnodevonPQisd(v).
AswithDFS,greynodesmaybefoundmorethanonce,sowemightneedtoimprovead(v)Dijkstra'salgorithmforv←Vdoπ(v):=nullcolour(v):=whited(v):=∞endforvarPQ:PriorityQueue:=newPriorityQueuePQ.
add(s,0)colour(s):=greyd(s):=0{Inv:LI1and.
.
.
andLI5andDI1andDI2andDI3}whilePQ.
isEmptydovalu:=PQ.
removeLeast(){uhasthesmallestdvalueofallgreynodes}colour(u):=blackforv|u→vdoifd(v)>d(u)+w(u,v)then{visnotblack,byDI1}d(v):=d(u)+w(u,v)PQ.
add(v,d(v));colour(v):=greyπ(v):=uendifendforendwhileNote:whenPQ.
add(v,d(v))isexecuted,vmayalreadybeonthequeue(grey).
Inthiscase,itspriorityisupdated.
TypesetNovember11,201613Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellTypesetNovember11,201614Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellWeneedtoseethattheinvariantsarepreserved.
DI1:Foreachblacknode,v,d(v)=t(v).
DI2:Foreachgreynode,v,d(v)isthedistanceofsomepathfromstov.
Lemma:IfDI1andDI2hold,then,foranywandanyoptimalpathfromstow,therstgreynodevonthepath(ifany)hasd(v)=t(v).
Proof.
Letvbegreyandtherstgreynodeonsomeoptimalpath.
Ifviss,thend(v)=0=t(s).
Ifvisnots,thensisblack.
Sincethesuccessorofablacknodemustbeblackorgrey,therstgreynodeonanypathstartingatswillbeprecededbyablacknode.
Letubethepredecesorofvonthepath,asuisblack,byDI1d(u)=t(u).
Furthermore,whenuwasvisited,theedgefromutovwouldhavebeenconsideredandsod(v)≤t(u)+w(u,v).
ByDI2,d(v)≥t(v),sod(v)=t(u)+w(u,v),and,since(u,v)isonanoptimalpath,t(v)=t(u)+w(u,v).
Sod(v)=t(v).
DI1ispreserved.
SupposethatDI1andDI2hold,but,atlinecolour(u):=black,udoesnothavea"truevalue"(t(u)GraphSearchcTheodoreNorvellSinceu=uoruisbeforeuonanoptimalpath,t(u)≤t(u).
Altogetherd(u)=t(u)≤t(u)and+withothersuitableoperators.
E.
g.
Ifweightsrepresent(independent)probabilitiesofsuccess,replace>withGraphSearchcTheodoreNorvellEfciencyAssumethepriorityqueueoperationsaddandremovecanbedoneinΘ(logn)timewherenisthesizeofthequeue:WemayneedΘ(|V|)itemsonthequeue,sothealgorithmtakesΘ(|E|*log|V|)time.
Dijkstra'salgorithmhasthepropertythatitcanbemodiedtoprintoutallthenodesinorderoftheirdistancefroms.
Canyoushowthatanyshortestpathalgorithmwiththispropertytakes(|E|*log|V|)timeTypesetNovember11,201617Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellPriorityQueueRepresentationAnefcientpriorityqueuecanbebuiltfromabalancedheap.
AheapisalabelledbinarytreeinwhicheachnodeislabeledwithadataitemandapriorityThepriorityofeachparentislessthanorequaltothepriorityofitschildren.
Westoretheitemsandprioritiesintherstnitemsofanarraya.
Invariant:i∈{0,.
.
n}·(leftExists(i)a(i).
priority≤a(left(i)).
priority)∧(rightExists(i)a(i).
priority≤a(right(i)).
priority)E.
g.
,Note:Onlytheprioritiesareshowninthepictures.
Wealsoneedafunctionmappingeachitemtoitslocationina.
Ifeachitemisrepresentedbyauniquesmallnumberin{0,.
.
m},wecanuseanarraylocsothati∈{0,.
.
n}·loc(a(i).
item.
number)=ij∈{0,.
.
m}·loc(j)=1∨a(loc(j)).
item.
number=jTypesetNovember11,201618Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellArrayrepresentationWecanbuildabalancedheapofsizenbyusingtherstnitemsofanarraya.
Usebreadth-rstnumbering.
Therootisatlocation0.
Invariant:i∈{0,.
.
n}·left(i)=2i+1∧right(i)=2i+2∧leftExists(i)=(2i+1GraphSearchcTheodoreNorvellInsertingintoaheapPutthenewitemata(n);incrementn.
Thenswaptheelementupwardsuntilitspriorityislargerorequaltoitsparent's(orattheroot)(+correspondingchangestoloc)E.
g.
TheworstcaseisΘ(logn)ReducingpriorityofanitemReducethepriorityandthenswapitupwards,justasininsert.
TypesetNovember11,201620Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellRemovingthelowestpriorityitemDecrementn;thena(0):=a(n)(+correspondingchangestoloc).
Swaptheitemnowattherootdownuntilitspriorityislessthanorequaltothatofallitschildren.
Swaponlywithalowestchild.
Thenumberofswapsislimitedtotheheightofthetree.
Θ(logn)TypesetNovember11,201621Algorithms:CorrectnessandComplexity.
Slideset13.
GraphSearchcTheodoreNorvellAnotherapplicationofheapsHeapSort:Input:anarrayasuchthata.
length>0Output:thesamearrayPostconditionaisasortedpermutationofa0varn:=1invaisapermutationofa0anda[0,.
.
n]isaheapwhilen0don:=n1swap(a,0,n)sinkDown(0)endwhilewhereoatUprestorestheheapinvariantbyswappinganitemupwardfromaleafpositionsinkDownrestorestheheapinvariantbyswappinganitemdownwardfromtherootposition.
SinceoatUpandsinkDownarebothΘ(logn)time(wherenisthesizeoftheheap),HeapSortisΘ(nlogn)time(wherenisthesizeofthearray).
(Nolocarrayisneeded.
Weonlyneededitbeforetoreducethepriorityofanitem.
)TypesetNovember11,201622
TmhHost是一家国内正规公司,具备ISP\ICP等资质,主营国内外云服务器及独立服务器租用业务,目前,商家新上香港三网CN2 GIA线路VPS及国内镇江BGP高防云主机,其中香港三网CN2 GIA线路最低每月45元起;同时对美国洛杉矶CN2 GIA线路高防及普通VPS进行优惠促销,优惠后美国洛杉矶Cera机房CN2 GIA线路高防VPS季付99元起。香港CN2 GIA安畅机房,三网回程CN2 ...
目前国内云计算市场竞争异常激烈,尤其是国内的腾讯云、阿里云、景安等商家促销活动一波接一波的进行,对于有需要的用户确实得到不小的实惠。但是这样给予国内的主机商确实是比较大的打击,毕竟这些商家的背景和实例强劲,即便是贴本补贴优惠,也是不怕的。前两年阿里一家各种活动促销,确实在国内市场占据主要的市场地位,腾讯云开始两年没有较大的吸引用户,不过这两年的发展还是比较稳健的。我们很多网友在之前肯定也享受到一些...
raksmart作为一家老牌美国机房总是被很多人问到raksmart香港服务器怎么样、raksmart好不好?其实,这也好理解。香港服务器离大陆最近、理论上是不需要备案的服务器里面速度最快的,被过多关注也就在情理之中了。本着为大家趟雷就是本站的光荣这一理念,拿了一台raksmart的香港独立服务器,简单做个测评,分享下实测的数据,仅供参考!官方网站:https://www.raksmart.com...
graphsearch为你推荐
如何设置浏览器允许弹出窗口regularitygraph伺服器win7支持ipadoutput_buffering飞飞的官方网站是啥windows键是哪个windows 快捷键 大全iphone连不上wifi苹果手机“无法加入网络”怎么办ipad上网为什么我的ipad 显示无法连接到网络xp关闭445端口Windows XP系统 关闭445端口后无法上网,求解?xp系统关闭445端口xp中,如何关闭掉一些没有用的端口,请高手解答?
便宜域名注册 北京服务器租用 香港主机租用 网易域名邮箱 主机 wavecom debian7 eq2 我爱水煮鱼 共享主机 域名和空间 免费全能主机 hkt 丽萨 监控服务器 阿里云免费邮箱 创速 江苏双线 数据湾 xshell5注册码 更多