数学建模常用算法—搜索算法

百年孤独

一、回溯算法 　回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： [非递归算法]
＜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;
　　[递归算法]

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[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;
　范例：迷宫问题，求解最短路径和可通路径。

评价：广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。

第二部分　搜索算法的优化

一、双向广度搜索
广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。
范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。
　问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点
所连接的两条路径所拼成的路径就是最优解。

百年孤独

对广度搜索算法的改进：

　1、添加一张节点表，作为反向扩展表。

　2、在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。
　3、在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。
　对双向广度搜索算法的改进：

　　略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。

　二、分支定界
　分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。
范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。
问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。

　　对回溯算法的改进：

　1、添加一个全局变量BestAnswer，记录当前最优解。

2、在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。

lpsszhm

哦