文档介绍：搜索算法
搜索算法的基本思想
搜索是竞赛中常用的方法,它实质上是枚举法的应用。由于它相当于枚举法,所以效率相当低。因此,为提高搜索效率,人们想出很多剪枝方法,如分枝定界,启发式搜索等等。在竞赛中,我们不仅要熟练掌握这些方法,还要因地制宜地运用技巧,以提高效率。
定义:Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展,并且返回扩展后的状态。
基本搜索算法一【回溯算法】
回溯算法采用了“走不通就掉头”的思想作为控制结构,用先根遍历的方法来构造解答树,可用于找所有解以及最优解。
回溯算法对空间的消耗较少,当其与分枝定界法一起使用时,对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用,以免产生循环。
生成长度为n的字串,其字符从26个英文字母的前p(p≤26)个字母中选取,使得没有相邻的子序列相等。例如p=3,n=5时
‘a b c b a’满足条件
‘a b c b c’不满足条件
输入:n,p
输出:所有满足条件的字串
构造字串
分析
状态:
待扩展的字母序号at。实际上字串s亦参与了递归运算,但是由于该变量的存储量太大,因此我们将s设为全局变量;

边界条件和目标状态:
产生了一个满足条件的字串,即at=n+1;
搜索范围:第at位置可填的字母集{‘a’.. chr(ord(‘a’)+p-1)};
约束条件:当前字串没有相邻子串相等的情况
var
n,p:integer;{字串长度和可选字母的个数}
tl:longint; { 满足条件的字串数}
ed:char; { 可选字母集中的最大字母}
s:string; {满足条件的字串}
procedure solve(at:integer);{递归扩展第at个字母}
var ch:char;i:integer;
begin
if at=n+1 then
begin writeln(s);inc(tl);exit{回溯}end;{then} {若产生了一个满足条件的字串,则输出,满足条件的字串数+1}
for ch:='a' to ed do {搜索每一个可填字母}
begin
s:=s+ch;i:=1;{检查当前字串是否符合条件}
while (i<=at div 2)and(copy(s,length(s)-i+1,i)<>copy(s,length(s)-2*i+1,i)) do inc(i);
if i>at div 2 then solve(at+1);{若当前字串符合条件,则递归扩展下一个字母}
delete(s,length(s),1){恢复填前的字串}
end{for}
end;{solve}
begin
readln(n,p);{输入字串长度和前缀长短}
ed←chr(ord('a')+p-1);{计算可选字母集中的最大字母}
s←''; tl←0;{满足条件的字串初始化为空,字串数为0}
solve(1);{从第1个字母开始递归计算所有满足条件的字串}
writeln('Total:',tl);{输出满足条件的字串数}
end.{main}
深搜和广搜的区别
一个人走一个迷宫,发现有岔路,选择条走到底;如果走不通,再回到岔路口,走另一条路。这就是深搜。
而广搜是从起点开始走,一旦发现岔路,就分别在每个方向上都释放一个分身。例如有两条路:我们暂且给两个分身取名为1,2。每次控制一个分身走一步路,然后切换控制另一个分身。例如:先让1走一步,然后控制2走一步,但如果发现有个分身又遇到了岔路,这时,只能让分身再次施展分身之术了,举个例子:某时,1又到了一个3岔路口,于是,1分身为了11,12,13。他又先让11走一步,然后12,13,最后2。一次循环下去(如果出现新分支也同理)。直到一个分身走到终点,那就完成了目标。
为了模拟如何控制每个分身,我们可以来看上图的一种数据结构队列。
为了更好的理解,我们可以把他认为是一个数组。
这么一来,我们可以发现,为了循环控制1,2,首先我将1,放到a[1]中去,2放到a[2]中去,然后我开始控制他们,首先将a[1]取出来,走一步,然后把1放到a[3]里,接着取出a[2]走一步,再把2放到a[4]里……假如某个时刻1在a[n]中,2在a[n+1],当我们取出1是发现,有新的3岔路口,那么1就分成了11,12,13。那么我们分别把他们放入a[n+2],a[n+3],a[n+4]中去(当然1就消失了)……直到走到出口,我们就停下来。队列有两个口子,一个