3问题求解与搜索1课件

Problem-solvingandSearch

(问题求解与搜索)UninformedSearch中南大学刘丽珏问题求解是人工智能的核心问题之一问题求解的目的机器自动找出某问题的正确解决策略更进一步，能够举一反三，具有解决同类问题的能力是从人工智能初期的智力难题、棋类游戏、简单数学定理证明等问题的研究中开始形成和发展起来的一大类技术求解的手段多种多样其中搜索技术是问题求解的主要手段之一问题表示解的搜索问题求解导航游戏分配调度路径规划很多问题可以转化为搜索问题12384567OriginalState12384567GoalState状态空间法的求解过程转化为在状态空间图中搜索一条从初始节点到目标节点的路径问题图的搜索无信息搜索（盲目搜索）SpecifyingaSearchProblem有信息搜索（启发式搜索）宽度优先搜索深度优先搜索A算法A*算法图的一般搜索策略FullyobservableDeterministicStaticDiscreteSingleagent一般图搜索的假设树是无圈连通图，每个节点只有一个父节点树搜索不检查重复状态图搜索大多比树搜索高效树搜索与图搜索ADBECFGS3444554322SADBDECEBFBFCGCG333224444444555G2G2G2树搜索图的搜索过程状态：(城市名)算子：常德→益阳 益阳→常德 益阳汨罗 益阳宁乡 益阳娄底

…？？？？必须记住哪些点走过了必须记住下一步还可以走哪些点深度优先搜索必须记住从目标返回的路径图的搜索过程必须记住哪些点走过了必须记住下一步还可以走哪些点必须记住从目标返回的路径OPEN表(记录还没有扩展的点)CLOSED表(记录已经扩展的点)每个表示状态的节点结构中必须有指向父节点的指针图的搜索常德OPEN:CLOSED:常德益阳益阳娄底宁乡汨罗娄底宁乡汨罗湘乡长沙湘乡长沙衡阳湘乡衡阳长沙岳阳岳阳宽度优先搜索图的搜索常德OPEN:CLOSED:常德益阳益阳娄底宁乡汨罗娄底株洲衡阳湘乡宁乡汨罗衡阳湘乡湘乡宁乡汨罗株洲OPEN表中节点的不同顺序决定了不同的搜索策略图的一般搜索策略(树搜索)开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移出n为目标节点吗？将n的后继节点放入OPEN表，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否4种途径来评价搜索算法的性能完备性—当问题有解时，算法是否保证找到一个解最优性—算法是否能找到一个最优解(路径耗散函数值最小的路径)时间复杂性—找到一个解需要花费多少时间空间复杂性—在搜索过程中需要占用多少内存搜索算法的性能盲目搜索(a.k.a.blindsearch)不使用任何与问题有关的经验信息分类宽度优先搜索Breadth-firstsearch深度优先搜索Depth-firstsearch有界深度优搜索Depth-limitedsearch等代价搜索Uniform-costsearch迭代加深搜索Iterativedeepeningsearch.特点搜索过程中不使用与问题有关的经验信息搜索效率低不适合大空间的实际问题求解无信息搜索（Uninformedsearch）节点除了存放状态本身的信息，还需保存指向父节点的指针，或是何种操作可以转换为这个状态Openlist存放所有已经被生成了，但还未被扩展的节点(opennodes)代表搜索树的前沿，也叫FrongelistClosedlist存放所有已经被扩展的节点(closednodes)Notnecessaryfortreesearch数据结构Expandshallowestunexpandednode搜索过程首先扩展根节点接着扩展根节点的所有后继节点然后再扩展后继节点的后继，依此类推在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展Implementation:openisaFIFOqueue宽度优先(BFS，Treesearch)generalSearch(problem,Queue)#ofnodestested:0,expanded:0Example:BFSExpnd.nodeOpenlist{S}generalSearch(problem,Queue)#ofnodestested:1,expanded:1Example:BFSExpnd.nodeOpenlist{S}Snotgoal{A,B,C}generalSearch(problem,Queue)#ofnodestested:2,expanded:2Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}Anotgoal{B,C,D,E}generalSearch(problem,Queue)#ofnodestested:3,expanded:3Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}Bnotgoal{C,D,E,G}generalSearch(problem,Queue)#ofnodestested:4,expanded:4Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}B{C,D,E,G}Cnotgoal{D,E,G,F}generalSearch(problem,Queue)#ofnodestested:5,expanded:5Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}B{C,D,E,G}C{D,E,G,F}Dnotgoal{E,G,F,H}generalSearch(problem,Queue)#ofnodestested:6,expanded:6Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}B{C,D,E,G}C{D,E,G,F}D{E,G,F,H}Enot

goal{G,F,H,G}

generalSearch(problem,Queue)#ofnodestested:7,expanded:6Example:BFSExpnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}B{C,D,E,G}C{D,E,G,F}D{E,G,F,H}E{G,F,H,G}

