搜索算法基础---(转帖2)

tbs005

第二部分　搜索算法的优化

　　一、双向广度搜索

　　广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。

　　范例：有N个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。

　　问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点
所连接的两条路径所拼成的路径就是最优解。

　　对广度搜索算法的改进：

　　1、添加一张节点表，作为反向扩展表。
　　2、在while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for循环。
　　3、在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。

　　对双向广度搜索算法的改进：

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

　　二、分支定界

　　分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。

　　范例：在一个商店中购物，设第I种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。

　　问题分析：显然，折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数向零递减搜索，设A为以打完折扣后优惠的价格，C为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中a为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1。

　　对回溯算法的改进：

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

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

　　三、A*算法

　　A*算法中更一般的引入了一个估价函数f,其定义为f=g+h。其中g为到达当前节点的耗费，而h表示对从当前节点到达目标节点的耗费的估计。其必须满足两个条件：

　　1、h必须小于等于实际的从当前节点到达目标节点的最小耗费h*。

　　2、f必须保持单调递增。
　　A*算法的控制结构与广度搜索的十分类似，只是每次扩展的都是当前待扩展节点中f值最小的一个，如果扩展出来的节点与已扩展的节点重复，则删去这个节点。如果与待扩展节点重复，如果这个节点的估价函数值较小，则用其代替原待扩展节点，具体算法描述如下：

　　范例：一个3*3的棋盘中有1-8八个数字和一个空格，现给出一个初始态和一个目标态，要求利用这个空格，用最少的步数，使其到达目标态。

　　问题分析：预期值定义为h=|x-dx|+|y-dy|。
　　　　　估价函数定义为f=g+h。


＜Type＞
　Node(节点类型)＝Record
　Situtation:TSituation（当前节点状态）;
　g:Integer;(到达当前状态的耗费)
　h:Integer;(预计的耗费)
　f:Real;(估价函数值)
　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＜- 初始状态;
　＜Main Program＞
　While (close＜open(还有未扩展节点)) and
　　(open＜Max(空间未用完)) and
　　(未找到目标节点) do
　Begin
　　Begin
　 　close:=close+1;
　　　For I:=close+1 to open do (寻找估价函数值最小的节点)
　　　Begin
　　　　if List.f＜List[close].f then
　　　　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)＜List[same].f then
　　　　　　(扩展出来的节点的估价函数值小于与其相同的节点)
　　　　　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*算法出现数据溢出时，从待扩展节点中取出若干个估价函数值较小的节点，然后放弃其余的待扩展节点，从而可以使搜索进一步的进行下去。


[em17] [em17] 未完!