搜索算法.txt

搜索算法——包含回溯法、分枝定界和贪心法

List<-0; 
open<-1; 
close<-0; 
List[1].Situation<- 初始状态; 

While (close (open (未找到目标节点) do 
Begin 
Begin 
　 　close:=close+1; 
　　　For I:=close+1 to open do (寻找估价函数值最小的节点) 
Begin 
if List.f Begin 
交换List和List[close]; 
End-If; 
End-For; 
End; 
For I:=1 to TotalExpendMethod do（扩展一层子节点） 
Begin 
New-S:=ExpendNode(List[close].Situation,I) 
If Not (New-S in List[1..close]) then 
(扩展出的节点未与已扩展的节点重复) 
Begin 
If Not (New-S in List[close+1..open]) then 
(扩展出的节点未与待扩展的节点重复) 
Begin 
open:=open+1; 
List[open].Situation:=New-S; 
List[open].Last:=close; 
List[open].g:=List[close].g+cost; 
List[open].h:=GetH(List[open].Situation); 
List[open].f:=List[open].h+List[open].g; 
End-If 
Else Begin 
If List[close].g+cost+GetH(New-S) (扩展出来的节点的估价函数值小于与其相同的节点) 
Begin 
List[same].Situation:= New-S; 
List[same].Last:=close; 
List[same].g:=List[close].g+cost; 
List[same].h:=GetH(List[open].Situation); 
List[same].f:=List[open].h+List[open].g; 
End-If; 
End-Else; 
End-If 
End-For; 
End-While; 
对A*算法的改进--分阶段A*： 
当A*算法出现数据溢出时，从待扩展节点中取出若干个估价函数值较小的节点，然后放弃其余的待扩展 
节点，从而可以使搜索进一步的进行下去。 
第三部分　搜索与动态规划的结合 
例1. 有一个棋子，其1、6面2、4面3、5面相对。现给出一个M*N的棋盘，棋子起初处于(1,1)点，摆放状态 
给定，现在要求用最少的步数从(1,1)点翻滚到(M,N)点，并且1面向上。 
分析：这道题目用简单的搜索很容易发生超时，特别当M、N较大时。所以可以考虑使用动态规划来解题。对 
于一个棋子，其总共只有24种状态。在(1,1)点时，其向右翻滚至(2,1)点，向上翻滚至(1,2)点。而 
任意（I，J）点的状态是由（I-1，J）和（I，J-1）点状态推导出来的。所以如果规定棋子只能向上 
和向右翻滚，则可以用动态规划的方法将到达（M，N）点的所有可能的状态推导出来。显然，从（1， 
1）到达（N，M）这些状态的路径时最优的。如果这些状态中有1面向上的，则已求出解。如果没有， 
则可以从（M，N）点开始广度搜索，以（M，N）点的状态组作为初始状态，每扩展一步时，检查当前 
所得的状态组是否有状态与到达格子的状态组中的状态相同，如果有，则由动态规划的最优性和广度 
搜索的最优性可以保证已求出最优解。 
例2.给出一个正整数n，有基本元素a，要求通过最少次数的乘法，求出a^n。 
分析：思路一：这道题从题面上来看非常象一道动态规划题，a^n=a^x1*a^x2。在保证a^x1和a^x2的最优性之 
后，a^n的最优性应该得到保证。但是仔细分析后可以发现，a^x1与a^x2的乘法过程中可能有 
一部分的重复，所以在计算a^n时要减去其重复部分。由于重复部分的计算较繁琐，所以可以 
将其化为一组展开计算。描述如下： 
I:=n;(拆分a^n) 
split[n]:=x1;(分解方案) 
Used[n]:=True;(在乘法过程中出现的数字) 
Repeat(不断分解数字) 
Used[I-split[I]]:=True; 
Used[split[I]]:=True; 
Dec(I); 
While (I>1) and (not Used[I]) do dec(I); 
Until I=1; 
For I:=n downto 1 do(计算总的乘法次数) 
If Used[I] then count:=count+1; 
Result:=count;(返回乘法次数) 
思路二：通过对思路一的输出结果的分析可以发现一个规律： 
a^19=a^1*a^18 
a^18=a^2*a^16 
a^16=a^8*a^8 
a^8=a^4*a^4 
a^4=a^2*a^2 
a^2=a*a 
对于一个n，先构造一个最接近的2^k，然后利用在构造过程中产生的2^I,对n-2^k进行二进制分解， 
可以得出解。对次数的计算的描述如下： 
count:=0; 
Repeat 
If n mod 2 = 0 then count:=count+1 
Else count:=count+2; 
n:=n div 2; 
Until n=1; 
Result:=count; 
反思：观察下列数据： 
a^15 a^23 a^27 
Cost:5 Cost:6 Cost:6 
a^2=a^1*a^1 a^2=a^1*a^1 a^2=a^1*a^1 
a^3=a^1*a^2 a^3=a^1*a^2 a^3=a^1*a^2 
a^6=a^3*a^3 a^5=a^2*a^3 a^6=a^3*a^3 
a^12=a^6*a^6 a^10=a^5*a^5 a^12=a^6*a^6 
a^15=a^3*a^12 a^20=a^10*a^10 a^24=a^12*a^12 
a^23=a^3*a^20 a^27=a^3*a^24 

这些数据都没有采用思路二种的分解方法，而都优于思路二中所给出的解。但是经过实测，思路一二 
的所有的解的情况相同，而却得不出以上数据中的解。经过对a^2－a^15的数据的完全分析，发现对于 
一个a^n，存在多个分解方法都可以得出最优解，而在思路一中只保留了一组分解方式。例如对于a^6 
只保留了a^2*a^4，从而使a^3*a^3这条路中断，以至采用思路一的算法时无法得出正确的耗费值，从 
而丢失了最优解。所以在计算a^n=a^x1*a^x2的重复时，要引入一个搜索过程。例如:a^15=a^3*a^12， 
a^12=a^6*a^6，而a^6=a^3*a^3。如果采用了a^6=a^2*a^4，则必须多用一步。 

Link=^Node; （使用链表结构纪录所有的可能解） 
Node=Record 
splitnteger; 
next :Link; 
End; 

Solution:Array[1..1000] of Link; （对于a^n的所有可能解） 
Cost :Array[1..1000] of Integer; （解的代价） 
max nteger; （推算的上界） 

Procedure GetSolution; 
Var i,j nteger; 
min,cnteger; 
countnteger; 
temp,tail:Link; 
plan :Array[1..500] of Integer; 
nUsed:Array[1..1000] of Boolean; 
Procedure GetCost(From,Costnteger); （搜索计算最优解） 
Var temp:Link; 
a,b :Boolean; 
i nteger; 
Begin 
If Cost>c then Exit; （剪枝） 
If From=1 then （递归终结条件） 
Begin 
If Cost Exit; 
End; 
temp:=Solution[From]; 
While temp<>NIL do （搜索主体） 
Begin 
a:=nUsed[temp^.Split]; 
If not a then inc(cost); 
nUsed[temp^.Split]:=True; 
b:=nUsed[From - temp^.Split]; 
If not b then inc(cost); 
nUsed[From-temp^.Split]:=True; 
i:=From-1; 
While (i>1) and (not nUsed) do dec(i); 
GetCost(i,Cost); 
If not a then dec(cost); 
If not b then dec(cost); 
nUsed[From-temp^.Split]:=b; 
nUsed[temp^.Split]:=a; 
temp:=temp^.next; 
End; 
End; 
Begin 
For i:=2 to Max do（动态规划计算所有解） 
Begin 
count:=0; 
min:=32767; 
For j:=1 to i div 2 do （将I分解为I-J和J） 
Begin 
c:=32767; 
FillChar(nUsed,Sizeof(nUsed),0); 
nUsed[j]:=True;nUsed[i-j]:=True; 
If j=i-j then GetCost(i-j,1) 
Else GetCost(i-j,2); 
If c Begin 
count:=1; 
min:=c; 
plan[count]:=j; 
End 
Else if c=min then 
Begin 
inc(count); 
plan[count]:=j; 
End; 
End; 
new(solution); （构造解答链表） 
solution^.split:=plan[1]; 
solution^.next:=NIL; 
Cost:=min; 
tail:=solution; 
For j:=2 to count do 
Begin 
new(temp); 
temp^.split:=plan[j]; 
temp^.next:=NIL; 
tail^.next:=temp; 
tail:=temp; 
End; 
End; 
End;