Ggoal{F,H,G}noexpandgeneralSearch(problem,Queue)#ofnodestested:7,expanded:6Example:BFSPath:S,B,GCost:8Expnd.nodeOpenlist{S}S{A,B,C}A{B,C,D,E}B{C,D,E,G}C{D,E,G,F}D{E,G,F,H}E{G,F,H,G}

G{F,H,G}完备性(Completeness)Doesitalwaysfindasolutionifoneexists?YESIfshallowestgoalnodeisatsomefinitedepthd时间复杂度(Timecomplexity)假设每个状态有

b

个后继,目标节点所在深度为d根节点有b个后继，这b个节点每个又有b个后继，即b2最坏的情况：扩展除d层最后一个节点外的所有节点总共扩展操作的次数:BFS性能空间复杂度(Spacecomplexity)每个节点都需要存储BFS性能最优性(Optimality)如果每步扩展的代价相同时，宽度优先搜索能找到最优解Twolessons指数级的时间消耗，内存消耗是比执行时间消耗更大的问题指数级复杂度的搜索问题无法通过无信息搜索完成，除非其搜索空间非常小假设每个节点有b=10个后继节点，目标节点在d层BFS性能123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567BFS的扩展版本Expandnodewithlowestpathcost

1959年由Dijkstra提出，也叫Dijkstra算法Letg(n)=costofpathfromstartnodestocurrentnoden

Implementation:open=PriorityQueue(queueorderedbyg).UCSisthesameasBFSwhenallstep-costsareequal.等代价搜索(Uniform-costsearch,UCS)generalSearch(problem,priorityQueue)#ofnodestested:0,expanded:0Example:UCSExpnd.nodeOpenlist{S}generalSearch(problem,priorityQueue)#ofnodestested:1,expanded:1Example:UCSExpnd.nodeOpenlist{S:0}Snotgoal{B:2,C:4,A:5}generalSearch(problem,priorityQueue)#ofnodestested:2,expanded:2Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}Bnotgoal{C:4,A:5,G:2+6}generalSearch(problem,priorityQueue)#ofnodestested:3,expanded:3Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}B{C:4,A:5,G:8}Cnotgoal{A:5,F:4+2,G:8}generalSearch(problem,priorityQueue)#ofnodestested:4,expanded:4Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}B{C:4,A:5,G:8}C{A:5,F:6,G:8}Anotgoal{F:6,G:8,E:5+4,D:5+9}generalSearch(problem,priorityQueue)#ofnodestested:5,expanded:5Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}B{C:4,A:5,G:8}C{A:5,F:6,G:8}A{F:6,G:8,E:9,D:14}Fnotgoal{G:4+2+1,G:8,E:9,D:14}generalSearch(problem,priorityQueue)#ofnodestested:6,expanded:5Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}B{C:4,A:5,G:8}C{A:5,F:6,G:8}A{F:6,G:8,E:9,D:14}F{G:7,G:8,E:9,D:14}Ggoal{G:8,E:9,D:14}noexpandgeneralSearch(problem,priorityQueue)#ofnodestested:6,expanded:5Example:UCSExpnd.nodeOpenlist{S:0}S{B:2,C:4,A:5}B{C:4,A:5,G:8}C{A:5,F:6,G:8}A{F:6,G:8,E:9,D:14}F{G:7,G:8,E:9,D:14}G{G:8,E:9,D:14}Path:S,C,F,GCost:7Completeness:YES,ifstep-cost>(asmallpositiveconstant)Timecomplexity:AssumeC*thecostoftheoptimalsolution.AssumethateveryactioncostsatleastWorst-case:Uniform-costsearchSpacecomplexity:IdemtotimecomplexityOptimality:nodesexpandedinorderofincreasingpathcost.YES,ifcomplete.深度优先搜索(DFS,Treesearch)ExpanddeepestunexpandednodeImplementation:openisaLIFOqueue(=stack)深度优先搜索过程：总是扩展搜索树的当前扩展分支(边缘)中最深的节点搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点那些没有后继节点的节点扩展完毕就从边缘中去掉然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展generalSearch(problem,Stack)#ofnodestested:0,expanded:0Example:DFSExpnd.nodeOpenlist{S}generalSearch(problem,Stack)#ofnodestested:1,expanded:1Example:DFSExpnd.nodeOpenlist{S}Snotgoal{A,B,C}generalSearch(problem,Stack)#ofnodestested:2,expanded:2Example:DFSExpnd.nodeOpenlist{S}S{A,B,C}Anotgoal{D,E,B,C}generalSearch(problem,Stack)#ofnodestested:3,expanded:3Example:DFSExpnd.nodeOpenlist{S}S{A,B,C}A{D,E,B,C}Dnotgoal{H,D,E,B,C}generalSearch(problem,Stack)#ofnodestested:4,expanded:4Example:DFSExpnd.nodeOpenlist{S:0}S{A,B,C}A{D,E,B,C}D{H,E,B,C}Hnotgoal{E,B,C}generalSearch(problem,Stack)#ofnodestested:5,expanded:5Example:DFSExpnd.nodeOpenlist{S}S{A,B,C}A{D,E,B,C}D{H,E,B,C}H{E,B,C}Enotgoal{G,B,C}generalSearch(problem,Stack)#ofnodestested:6,expanded:5Example:DFSExpnd.nodeOpenlist{S}S{A,B,C}A{D,E,B,C}D{H,E,B,C}H{E,B,C}E{G,B,C}Ggoal{B,C}

