第三章 问题求解方法

人工智能

(ArtificialIntelligence)第三章问题求解方法Chapter3.ProblemsSolving本章教学计划教学重点1.图搜索策略2.搜索技术教学难点1.启发式搜索算法2.模拟退火算法3.遗传算法教学要求：了解和掌握各类常用的搜索算法，着重对适于AI的启发式算法的理解。3.1图搜索策略

(Strategiesforsearching)图搜索策略在图中寻找特定路径的方法。图中每个节点对应于一个状态，节点间的连接边对应于转移函数。图搜索策略即为选择适合的搜索算法，可用于在状态空间中找到能实现从初始状态到目标状态的转移路径。*

3.1图搜索策略

(Strategiesforsearching)3.2状态空间搜索概述

(StateSpaceSearchingScheme)状态图状态图中的节点表示问题的一种格局，转移函数控制格局之间的转换。当目标格局出现时，表示搜索成功。Question：Issearchingproceduredestinedfortermination?Why?3.2状态空间搜索概述

(StateSpaceSearchingScheme)问题求解与状态空间搜索(1)将问题形式化定义为四元组的状态机(2)状态空间法将求解过程定义为若干算子与搜索的有机结合体(3)状态空间包含问题相关对象的各种可能排列(4)定义出初始状态和目标状态(5)使用规则对应搜索操作3.2状态空间搜索概述

(StateSpaceSearchingScheme)pp.55-56,eg.3.1,3.2pp.57-58,eg.3.3搜索的基本问题：搜索过程是否一定有解？搜索过程是否可终止？搜索得到的解是否唯一？搜索得到的解是否最优？搜索算法的空间和时间复杂性？3.2状态空间搜索-盲目的图搜索

(BruteForceSearching)搜索的概念与特点pp.58按固定算法进行搜索，不针对特定问题的信息条件pp.60,搜索代价主要类型回溯宽度优先深度优先图搜索盲目的图搜索-回溯(BackTracking)带回溯策略的搜索是从初始状态出发，试探性寻找路径，直到达到目的状态或得到不可解结论。该求解过程呈现递归性质。pp.61.StepTrack()?pp.62.Figure3.6pp.63.Functionbacktrack3.2状态空间搜索-盲目的图搜索

(BruteForceSearching)特点按固定算法进行搜索，不针对特定问题的信息条件主要类型回溯宽度优先深度优先图搜索盲目的图搜索-宽度优先(WFS)AlgorithmBreadth_First_Searchpp.64eg.3.4pp.65如何描述其状态空间？3.2状态空间搜索-盲目的图搜索

(BruteForceSearching)特点按固定算法进行搜索，不针对特定问题的信息条件主要类型回溯宽度优先深度优先图搜索盲目的图搜索-深度优先(DFS)定义：首先扩展最新产生(深度)的节点算法为防止搜索沿无效路径一直扩展，通常会给出一个节点扩展最大深度限制。盲目的图搜索-深度优先(DFS)pp.66.AlgorithmDescriptionpp.67.eg.3.53.2状态空间搜索-盲目的图搜索

(BruteForceSearching)特点按固定算法进行搜索，不针对特定问题的信息条件主要类型回溯宽度优先深度优先图搜索盲目的图搜索-图搜索(GS)根据搜索路径呈现出的图特性来搜索其它搜索方法：等代价搜索是宽度优先搜索的变形，不是沿等长度路径断层进行扩展，而是沿连接弧线上相关代价，按等代价路径断层进行扩展。分支界限法pp.683.3启发式搜索

(HeuristicSearching)概念和特点pp.69选择最有希望的节点(目标)进行搜索扩展主要类型A算法A*算法3.3启发式搜索

(HeuristicSearching)启发式策略(HeuristicStrategy)启发是针对发现操作算子启发式信息是指用于加速搜索过程的有关问题域所包含的特征信息启发式策略的应用场景(Context)问题的陈述和数据获取具有模糊性盲目搜索的时间代价太高*pp.70,eg.3.63.3启发式搜索

(HeuristicSearching)启发信息和估价函数pp.71-72为实现节点的启发式信息目标，提供对搜索算法新搜索路径选择的支持，使用量化的函数来评估搜索的有效性。启发式信息(不完全/效率)：陈述型过程型控制型3.3启发式搜索

(HeuristicSearching)启发信息和估价函数pp.71-72启发式函数f(n):

节点的评估函数f(n)=g(n)+h(n)//有记忆性g(n)g(n).vs.h(n)估价函数的设计将直接决定搜索算法的性能易于导致局部最优过早收敛3.3启发式搜索算法-A&A*算法

(HeuristicSearching)Procedureheuristic_searchpp.73Beginopen,close,f(s)=g(s)+h(s)//initWhile(!EMPTY(open))do…foreachsub-stateofndocase1:newstate;//intocandidatecase2:stateinOPEN;//updateactivetablecase3:stateinCLOSE;//updateinactivetable…endfor…endwhile//heretomeanfailureend3.3启发式搜索算法-A&A*算法

