数学建模常用算法—搜索算法
一、回溯算法 回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法]＜Type＞ Node(节点类型)＝Record
Situtation:TSituation（当前节点状态）;
Way-NInteger（已使用过的扩展规则的数目）;
End
＜Var＞
List(回溯表):Array of Node;
pos(当前扩展节点编号):Integer;
＜Init＞
List＜-0;
pos＜-1;
List.Situation＜-初始状态;
＜Main Program＞
While (pos＞0(有路可走)) and ([未达到目标]) do
Begin
If pos＞=Max then (数据溢出,跳出主程序);
List.Way-N=List.Way-No+1;
If (List.Way-NO＜=TotalExpendMethod) then (如果还有没用过的扩展规则)
Begin
If (可以使用当前扩展规则) then
Begin
(用第way条规则扩展当前节点)
List.Situation:=ExpendNode(List.Situation,List.Way-NO);
List.Way-N=0;
pos:=pos+1;
End-If;
End-If
Else Begin
pos:=pos-1;
End-Else
End-While;
[递归算法]
Procedure BackTrack(Situation:TSituation;deepth:Integer);
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的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。
评价：回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。
二、深度搜索与广度搜索
深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构.
[广度搜索]
＜Type＞
Node(节点类型)＝Record
Situtation:TSituation（当前节点状态）;
Level:Integer(当前节点深度);
Last :Integer(父节点);
End
＜Var＞
List(节点表):Array of Node(节点类型);
open(总节点数):Integer;
close(待扩展节点编号):Integer;
New-S:TSituation;(新节点)
＜Init＞
List＜-0;
open＜-1;
close＜-0;
List.Situation＜- 初始状态;
List.Level:=1;
List.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.Situation,I);
If Not (New-S in List) then
(扩展出的节点从未出现过)
Begin
open:=open+1;
List.Situation:=New-S;
List.Level:=List.Level+1;
List.Last:=close;
End-If
End-For;
End-While;
[深度搜索]
＜Var＞
Open:Array of Node;(待扩展节点表)
Close:Array of Node;(已扩展节点表)
openL,closeL:Integer;(表的长度)
New-S:Tsituation;(新状态)
＜Init＞
Open＜-0; Close＜-0;
OpenL＜-1;CloseL＜-0;
Open.Situation＜- 初始状态;
Open.Level＜-1;
Open.Last＜-0;
＜Main Program＞
While (openL＞0) and (closeL＜Max) and (openL＜Max) do
Begin
closeL:=closeL+1;
Close:=Open;
openL:=openL-1;
For I:=1 to TotalExpendMethod do（扩展一层子节点）
Begin
New-S:=ExpendNode(Close.Situation,I);
If Not (New-S in List) then
(扩展出的节点从未出现过)
Begin
openL:=openL+1;
Open.Situation:=New-S;
Open.Level:=Close.Level+1;
Open.Last:=closeL;
End-If
End-For;
End;
范例：迷宫问题，求解最短路径和可通路径。
评价：广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。
第二部分 搜索算法的优化
一、双向广度搜索
广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。
范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。
问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点
所连接的两条路径所拼成的路径就是最优解。
对广度搜索算法的改进：
1、添加一张节点表，作为反向扩展表。
2、在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。
3、在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。
对双向广度搜索算法的改进：
略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。
二、分支定界
分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。
范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。
问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。
对回溯算法的改进：
1、添加一个全局变量BestAnswer，记录当前最优解。
2、在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。
哦
页:
[1]