搜索的优化

搜索的优化 1． 引论 在我们遇到的大部分题目中，一般都可以运用搜索的算法。但是其中又有 差别。对于一些庞大的数据和繁多的搜索次数，光用搜索就显得力不从心了。因此在这篇文章中，主要讲述了几种主要搜索方法及优化搜索的方法。（主要介绍了启发式搜索）。 例题1：八数码难题。 在3 X 3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求给出一个初始状态和目标状态，找到一种最少步骤的移动方法，实现从初始状态到目标状态的转变。 例题2：中国盒子问题。 给定10个盒子排成一行，其中有相邻的两个盒子是空的，其余盒子中有4 个“A”和4个“B”。 A B B A A B A B 规则：任意移动相邻的字母可移到空盒中去，但这两字母的次序应保持不变。 目标：全部A都在B的左边。 A A A A B B B B 2． 无信息搜索 无信息搜索包括：广度优先搜索和深度优先搜索。由于它们新扩展的子结 点在数据库中的排列顺序完全是随意的，一般是按人为随意确定的产生规则的 先后顺序而定的，与题目本身毫无关系。 ㈠　广度优先搜索 什么是广度优先搜索呢？在搜索过程中，深度越小的结点先得到扩展， 就 是广度优先搜索。这就好比是一棵树，先从离人最近的树枝开始数叶子，将这 一层的树叶全部数完了，再到离人更远的树枝去数。这实际上是一层一层的递 进关系 —— 由近到远，先横向扩展，再纵向扩展。 ㈡ 深度优先搜索 深度优先搜索和广度优先搜索正好相反，在深度优先搜索法中，深度越大的结点越先得到扩展。这也相当于先顺着一个枝干，将这个枝干上的所有树叶由近到远的数出来，再回到树根处，继续数别的枝干上的树叶，直到将整个树遍历一遍 —— 先纵向扩展，再横向扩展。 ㈢ 无信息搜索的优化 对于无信息的优化，一般来说是用分枝定界的方法。也就是在生成一个结点的时候，判断是否符合要求，若不符合，则将其删去。这样就可以避免许多无用和重复的运算。但是这种方法也只能处理较多的数据，对于庞大的数据便有点牵强。 3． 启发式搜索 无论是广度优先搜索还是深度优先搜索，在一般情况下，其耗费是很大的， 或者要花费太多的时间，或者要占用非常大的储存空间，这在实际应用上往往 行不通。因此引进了启发式搜索。启发式搜索就是根据人为地对题目的进行优 化，再将人脑中进行的筛选过程输入给电脑，由电脑模拟这一过程，从而达到 优化程序的目的。在本文中主要介绍启发数和A算法和A*算法。 ㈠ 启发函数 启发式搜索的基本思路是：预先确定好一个函数，它能反映该结点与目标 结点的接近程度，这个函数称为启发函数 —— 它是根据题目而定的，一般没 有固定的公式。 像在八数码难题中，最基本的思路就是：F（n）= 未到位的数字个数 + 当前结点的深度。（F（n）被称为估价函数） 然后根据F（n）的大小来把这些结点重新排列，将F（n）值最小的放在最前面，使得取用时就可以直接运用到估价函数最小的子结点。由于先扩展的是启发函数值最小的结点，所以由此找到的结果，必定是最少步骤可以达到的。但是在计算时，如果其启发函数值一样，当然选择深度最小的结点进行扩展。 ㈡ A算法和A*算法 对于同一道题，我们可以选取不同的条件来建立估价函数，比如八数码问题我们也可以取F（n）=各数字到目标地点的距离之和 + 当前结点的深度。其结果是不一样的。这样随着人为地对一个估价函数的变动，h（n）作为人为的成分，来重新排列被扩展的子结点顺序的算法，就是A算法。 在例题2中，我们有3种方法。 ①F（n）= 任意一个结点中B右边A的数目 + 结点的深度。 ②F（n）= 任意一个结点中A左边相邻B的A的数目 + 结点的深度。 ③F（n）= 任意一个结点中每个A左边B的数目之和 + 结点的深度。 对于其不同的输入数据的结果是不一样的。（见附录）可知：没有任何启发函数的无信息算法所扩展的结点数最多，可达400多个。而方法1的启发能力较强，最强的是方法3。 在例题1中，本文应用了：计算没有到位的数据的个数来排序启发函数；其实，也可以采用到位的数据的个数来建立启发函数；或者是，各个数字到目标位置的距离之和。 这只要将一下程序中的粗体改变一下。变成计数到位的数据的个数或距离之和就可以了。 对于其不同的输入数据的结果是不一样的。（见附录）可知：没有任何启发函数的无信息算法所扩展的结点数最多，可达400多个。而方法1的启发能力较强，最强的是方法3。 我们也应看到：虽然A算法可以优化搜索，但是，由于方法3的搜索能力太强了，从而导致了丢失了最优解。所以，A算法并不能得到最有解。 对于这种情况，人们有创建了另一个算法：A*算法。 定理：如果h*（n）是中间结点n到目标结点的实际费用，h（n）是定义的启发函数，如果对于任何结点n有h（n）≤h*（n），则用估价函数f（n）=g（n）+h（n），（g（n）为根结点到结点n的实际费用）一定可以得到最优解。 满足定理的A算法，就称为A*算法。 也就是说：在保证定理的条件下，使h（n）尽可能的大。但是，启发能力越强的函数，往往越复杂，计算量也越大。如果，计算量超过了产生新结点的时间，就得不偿失了。因此，必须合理利用A和A*算法。 八数码的程序如下： Program Eight_Chess(Input,Output); Uses Crt; Type att=Array [1..3,1..3] Of Integer; Const a:Array [1..4] Of Integer=(-1,0,1,0); { 控制方向的数组 } b:Array [1..4] Of Integer=(0,1,0,-1); Var num,arty:att; hh:Array [0..100,1..11] Of Integer; pp:Integer; Procedure Input; { 初始化 } Begin num[1,1]:=2; num[1,2]:=8; num[1,3]:=3; num[2,1]:=1; num[2,2]:=6; num[2,3]:=4; num[3,1]:=7; num[3,2]:=0; num[3,3]:=5; arty[1,1]:=1; arty[1,2]:=2; arty[1,3]:=3; arty[2,1]:=8; arty[2,2]:=0; arty[2,3]:=4; arty[3,1]:=7; arty[3,2]:=6; arty[3,3]:=5; hh[0,1]:=2; hh[0,2]:=8; hh[0,3]:=3; hh[0,4]:=1; hh[0,5]:=6; hh[0,6]:=4; hh[0,7]:=7; hh[0,8]:=0; hh[0,9]:=5; hh[0,11]:=-1; End; { End Of Input } Function Ok(dep,ii,i,j:Integer;num:att):Boolean; { 判断移动棋子是否符合条件 } Var aa,jj,ii1,jj1,k:Integer; gg:Array [1..9] Of Integer; { 交换变量 } Begin i:=i+a[ii]; j:=j+b[ii]; Ok:=True; If (i<1) Or (i>3) Or (j<1) Or (j>3) { 判断I,J是否出界 } Then Begin Ok:=False; Exit; End; If dep<2 Then Exit; i:=i-a[ii]; j:=j-b[ii]; num[i,j]:=num[i+a[ii],j+b[ii]]; num[i+a[ii],j+b[ii]]:=0; k:=0; For ii1:=1 To 3 Do For jj1:=1 To 3 Do Begin Inc(k); gg[k]:=num[ii1,jj1]; End; For jj:=0 To dep Do { 判断是否有重复 } Begin aa:=0; For ii1:=1 To 9 Do If gg[ii1]=hh[jj,ii1] Then Inc(aa); If aa=9 Then Begin Ok:=False; Exit; End; End; End;{End Of Ok } Procedure Swep(Wei,uk:Integer); { 交换 } { 对启发函数的大小进行排序 } Var i,j,ii,jj:Integer; gh:Array [1..11] Of Integer; Begin For i:=Wei To uk-1 Do Begin For j:=Wei+1 To uk Do If hh[i,10]>hh[j,10] Then Begin For ii:=1 To 10 Do gh[ii]:=hh[i,ii]; For ii:=1 To 10 Do hh[i,ii]:=hh[j,ii]; For ii:=1 To 10 Do hh[j,ii]:=gh[ii]; End; End; End;{ End Of Swep } Procedure Search(dep,i,j:Integer); { 对八数码进行扩展 } Var p,ii,ii1,jj1,k,Min,o,Wei,Wei1:Integer; uk:Integer; f:Boolean; Begin Wei:=1; p:=0; Repeat Wei1:=0; uk:=0; Min:=9; If dep=1 Then Wei:=dep Else Wei:=dep+1; For ii:=1 To 4 Do Begin If Ok(dep,ii,i,j,num) { 如果符合条件 } Then Begin Inc(dep); Inc(uk); num[i,j]:=num[i+a[ii],j+b[ii]]; num[i+a[ii],j+b[ii]]:=0; k:=0; o:=0; For ii1:=1 To 3 Do For jj1:=1 To 3 Do Begin If num[ii1,jj1]<>arty[ii1,jj1] Then Inc(o); { 对启发函数进行计数 } Inc(k); hh[dep,k]:=num[ii1,jj1]; End; hh[dep,10]:=o; If oarty[ii1,jj1]) And (f) Then Begin f:=False; Break; End; Until f; pp:=p; End; { End Of Search } Procedure Print; { 打印 } Var gg:Array [1..100] Of Integer; i,j,ii:Integer; Begin i:=0; FillChar(gg,SizeOf(gg),0); Repeat Inc(i); gg[i]:=hh[pp,11]; pp:=hh[pp,11]; Until hh[pp,11]=-1; For j:=i DownTo 1 Do Begin For ii:=1 To 9 Do Begin Write(hh[gg[j],ii],' '); If ii Mod 3=0 Then WriteLn; End; WriteLn; End; For ii:=1 To 3 Do Begin For j:=1 To 3 Do Write(arty[ii,j],' '); WriteLn; End; End;{ End Of Print } Begin Clrscr; Input; { 初始化 } Search(0,3,2); Print; { 打印 } End. 粗体的地方就是对此八数码所建立的启发函数的计算。 我们可以对比以下，如果不用启发函数，而用无信息的搜索，次数可达上百，但是，如果用了启发函数，而产生的结点只有11个。所以我们可以显而易见的发现搜索的优化是多么有用。 但是，在考试中，并不能一眼看出对于一道题目的最好的方法，所以，取好的算法，在考试中是非常重要的。 而且对于一些较大数目的数据，如果运用搜索的方法，最重要的环节就是：搜索的优化。 附录： 搜索方法 子结点的总个数 目标的最少步数 无信息 409 5 方法 ① 70 5 方法 ② 165 5 方法 ③ 53 7