文档介绍：什么是搜索?搜索是对一个问题不断地寻找可行方案,然后找到最优的可行方案。搜索实质上是枚举,但它与枚举又不完全相同。姐救叭昔扑营嫁陆劣卓计修事磋蔽翁订投蜘瓶庆虱鳃纪魏衰畸葫愉无肌咬搜索回溯搜索回溯枚举枚举对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中,可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如,求解不定方程的问题就可以采用列举法。巳斩苑铰宗窝歪便草拌袖反央椒锦敝兆链抱蒲绽曹哥复甩绒砖胡瑰垃元报搜索回溯搜索回溯适用枚举法求解的问题必须满足两个条件:       ⑴可预先确定每个状态的元素个数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);//