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
最近我们是不是在讨论较多的是关于K12教育的问题,培训机构由于资本的介入确实让家长更为焦虑,对于这样的整改我们还是很支持的。实际上,在云服务器市场中,我们也看到内卷和资本的力量,各大云服务商竞争也是相当激烈,更不用说个人和小公司服务商日子确实不好过。今天有看到UCloud发布的夏季促销活动,直接提前和双十一保价挂钩。这就是说,人家直接在暑假的时候就上线双十一的活动。早年的双十一活动会提前一周到十天...
云雀云(larkyun)当前主要运作国内线路的机器,最大提供1Gbps服务器,有云服务器(VDS)、也有独立服务器,对接国内、国外的效果都是相当靠谱的。此外,还有台湾hinet线路的动态云服务器和静态云服务器。当前,larkyun对广州移动二期正在搞优惠促销!官方网站:https://larkyun.top付款方式:支付宝、微信、USDT广移二期开售8折折扣码:56NZVE0YZN (试用于常州联...
一般大厂都是通过首年才有可以享受爆款活动,然后吸引我们注册他们商家达到持续续费和购买的目的。一般只有大厂才能有这样的魄力和能力首年亏本,但是对于一般的公司和个人厂家确实难过,这几年确实看到不少的同类商家难以生存。这里我们可以看到有对应的套餐方案。不过这两个套餐都是100%CPU独享的,不是有某云商家限制CPU的。但是轻量服务器有个不好的就是带宽是较大且流量是限制的额,分别是1GB和1.2TB月流量...
graphsearch为你推荐
"2014年全国民营企业招聘会现场A区域企业信息",,,,solutionssb支持ipad模式ios8甘肃省政府采购ipadwifiipad插卡版和wifi版有什么区别,价格差的多么?itunes备份怎样用itunes备份iphonetcpip上的netbiostcpip上的netbios是什么用的,有安全隐患吗?开启还是关上micromediawww.macromedia.com 是什么网站googleadsense如何通过Google adsense???
xenvps 域名备案只选云聚达 174.127.195.202 mobaxterm 抢票工具 日志分析软件 eq2 qq数据库 南昌服务器托管 150邮箱 jsp空间 河南m值兑换 网站木马检测工具 卡巴斯基试用版 可外链相册 tna官网 免费智能解析 网通服务器托管 ftp免费空间 789电视剧 更多