Chapter—AnEfficientSearchingWhatwehaveknownafterpreviousAsubclassofintractableproblemshavebeenstudied,commonlyreferredtoastheclassof pleteproblems.TheClassTheClass?? pleteProblems??CowithThreeusefulOne,Suitableforthoseproblemsthatexhibitgoodaveragetimecomplexity,butforwhichtheworstcasepolynomialtimesolutionisexclusive.Thismethodologyisbasedonamethodicexaminationoftheimplicitstatespaceinducedbytheprobleminstanceunderstudy.Intheprocessofexploringthestatespaceoftheinstance,somepruningtakesplace.Two,basedontheprobabilisticnotionofThree,usefulforincrementalsolutionswhereoneiswillingtocompromiseonthequalityofsolutioninreturnforfaster(polynomialtime)solutions.ContentsofcurrentThe3-coloringThe8-queensTeralbacktrackingSubofsubsetHamiltoncycleBranchandTSPInmanyrealworldproblems,asinmostoftheNP-hardproblems,asolutioncanbeobtainedbyexhaustivelysearchingthroughalargebutfinitenumberofMoreover,forvirtuallyalltheseproblems,theredoesnot gorithmthatusesamethodotherthanexhaustiveHowtodevelopsystematictechniquesofsearching?Andhowtocutdownthesearchspacetopossiblyamuch 回回溯自某個有窮集Si通常,所求解的問題需要求取一個使某一個規(guī)范顯式約束限定每個x只從一個給定的集合上取值,滿足顯隱式約束規(guī)定解空間中那些實際上滿足規(guī)范函數(shù)的元組,因此問題的求解方法假定集合Si的大小為mi，于是就有mm1m2mn個n-那么就將可能要測試的mi+1mi+2…mn個向量一概略去。問問題舉顯示約束上），子集和數(shù)問題：已知n+1個正整數(shù)：w1,w2,…,wn顯示約束：xi{j|j是一個整數(shù)且1jnM；為避免子集重復(fù)，要求xi<xi+1子集和數(shù)問題：已知n+1個正整數(shù)：w1,w2,…,wnxi{0,11in。如果沒有選擇wi，則xi＝0，否則顯示約束：xi{0，1樹中的每個結(jié)點確定所求解問題的一個問題狀態(tài)狀態(tài)空間.解狀態(tài)是這樣一些問題狀態(tài)S,根到S答案狀態(tài)對于這些解狀態(tài)而言,由根到S解空間的樹結(jié)構(gòu)成為狀態(tài)空間樹狀態(tài)空間樹=>問題問題狀態(tài)的生成從根結(jié)點開始生成其它結(jié)點活結(jié)點如果已生成一個結(jié)點而它的兒子結(jié)點還沒有全問題狀態(tài)的生成方再次成為E-結(jié)點.使用限界函數(shù)的深度優(yōu)先結(jié)點生成方法稱法,棧方法)Thisalgorithmdesigntechniquecanbedescribedasanorganizedexhaustivesearchwhichoftenavoidssearchingallpossibilities．解空間樹結(jié)構(gòu)4－皇后問解不定長表示的子集和數(shù)問解定長表示的子集和數(shù)問The3-ColoringProblemGivenanundirectedgraphG=(V,E),itisrequiredtocoloreachvertexinVwithoneofthreecolors,say1,2,and3,suchthatnotwoadjacentverticeshavethesameAcoloringcanberepresentedbyann-tuple（c1,c2,cn）suchthatci∈｛1,2,3｝,Forexample,(1,2,2,3,1)denotesacoloringofagraphwithfivevertices．Thereare3npossiblecolorings（legalandillegal）tocoloragraphwithnvertices. SearchThesetofallpossiblecoloringscanberepresentedbyacompleteternarytreecalledthesearchtree．EachpathfromtheroottoaleafnoderepresentsonecoloringThesearchtreeforallpossible3-coloringsforagraphwith3verticesBacktracking:PartialColoringPartial:An pletecoloringofagraphispartialifnotwoadjacentcoloredverticeshavethesamecolor.Idea:Backtrackingworksbygeneratingtheunderlyingtreeonenodeatatime.Ifthelengthofthepathfromtheroottothecurrentnodeislessthannandthecorrespondingcoloringispartial,thenonechildofthecurrentnodeisgeneratedandismarkedasthecurrentnode.If,ontheotherhand,thecorrespondingpathisnotpartial,thenthecurrentnodeismarkedasadeadnodeandanewnodecorrespondingtoanothercoloris aabcdeFinda Wehavearrivedatthesolutionaftergeneratingonly10nodesoutofthe364nodescomprisingthesearchtree.Thenodesaregeneratedinadepth-first- Thereisnoneedtostorethewholesearchtree;weonlyneedtostorethepathfromtheroottothecurrentactivenode.Infact,nophysicalnodesaregeneratedatall;thewholetreeisimplicit.Inaboveexample,weonlyneedtokeeptrackofthecolorassignment.Algorithm13.13-Input:AnundirectedgraphOutput:A3-coloringc[1..n]oftheverticesofG,whereeachc[j]1,2orfork1toendifflagthenoutputelseoutput“noProcedureforcolor=1toifcisalegalcoloringthensetflagtrueandelseifcispartialthenendAlgorithm13.23-Input:AnundirectedgraphOutput:A3-coloringc[1..n]oftheverticesofG,whereeachc[j]1,2orfork1toendwhilekwhilec[k]ifcisalegalcoloringthensetflagtrueandfromthetwowhileelseifcispartialthenkk+1endkk-endifflagthenoutput16elseoutput“no Astothetimecomplexityofthesetwoalgorithms,wenotethatO(3n)nodesaregeneratedintheworstcase.Foreachgeneratednode,O(n)workisrequiredtocheckifthecurrentcoloringislegal,partial,orneither.Hence,theoverallrunningtimeisO(n3n)intheworstcase.Thespacecomplexityis Then-Queensn-QueensProblemdescriptionHowcanwearrangenqueensonanchessboard(n≥1)sothatnotwoqueensattackeachTwoqueenscanattackeachotheriftheyareinthesamerow,columnordiagonal. The4-QueensForthe4-queensproblem,sincenotwoqueenscanbeplacedinthesamerow,eachqueenisinadifferentrow.Sincetherearefourpositionsineachrow,thereare44possibleconfigurations.Eachpossibleconfigurationcanbedescribedbyavectorwithfourcomponentsx=Infact,sincenotwoqueenscanbeplacedinthesamecolumn,alegalplacementcorrespondstoapermutationofthenumbers1,2,3and4.Thisreducesthesearchspacefrom44to AnThevector Thepartialvector AttackEachSuppose:thesolutionisrepresentedbySinceeachrowplaceonequeen,twoqueencannotplaceinthesamerow;Iftwoqueensiandjareplacedinthesamecolumn,theyattackeachother.Inthiscase,Iftwoqueensiandjareplacedinthesamediagonal,theyattackeachother.Inthiscase,xi-xj=i-jorxi-xj=j-Algorithm13.34-QUEENS(iterative)Input:none.Output:Avectorx[1..4]correspondingtothesolutionofthe4-queensfork1tox[k]0{noqueensareplacedontheendwhilekwhilex[k]

ifxisalegalplacementthensetflagtrueandexitfromthetwoelseifxispartialthenkk+1endendifflagthenoutputelseoutput“noAnexample:4-QueensProblem1X1XX2XXXX12X3XXXX1212XX1XXX23XX4Finda Now,considerabrute-forcemethodtosolveteralqueensSincenotwoqueenscanbeplacedinthesamecolumn,thesolutionvectormustbeapermutationofthenumbers1,2,…,n.Thus,thebrute-forcemethodcanbeimprovedtotestn!configurationsinsteadofnn.Considerthe(n-2)!Vectorscorrespondingtothoseconfigurationsinwhichthefirsttwoqueensareplacedinthefirstcolumn.Thebrute-forcemethodblindlytestsallthesevectors,whereasinbacktrackingmethodtosolvethen-queensproblemcostsO(nn)intheworstcase,itempiricallyfarexceedstheO(n!)brute-forcemethodinefficiency,asitsexpectedrunningtimeisgenerallymuchTeralbacktrackingRepresentationof eralbacktrackingalgorithmasasystematic ethodcanbeappliedtoaclassofsearchproblemswhosesolutionconsistsofavector(x1,x2,...,xi)satisfyingsomepredefinedconstraints.Hereiissomeintegerbetween0andn,wherenisconstantthatisdependentontheproblemformulation.Inthetwoalgorithmswehavecovered,3-COLORINGandthen-QUEENsproblems,iwasfixed.However,insomeproblemsimayvaryfromsolutiontoExample:fixedandvariablelengthofGivenasetofnintegersX={x1,x2,...,xn}andanintegery,findsubsetYofXwhosesumisequaltoy.ForinstanceifX{10,20,30,40,80,60}andy=VariablelengthofThreesolutionsofdifferentFixedlengthofThesolutionisaBooleanvectoroflengthnintheBasicideaofInbacktracking,eachxiinthesolutionvectorbelongstofiniinearlyorderedsetThus,thebacktrackingalgorithmconsiderstheelementsofcartesianproductX1X2…Xninlexicographic Initially,thealgorithmstartswiththeemptyvector.Itthenchoosestheleas ementofX1asx1.If(x1)isapartialsolution,thealgorithmproceedsbychoosingtheleas ofX2asx2.If(x1,x2)isapartialsolution,thentheleastelementofX3isincluded;otherwisex2issettothenextelementinX2.Ingeneral,supposethatthealgorithmhasdetectedthepartialsolution(x1,x2,…,xj).ItthenconsidersthevectorBasicideaofbacktrackingIfvrepresentsafinalsolutiontotheproblem,thealgorithmrecordsitasasolutionandeitherterminatesincaseonlyonesolutionisdesiredorcontinuestofindothersolutions.(Theadvancestep).Ifvrepresentsapartialsolution,theadvancedbychoosingthe ementinthesetIfvisneitherafinalnorapartialsolution,wehavetwoIftherearestillmoreelementstochoosefromintheXj+1,thealgorithmsetsxj+1tothenextmemberof(Thebacktrackstep).IftherearenomoreelementstochoosefrominthesetXj+1,thealgorithmbacktracksbysettingxjtothenextmemberofXj.IfagaintherearenomoreelementstochoosefrominthesetofXj,thealgorithmbacktracksbysettingXj-1tothenextmemberofXj-1,andsoAlgorithm13.4Input:ExplicitorimplicitdescriptionofthesetsOutput:Asolutionvectorv=(x1,x2,…,xi),0iifflagthenoutputelseoutput“noProcedureforeachxxkx;appendxktoifvisafinalsolutionthensetflagtrueandelseifvispartialthenendAlgorithm13.5Input:ExplicitorimplicitdescriptionofthesetsOutput:Asolutionvectorv=(x1,x2,…,xi),0iwhilekwhileXkisnot ementinXk;appendxktoifvisfinalsolutionthensetandexitfromthetwowhile elseifvispartialthenkk+1endResetXksothatthe ementisthekk-endifflagthenoutputelseoutput“no子集和數(shù)問已知n+1個正數(shù):wi,(1in),和M要求找出wi的和數(shù)是M解的表示形式采用定長元組:解為n元組(X1,X2,…,Xn其中Xi表取01表示wi約束條件：并設(shè)定wi(1in)按非降次序排列nw(i)x(i)限界函Bk(x(1),…x(k))=true當(dāng)且僅當(dāng) w(i)x(i)

ik

w(i)假定wi已經(jīng)按照非降次序排列則可以強(qiáng)化限界函數(shù)如果下式成立,Bk(x(1),…x(k))為假:kw(i)x(i)

1),Bk(x(1),…x(k))=true當(dāng)且僅當(dāng) w(i)x(i)

ik

w(i)M并且w(i)x(i)w(k1)AlgorithmInput:w[1,2,…n]andM,w[i]>0,MOutput:Asolutionvectorx[1,2,…,n],whereeachx[i]is0orfork1toends0;rIfrMthenSUBOFSUB(s,1,r)ifflagthenoutputelseoutput“noendProcedureSUMOFSUBx[k]if //xisalegalthensetflagtrueandif //xis thenSUMOFSUB(s+w[k],k+1,r-endendifs+r-w[k]Mand thenx[k]0,SUMOFSUB(s,k+1,r-end

環(huán) 環(huán):設(shè)G=(V,E)是一個n結(jié)點的連通圖.一個 找出一個圖 解的表示x1,…,xn)表示解,其中,xi是找到的環(huán)中第i個被訪約束x(1)=1,如果1<k<n,則x(k)可以是不同于x(1),…,x(k-1)AlgorithmInput:AnundirectedgraphOutput:Asolutionvectorx[1,2,…,n],wherex[i]isthenumberofithvisitednode,fork1toendifflagthenoutputelseoutput“noendProcedurewhile //assignifx[k]=0thenexitendifk=nthenflagtrueandelseendendwhilex[k]=x[k]+1mod(n+1)ifx[k]=0thenexitendififGRAPH(x[k-1],x[k])thenforj=1tok-1doifx[j]=x[k]thenexitendforifj=kthenifk<nor(k=nandGRAPH(x[n],1))thenexitendifBranchand檢索策略分為FIFO(firstinfirstout)檢索:類似于BFS的狀態(tài)空間檢索,活結(jié)點表采用一張先進(jìn)先出表(隊列LIFO(lastinfirstout)檢索:類似于D-檢索的狀態(tài)空間檢索,的活結(jié)點表是一張后進(jìn)先出表(棧LC-例子：4－皇后問題的FIFO分枝限1

FIFO/LIFO方法的缺解決對活結(jié)點使用一個“有智力的”排序函數(shù)c(.)來選稱為E-結(jié)點,從而可以加快到達(dá)一個答案結(jié)點的檢索速(1)在生成一個答案結(jié)點之前,子樹X需要生成的結(jié)點數(shù)(2)子樹X中離X最近的那個答案結(jié)點到X的路徑長度成本函結(jié)點成本函數(shù)c(.)定義如下的復(fù)雜度,這是因為計算一個結(jié)點的代價通常要檢索包含一個答案結(jié)點的子樹X才能確定而這正是解決此問題所要做的工作因此要得到精確解決：定義新的成本估計函數(shù):?(X).函數(shù)強(qiáng)使算法優(yōu)先選擇更近答案結(jié)點但又離根較近的結(jié)點LC-檢解決估計函數(shù)）但單純使用?(.)會導(dǎo)致算法偏向于做縱深檢查定義新的成本估計函數(shù):?(X)=f(h(X)+?(X)).其中,?(X)是由X到達(dá)一個案結(jié)點所需做的附加工作的估計函數(shù);h(X)是由根結(jié)點到結(jié)點X的本.f(.)是一個非降函數(shù).f函數(shù)強(qiáng)使算法優(yōu)先選擇更靠近答案結(jié)點但有根較近的結(jié)LC-檢索:選取下一個E-結(jié)點的檢索策略總是選取?(.)值最小的活結(jié)為下一個E-結(jié)點.稱為最小成本檢索,簡稱為LC-檢索LC分枝-限界檢索:伴之有限界函數(shù)的LC-檢索稱為LC分枝-限界檢索15-15-謎問題(例子4456789 目標(biāo)狀態(tài)是否可由初始狀態(tài)到達(dá)(即目標(biāo)狀給棋盤的方格編上1～16的，位置i是設(shè)LESS(i)是使牌j小于牌i1234123456897上右上右左下右 9107右 9107下8 9107左 9107下左上下4 89107 910左下左上4 9107 91011下563897456897456789右左下44234567856785678999456897 579下4568975252946876789454538563897974568689797DFS檢1234568975123456897563897563897856397下左 39左 39107下56397639785639上 4上 49103右 49103下85856936493715-謎問題的LC-檢成本函數(shù)c(.從根出發(fā)到最近目標(biāo)結(jié)點路徑上的每f(X)是由根到結(jié)點X的路徑的長度X)XX估計。它至少應(yīng)是能把狀態(tài)X轉(zhuǎn)換成目標(biāo)狀態(tài)所需的最小移?(X)=不在其目標(biāo)位置的非空白牌數(shù)可以看出?(X)是c(X)的下界1234123456897

LC-檢上右 上右左下5638563897

4568456897

上下4567上下456789

左左右456789右456789下456789456897234567894564567986789LC-檢索的一般過LC-檢索與FIFOLIFO的區(qū)別在于得到下一個E-結(jié)點的c(.):狀態(tài)空間樹T中結(jié)點的成本函數(shù)c(X)是其根為X的子樹中任一答案結(jié)點的最小成本;c(T)是T中最小成本通常不可能找到如上定義的易于計算的c?(.)一般易于計算且有如下性質(zhì)如果X點或是一個葉子結(jié)點則有c(X)=AlgorithmLC-Input:狀態(tài)空間樹T,T中結(jié)點的估計成本函數(shù)?Output:問題的解（從根到答案結(jié)點的路徑ifT是答案節(jié)點then輸出TandreturnendET//E-結(jié)將活結(jié)點表初始為forE的每個兒子ifX是答案結(jié)點輸出從X到T的路徑, endcallADD(X)//將新的活結(jié)點X加到活結(jié)點表PARENT(XE//E結(jié)點標(biāo)記為X的父結(jié)endif活結(jié)點表為空輸出“無解”endcallLEAST(E)//找一個具有最小?值的活結(jié)點放到E中，從活結(jié)點表中刪endLC-檢索的特如果有兩個結(jié)點X,Yc(X)>c(Y但?X)<?(YLC不能如果使每一對c(X)<c(Y)的結(jié)點X,Y,都有?(X)<?(Y),滿足上述要求2且易于計算的?通常很難,一般只能找到易于計算且有如下性質(zhì)的?:對每個結(jié)點X,有?(X)c(X)且對于答案結(jié)點X?(X)＝c(X這時改進(jìn)算法LC,可找到最小成本的答案結(jié)點;AlgorithmLC1-Input:狀態(tài)空間樹T,T中結(jié)點的估計成本函數(shù)?Output:問題的解（從根到最小成本答案結(jié)點的路徑ET//E-結(jié)將活結(jié)點表初始為ifE是答案節(jié)點then輸出從E到T的路徑andreturnendforE的每個兒子callADD(X)//將新的活結(jié)點X加到活結(jié)點表PARENT(XE//E結(jié)點標(biāo)記為X的父結(jié)endif活結(jié)點表為空輸出“無解”endcallLEAST(E)//找一個具有最小?值的活結(jié)點放到E中，從活結(jié)點表中刪end使用?(X)c(X)的成本估計函數(shù)?(.)來給出由任一結(jié)點X得出的解的下界使算法具有一定的智能,減少盲目性;定義U是最小成本解的成本上界,則達(dá)的答案結(jié)點X有c(X)(2)如果已經(jīng)到達(dá)一個具有成本U的答案結(jié)點,則?(XU的(3U的初始值可以用某種啟發(fā)是方法得到，也可以置成Similartobacktracking,branchandbounddesigngeneratesasearchtreeandlooksforoneormoreHowever,whilebacktrackingsearchesforasolutionorasetsolutionsthatsatisfycertainpropertiesizationorminimization),branch-and-boundalgorithmsaretypicallyconcernedwithonly izationorminimizationofagivenfunction.Inbranch-and-boundalgorithms,aboundiscalculatedateachnodexonthepossiblevalueofanysolutiongivenbynodesthatmaylaterbegeneratedinthesubtreerootedatx.Iftheboundcalculatedisworsethanapreviousbound,thesubtreerootedatxisblocked,i.e.,noneofitschildrenare優(yōu)化問題的分枝-界限算成本函數(shù)c(.):目標(biāo)函數(shù)可行解的結(jié)點c(X)就是估值函數(shù)有?(X)c(X),不是估計到達(dá)一個答案TSPProblemGivenasetofcitiesandacostfunctionthatisdefinedoneachpairofcities,findatourofminimumcost.Here