noexpandgeneralSearch(problem,Stack)#ofnodestested:6,expanded:5Example:DFSExpnd.nodeOpenlist{S}S{A,B,C}A{D,E,B,C}D{H,E,B,C}H{E,B,C}E{G,B,C}G{B,C}

Path:S,A,E,GCost:15Completeness;Doesitalwaysfindasolutionifoneexists?NOunlesssearchspaceisfiniteandnoloopsarepossible.Timecomplexity假设每个状态有

b

个后继,目标节点所在深度为d，搜索树的最大深度为mDFS的性能Terribleifmismuchlargerthand(depthofoptimalsolution)Spacecomplexity深度优先搜索对内存的需求比较适中只需要保存从根到叶的单条路径，包括在这条路径上每个节点的未扩展的兄弟节点当搜索过程到达了最大深度的时候，所需要的内存最大假定每个节点的分支系数为b，最大深度为m的搜索树保存在内存中的节点的数量包括到达深度m时所有未扩展的节点以及正在被考虑的节点。每个层次上都有(b-1)个未扩展的节点，总的内存需要量为m(b-1)+1。因此深度优先搜索的空间复杂度是b的线性函数O(bm)OptimalityNoDFS的性能IsDF-searchwithdepthlimitl.i.e.nodesatdepthlhavenosuccessors.ProblemknowledgecanbeusedSolvestheinfinite-pathproblem.Ifl<dthenincompletenessresults.Ifl>dthennotoptimal.Timecomplexity:Spacecomplexity:有界深度优先Depth-limitedsearchGeneticsProfessorWantingtonamehernewbabygirlUsingonlythelettersD,N&ASupposeyouhavethelettersorderedalphabetically(A,D,N)andyoustartwritingdownpossibilities:

A,D,N,AA,AD,AN,DA,DD,DN,NA,ND,NN,...

HowmanystringsoffourorfewerlettersaretherewherethelettersareD,NorA?Intheabovepossibilities,areyousearchinginadepthfirstorbreadthfirstway?Whatarethenextthreepossiblenamesyouwouldwritedown?HowmanypossibilitieswillyouwritedownbeforegettingtothenameANNA?NameofagirlWhat?每次改变限制深度，多次调用深度有限搜索算法Ageneralstrategytofindbestdepthlimitl.Goalsisfoundatdepthd,thedepthoftheshallowestgoal-node.CombinesbenefitsofDF-andBF-search迭代加深搜索(IterativeDeepeningSearch,Treesearch)functionITERATIVE_DEEPENING_SEARCH(problem)returnasolutionorfailure inputs:problem fordepth0to∞do

result

DEPTH-LIMITED_SEARCH(problem,depth) ifresultcuttoffthenreturnresultID-search,exampleLimit=0ID-search,exampleLimit=1ID-search,exampleLimit=2ID-search,exampleLimit=3Example:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSExample:IDSCompleteness:YES(noinfinitepaths)Timecomplexity:叠代深入搜索中因为多次重复搜索，因此部分状态被多次生成，看起来很浪费但因为在分支因子比较平衡的搜索树中，多数节点都在最底层(即叶子节点)，所以上层节点的多次生成影响不是很大Nodegeneration:leveld:onceleveld-1:2leveld-2:3…level2:d-1level1:dIDS的性能NumberofnodesgeneratedinaBFStodepthdwithbranchingfactorb: NBFS=b1+b2+…+bd-1+bdNumberofnodesgeneratedinaniterativedeepeningsearchtodepthdwithbranchingfactorb:NIDS=(d+1)b0+d

b+(d-1)b2+…+3bd-2+2bd-1+1bd

Forb=10,d=5,NBFS=1+10+100+1,000+10,000+100,000=111,111NIDS=6+50+400+3,000+20,000+100,000=123,456Overhead=(123,456-111,111)/111,111=11%ComparetoBFSIDS的性能Spacecomplexity:Cfr.depth-firstsearchO(bd)Optimality:路径代价是节点深度的非递增函数时是最优的一般来讲，当搜索空间很大而解的深度未知时，迭代加深搜索是一个首选的无信息搜索方法IDS的性能Depth-limited=1123845671238456712384567123845671238456781324567Goal:ID-search,exampleDepth-limited=21238456712384567123845671238456741238567123845671238456712384567123845671238456712384567123845675671238481324567Goal:Depth-limited=312384567123845671238456712384567412385671238456712384567123845671238456712384567123845671238456712384567123845671238456712384567123845671238456712384567123845675671238481324567Goal:Depth-limited=412384567123845671238456712384567123845671345612367812384567Goal81324567Goal:1238456712384567123845671238456712384567123845671238456712384567412385671238456712384567123845671