(HeuristicSearching)pp.75,eg.3.8A算法求解八数码问题的搜索树，估价函数定义为f(n)=d(n)+w(n)Keyproblemistochoosetheevaluationfunction.pp.76,figure3.163.3启发式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的讨论可采纳性，单调性，信息性1.可采纳性当一个搜索算法在最短路径存在时能保证找到它，则称为可采纳的。pp.75f*(n)=g*(n)+h*(n)g(n)层数，h*(n)启发函数该函数可作中间参照，一旦f超过f*可确定该节点n不是所需节点3.3启发式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的讨论2.单调性对一个启发式函数有：(1)对状态ni和nj，nj是ni的后继，满足h(ni)-h(nj)<=cost(ni,nj)，其中cost(ni,nj)是从ni到nj的实际代价；(2)目的状态的启发函数值为0或h(Goal)=0；则称该启发函数h(n)是单调的。3.3启发式搜索算法-A&A*算法

(HeuristicSearching)A*搜索算法的讨论3.信息性h1(n1)<=h2(n2)，称策略h2比h1具更多信息性。h(n)越大表示所搜索的状态越少，因此搜索效果更好。3.4与/或图搜索

(And/OrSearching)特点使用与/或表示事物间的联系，对问题进行规约求解。主要类型AO算法AO*算法3.4与/或图搜索-概念

(Conception)与/或图的概念Reviewpp.20问题求解的规约pp.78,figure3.17,figure3.18可解节点与非可解节点的递归定义pp.78可解图定义pp.78-79可解图扩展的代价计算pp.793.4与/或图搜索-AO,AO*算法

(And/OrAlgorithm)AOandAO*Algorithmpp.80-81书中的描述？Figure3.23(c)(d)OR(n5,n6)?算法是针对AO图所表示的问题进行启发式搜索求解，求得可能的解路径(解图)则为解决该问题时的规约子问题。3.4与/或图搜索-博弈树搜索

(GameSearching)pp.83,eg.3.10explanation尽量使游戏向有利于自己方发展局部状态与全局状态的考虑3.4与/或图搜索-博弈树搜索

(GameSearching)pp.85,eg.3.11一字棋游戏pp.89,eg.3.12

3.5局部搜索算法

(LocalSearching)特点沿梯度最大变化反方向选择搜索路径pp.90,procedurelocal_search…

while…iff(xn)<f(xb)thenxb=xn,P=N(xn)//若趋势向好的方向发展，则重新选择邻域3.5局部搜索算法

(LocalSearching)pp.91,eg.3.13局部搜索的问题：(1)局部最优问题？初始点的选择对全局最优点的影响多极值如何避免局部收敛？为什么不用定义域来表示该概率xi/∑(xi)3.5局部搜索算法

(LocalSearching)局部搜索的问题：(2)步长问题对收敛速度的影响对全局收敛的影响可变步长与动量方法3.6模拟退火算法

(SimulatedAnnealingAlgorithm)概念是局部搜索算法的一种扩展是对固体退火物理过程的模拟pp.93-94初始温度必须足够高每个温度下，能量的转换充分温度的下降必须足够缓慢最终温度必须足够低Simulatedannealing(SA)(/wiki/Simulated_annealing)3.6模拟退火算法

(SimulatedAnnealingAlgorithm)模拟退火算法

pp.94表3.2组合优化问题与固体退火过程的类比组合优化问题固体退火过程组合优化问题的解i(i∈D)物理系统中的一个状态s(s∈S)解的指标函数f(i)状态的能量E(s)解在邻域N中的交换X粒子的热运动M最优解fmin(i)能量最低状态Emin(x)控制参数温度T3.6模拟退火算法

(SimulatedAnnealingAlgorithm)类固体退火过程(1)设置较大温度t(2)随机设定一个初始解值i及领域N(i)(局部搜索)(3)求解转移概率(4)若新解j被接受，则以j替代i，否则i不变。重复(3)~(4)，直到在控制参数t下达到平衡下调t重复上述过程，直到退火t稳定3.6模拟退火算法

(SimulatedAnnealingAlgorithm)pp.95ProcedureSimulated-AnnealingBeginInitiation:t0,x0Loop1untiltislowenoughLoop2untilbanlanceattComputingf(x)|tendLoop2decreasetendLoop1end3.6模拟退火算法

(SimulatedAnnealingAlgorithm)局部搜索与模拟退火算法间的差异SA接受劣解见转移函数PtPt是t的函数，当t较大时，接受劣解的概率大这种差异设计有什么优点？3.6模拟退火算法

(SimulatedAnnealingAlgorithm)控制参数的确定并不是任何一组参数都保证SA算法收敛于某一近似解；经验表明，解质量与算法的运行时间成正比关系，因此结果取决于平衡选择；pp.96控制参数包括:初始温度参数t0温度tk的衰减函数Drop(tk)，即温度下降设计每一温度tk下的停止准则，即马尔科夫长度Lk算法的终止准则3.6模拟退火算法-参数控制

(SA-ParameterSetting)1.初始温度t0(1)给定一个希望的初始接受概率P0，给定一个较低的初始温度t0，如t0=1(2)随机产生状态序列，接受概率计算公式为

接受概率=接受的状态数/产生的状态总数如果接受概率小于给定的初始概率P0，则提高温度，更新t0，直至接受概率大于P03.6模拟退火算法-参数控制

(SA-ParameterSetting)2.温度的下降方法为保证温度尽可能缓慢下降，常用下述方法：(1)等比例下降

tk+1=a*tk(0<a<1)(2)等值下降

tk+1=tk-delta(t)(3)基于距离参数的下降法

pp.97,formula3.11,3.123.6模拟退火算法-参数控制

(SA-ParameterSetting)3