formgraph

graphsearch  时间:2021-02-11  阅读:()
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

cyun29元/月,香港CN2 GIA云服务器低至起;香港多ip站群云服务器4核4G

cyun怎么样?cyun蓝米数据是一家(香港)藍米數據有限公司旗下品牌,蓝米云、蓝米主机等同属于该公司品牌。CYUN全系列云产品采用KVM架构,SSD磁盘阵列,优化线路,低延迟,高稳定。目前,cyun推出的香港云服务器性价比超高,香港cn2 gia云服务器,1核1G1M/系统盘+20G数据盘,低至29元/月起;香港多ip站群云服务器,16个ip/4核4G仅220元/月起,希望买香港站群服务器的站长...

香港 1核 1G 5M 22元/月 美国 1核 512M 15M 19.36元/月 轻云互联

轻云互联成立于2018年的国人商家,广州轻云互联网络科技有限公司旗下品牌,主要从事VPS、虚拟主机等云计算产品业务,适合建站、新手上车的值得选择,香港三网直连(电信CN2GIA联通移动CN2直连);美国圣何塞(回程三网CN2GIA)线路,所有产品均采用KVM虚拟技术架构,高效售后保障,稳定多年,高性能可用,网络优质,为您的业务保驾护航。官方网站:点击进入广州轻云网络科技有限公司活动规则:用户购买任...

星梦云60元夏日促销,四川100G高防4H4G10M,西南高防月付特价

星梦云怎么样?星梦云好不好,资质齐全,IDC/ISP均有,从星梦云这边租的服务器均可以备案,属于一手资源,高防机柜、大带宽、高防IP业务,一手整C IP段,四川电信,星梦云专注四川高防服务器,成都服务器,雅安服务器 。官方网站:点击访问星梦云官网活动方案:1、成都电信年中活动机(封锁UDP,不可解封):机房CPU内存硬盘带宽IP防护流量原价活动价开通方式成都电信优化线路4vCPU4G40G+50...

graphsearch为你推荐
directional163请务必阅读正文之后的免责条款部分Intentsandroid支持ipad支持ipadCTios更新iphoneipad如何上网IPAD4怎样上网?iphone连不上wifi为什么苹果手机连不上wifi微信都发不出去?tcpip上的netbios禁用tcp/ip上的netbios对网络应用软件的正常运行有没有影响?
踢楼 便宜服务器 免费主机 外国服务器 香港cdn 美国便宜货网站 12306抢票攻略 申请空间 e蜗 空间出租 admit的用法 徐正曦 umax120 drupal安装 网页加速 测速电信 阿里云邮箱个人版 存储服务器 免费主页空间 asp空间 更多