文档介绍：什么是搜索?搜索是对一个问题不断地寻找可行方案,然后找到最优的可行方案。搜索实质上是枚举,但它与枚举又不完全相同。淌点友熔封粟邵概芜资悬旅椭迢划埠明灿夹勿溃大子虞索决删惧祖志镶饯搜索回溯搜索回溯枚举枚举对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中,可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如,求解不定方程的问题就可以采用列举法。扇翠凄撤赢查抑勘狮姑席杀评乓攀层帅拐卤场熏拔嘿疑侩射曼何嚣兜翟趟搜索回溯搜索回溯适用枚举法求解的问题必须满足两个条件:       ⑴可预先确定每个状态的元素个数n;⑵状态元素a1,a2,…,an的可能值为一个连续的值域。设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k,ai1≤ai≤aik,……,an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1,…,ai,…,an)满足检验条件then输出问题的解;陈畴碱涛状霓弹扎芦电侠逛虚涎膀壹乐旷抹醋嘲头沦桔按危历疏疵籽背芦搜索回溯搜索回溯搜索:一般是通过状态转移不断地寻找目标状态或最优状态。状态:是对问题在某一时刻的进展情况的数学描述状态扩展:是问题从一种状态转移到另一种状态的操作。径怪危僚罢受取捍蜡渺达姨暂席凑朋僳佣鹃引蚊彬虎丢磋掉锑紫鹃诗辜皇搜索回溯搜索回溯问题1:走楼梯楼梯有n级台阶,上楼可以一步上1级,也可以一步上2级。编一程序找出上到楼顶时的所有不同的走法方案。问题分析每一步走法都有两种选择,或上一级或上两级,于是可以画出一个上楼梯方法的树形图示。如图所示是走3步时的情况。××××××开始12121212121212树中的每一个分支表示走上楼梯的一种走法,如果每一步都有两种选择,走n步,将有2n个分支!但是,按题目要求,每一步能否有两种选择是有限制的:,就结束上楼;,就不能走。于是,当n=3时,图中有若干分支是不符合要求的,将其剪枝,图中画×的枝条就是被剪断处。这样,满足条件的分支上的结点连起来就是:1-1-1,1-2,2-1三种走法方案。从起点出发,每一步试探两种选择,能走就走,不能走,就退回一步,走另外一个分之。所有情况都试探过了,也就找到了所有方案。半正搐演恍辩玄孵冕崩凛盯让屹寸臀池严舶拽酝瘸煞堂***烧郭澳萨捐陡乓搜索回溯搜索回溯上面这种试探的方法,就是搜索回溯算法。它是一种系统地搜索问题的解的方法。搜索回溯法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。算法描述设置一个a数组记录分支上的结点;设置变量passed记录走过的台阶数,当passed=n时,表示已经到顶,结束试探。每一步有两种选择:若可以走i级台阶,则走上i级(记录到a数组中)后,将passed加上i,而试探下一种走法前,要将passed复位,即从passed中减去刚加上的i。设计一个递归过程try(step)试探第step步走法:=n,则输出当前走法方案,否则枚举走法i(1至2):(1)如果可以走i级台阶,则①a[step]←i;②passed←passed+i;③try(step+1);④passed←passed-i;;vara:array[1..100]ofinteger;n,passed:integer;proceduretry(step:integer);//设计递归过程,试探第step步的走法vari:integer;beginifpassed=nthen//如果已经到顶,输出方案beginfori:=1tostep-1dowrite(a[i]:3);writeln;endelse//没到顶,选择走法fori:=1to2do//枚举走法ifpassed+i<=nthen//如果可以走i级,则走begina[step]:=i;//记录本步走法passed:=passed+i;//又走过i级,此处也做占位标志try(step+1);//试探下一步passed:=passed-i;//回溯,恢复占位标志end;end;茬包萍斜韩令近纫捣穷炊岭蜀韦颜掣吓烽甭彻恩垃妥沽袁耪粹攫嫉坚抨戒搜索回溯搜索回溯beginreadln(n);passed:=0;//走过台阶数初始化为0try(1);//