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

DMIT(季度$28.88)调整洛杉矶CN2 GIA优化端口

对于DMIT商家已经关注有一些时候,看到不少的隔壁朋友们都有分享到,但是这篇还是我第一次分享这个服务商。根据看介绍,DMIT是一家成立于2017年的美国商家,据说是由几位留美学生创立的,数据中心位于香港、伯力G-Core和洛杉矶,主打香港CN2直连云服务器、美国CN2直连云服务器产品。最近看到DMIT商家有对洛杉矶CN2 GIA VPS端口进行了升级,不过价格没有变化,依然是季付28.88美元起。...

Spinservers:美国圣何塞服务器,双E5/64GB DDR4/2TB SSD/10Gbps端口月流量10TB,$111/月

spinservers怎么样?spinservers大硬盘服务器。Spinservers刚刚在美国圣何塞机房补货120台独立服务器,CPU都是双E5系列,64-512GB DDR4内存,超大SSD或NVMe存储,数量有限,机器都是预部署好的,下单即可上架,无需人工干预,有需要的朋友抓紧下单哦。Spinservers是Majestic Hosting Solutions,LLC旗下站点,主营美国独立...

无法忍受旧版不兼容PHP7+主题 更换新主题

今天父亲节我们有没有陪伴家人一起吃个饭,还是打个电话问候一下。前一段时间同学将网站账户给我说可以有空更新点信息确保他在没有时间的时候还能保持网站有一定的更新内容。不过,他这个网站之前采用的主题也不知道来源哪里,总之各种不合适,文件中很多都是他多年来手工修改的主题拼接的,并非完全适应WordPress已有的函数,有些函数还不兼容最新的PHP版本,于是每次出现问题都要去排查。于是和他商量后,就抽时间把...

graphsearch为你推荐
请仔细阅读在本报告尾部的重要法律声明2011年停止接单产品支持ipadphotoshop技术PS技术是干什么的,如何使用PS技术?ipad连不上wifi苹果ipad突然连不上网了,是怎么回事?网络是好的,手机能上网。勒索病毒win7补丁win7有针对勒索病毒的补丁吗联通版iphone4s联通版iPhone4s 用联通3G卡好还是移动的好googleadsense·什么是Google AdSense?如何加入Google AdSense? 谁可以告诉我吗?chromeframe我的Chrome Frame为什么不能使用?morphvoxpro怎么用morphvox pro和全民k歌怎么用
虚拟主机试用 播放vps上的视频 flashfxp怎么用 便宜服务器 vmsnap3 轻博客 免费个人网站申请 帽子云 河南m值兑换 789电视 老左来了 刀片式服务器 服务器合租 cdn加速是什么 中国网通测速 华为云服务登录 空间登陆首页 徐州电信 登陆qq空间 rewritecond 更多