人工智能原理-北京大学-4--PartIISearchingChapter4LocalSear-(4

PrinciplesofArtificialIntelligence1LocalSearchAlgorithmsSchoolofElectronicandComputerEngineeringPekingUniversityWangWenminPrinciplesofArtificialIntelligence2Contents4.2.1.Hill-ClimbingSearch4.2.2.LocalBeamSearch4.2.3.TabuSearchPrinciplesofArtificialIntelligence::Searching::LocalSearch3Keepingjustonenodeinmemorymightseemtobeanextremereactiontotheproblemofmemorylimitations.在内存中仅保存一个节点似乎是对内存限制问题的极端反应。Localbeamsearchkeepstrackofkstatesratherthanjust1.而局部束搜索保持k个状态而不仅仅为1。LocalBeamSearch局部束搜索4.2.2.LocalBeamSearchItbeginswithkrandomlygeneratedstates.Ateachstep,allthesuccessorsofallkstatesaregenerated.Ifanyoneisagoal,thealgorithmhalts,elseitselectsthekbestsuccessorsfromthecompletelist,andrepeats.Inalocalbeamsearch,usefulinformationcanbepassedamongtheparallelsearchthreads.在局部束搜索中，有用的信息能够在并行搜索线程间传递。PrinciplesofArtificialIntelligence::Searching::LocalSearch4Example:TravellingSalespersonProblem(TSP)旅行推销员问题4.2.2.LocalBeamSearchABCDABCDKeepstrackofkstatesratherthanjust1.Startwithkrandomlygeneratedstates.k=2inthisexample.保持k个状态而不仅仅为1。从k个随机生成的状态开始。本例中k=2。PrinciplesofArtificialIntelligence::Searching::LocalSearch5Example:TravellingSalespersonProblem(TSP)旅行推销员问题4.2.2.LocalBeamSearchABCDABCDGenerateallsuccessorsofallthekstates.Noneoftheseisagoalstatesowecontinue.生成所有k个状态的全部后继节点。这些后继节点中没有目标状态，故继续下一步。ABCDABCDABCDABCDABCDABCDKeepstrackofkstatesratherthanjust1.Startwithkrandomlygeneratedstates.k=2inthisexample.保持k个状态而不仅仅为1。从k个随机生成的状态开始。本例中k=2。PrinciplesofArtificialIntelligence::Searching::LocalSearch6Example:TravellingSalespersonProblem(TSP)旅行推销员问题4.2.2.LocalBeamSearchABCDABCDABCDABCDABCDABCDABCDABCDSelectthebestksuccessorsfromthecompletelist.Repeattheprocessuntilgoalfound.从完成表中选择最佳k个后继节点。重复上述过程，直到找到目标。Keepstrackofkstatesratherthanjust1.k=2inthisexample.Startwithkrandomlygeneratedstates.Generateallsuccessorsofallthekstates.Noneoftheseisagoalstatesowecontinue.生成所有k个状态的全部后继节点。这些后继节点中没有目标状态，故继续下一步。PrinciplesofArtificialIntelligence::Searching::LocalSearch7StochasticBeamSearch随机束搜索Localbeamsearchmayquicklybecomeconcentratedinasmallregionofstatespace,makingthesearchlittlemorethananexpensiveversionofhillclimbing.局部束搜索会很快地集中在状态空间的某个小区域内，使得搜索代价比爬山法还要昂贵。Itanalogoustostochastichillclimbing,helpsalleviatethisproblem.它模仿随机爬山法，有助于缓解这个问题。VariantofLocalBeamSearch局部束搜索的变型4.2.2.LocalBeamSearchPrinciplesofArtificialIntelligence::Searching::LocalSearch8StochasticBeamSearch随机束搜索Insteadofchoosingbestksuccessors,itchoosesksuccessorsrandomly,withtheprobabilityofchoosingasuccessorbeinganincreasingfunctionofitsvalue.它不是选择k个最佳后继节点，而是以选择后继节点的概率是其值的递增函数，来随机地选择k个后继节点。Stochasticbeamsearchbearssomesimilartotheprocessofnaturalselection.随机束搜索有些类似于自然选择的过程。VariantofLocalBeamSearch局部束搜索的变型4.2.2.LocalBeamSearch