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

RAKsmart含站群服务器/10G带宽不限流量首月半价

RAKsmart 商家估摸着前段时间服务器囤货较多,这两个月的促销活动好像有点针对独立服务器。前面才整理到七月份的服务器活动在有一些配置上比上个月折扣力度是大很多,而且今天看到再来部分的服务器首月半价,一般这样的促销有可能是商家库存充裕。比如近期有一些服务商挖矿服务器销售不好,也都会采用这些策略,就好比电脑硬件最近也有下降。不管如何,我们选择服务器或者VPS主机要本着符合自己需求,如果业务不需要,...

硅云香港CN2+BGP云主机仅188元/年起(香港云服务器专区)

硅云怎么样?硅云是一家专业的云服务商,硅云的主营产品包括域名和服务器,其中香港云服务器、香港云虚拟主机是非常受欢迎的产品。硅云香港可用区接入了中国电信CN2 GIA、中国联通直连、中国移动直连、HGC、NTT、COGENT、PCCW在内的数十家优质的全球顶级运营商,是为数不多的多线香港云服务商之一。目前,硅云香港云服务器,CN2+BGP线路,1核1G香港云主机仅188元/年起,域名无需备案,支持个...

香港E3-1230v2 16GB 30M 326元/月 数脉科技

官方网站:https://www.shuhost.com/公司名:LucidaCloud Limited尊敬的新老客户:艰难的2021年即将结束,年终辞旧迎新之际,我们准备了持续优惠、及首月优惠,为中小企业及个人客户降低IT业务成本。我们将持续努力提供给客户更好的品质与服务,在新的一年期待与您有美好的合作。# 下列价钱首月八折优惠码: 20211280OFF (每客户限用1次) * 自助购买可复制...

graphsearch为你推荐
传感器安卓4支持ipad支持ipad步骤ioswin10关闭445端口win10家庭版怎么禁用445端口win10关闭445端口在win10 如何关闭445端口的最新相关信息chromeframe有用过 Google Chrome Frame 的吗迅雷下载速度迅雷下载快慢和什么有关ipad无法加入网络为什么我的ipad加入网络没法用杀毒软件免费下载2013排行榜杀毒软件排行榜2015有哪些?
虚拟主机99idc 济南域名注册 成都主机租用 域名抢注工具 187邮箱 5折 linkcloud ubuntu更新源 dropbox网盘 警告本网站美国保护 国外免费全能空间 hostloc 爱奇艺会员免费试用 shopex主机 空间登入 海外空间 论坛主机 photobucket 徐州电信 apnic 更多