标题: 数学建模常用算法—搜索算法 [打印本页] 作者: 百年孤独 时间: 2016-3-2 14:38 标题: 数学建模常用算法—搜索算法 一、回溯算法 回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法]
＜Type＞ Node(节点类型)＝Record
Situtation:TSituation（当前节点状态）;
Way-NInteger（已使用过的扩展规则的数目）;
End
＜Var＞
List(回溯表):Array[1..Max(最大深度)] of Node;
pos(当前扩展节点编号):Integer;
＜Init＞
List＜-0;
pos＜-1;
List[1].Situation＜-初始状态;
＜Main Program＞
While (pos＞0(有路可走)) and ([未达到目标]) do
Begin
If pos＞=Max then (数据溢出,跳出主程序);
List[pos].Way-N=List[pos].Way-No+1;
If (List[pos].Way-NO＜=TotalExpendMethod) then (如果还有没用过的扩展规则)
Begin
If (可以使用当前扩展规则) then
Begin
(用第way条规则扩展当前节点)
List[pos+1].Situation:=ExpendNode(List[pos].Situation,List[pos].Way-NO);
List[pos+1].Way-N=0;
pos:=pos+1;
End-If;
End-If
Else Begin
pos:=pos-1;
End-Else
End-While;
[递归算法]
Var I :Integer;
Begin
If deepth＞Max then (空间达到极限,跳出本过程);
If Situation=Target then (找到目标);
For I:=1 to TotalExpendMethod do
Begin
BackTrack(ExpendNode(Situation,I),deepth+1);
End-For;
End;
范例：一个M*M的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。
Node(节点类型)＝Record
Situtation:TSituation（当前节点状态）;
Level:Integer(当前节点深度);
Last :Integer(父节点);
End
＜Var＞
List(节点表):Array[1..Max(最多节点数)] of Node(节点类型);
open(总节点数):Integer;
close(待扩展节点编号):Integer;
New-S:TSituation;(新节点)
＜Init＞
List＜-0;
open＜-1;
close＜-0;
List[1].Situation＜- 初始状态;
List[1].Level:=1;
List[1].Last:=0;
＜Main Program＞
While (close＜open(还有未扩展节点)) and
(open＜Max(空间未用完)) and
(未找到目标节点) do
Begin
close:=close+1;
For I:=1 to TotalExpendMethod do（扩展一层子节点）
Begin
New-S:=ExpendNode(List[close].Situation,I);
If Not (New-S in List) then
(扩展出的节点从未出现过)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Level:=List[close].Level+1;
List[open].Last:=close;
End-If
End-For;
End-While;
[深度搜索]
＜Var＞
Open:Array[1..Max] of Node;(待扩展节点表)
Close:Array[1..Max] of Node;(已扩展节点表)
openL,closeL:Integer;(表的长度)
New-S:Tsituation;(新状态)
＜Init＞
Open＜-0; Close＜-0;
OpenL＜-1;CloseL＜-0;
Open[1].Situation＜- 初始状态;
Open[1].Level＜-1;
Open[1].Last＜-0;
＜Main Program＞
While (openL＞0) and (closeL＜Max) and (openL＜Max) do
Begin
closeL:=closeL+1;
Close[closeL]:=Open[openL];
openL:=openL-1;
For I:=1 to TotalExpendMethod do（扩展一层子节点）
Begin
New-S:=ExpendNode(Close[closeL].Situation,I);
If Not (New-S in List) then
(扩展出的节点从未出现过)
Begin
openL:=openL+1;
Open[openL].Situation:=New-S;
Open[openL].Level:=Close[closeL].Level+1;
Open[openL].Last:=closeL;
End-If
End-For;
End;
范例：迷宫问题，求解最短路径和可通路径。
