数学建模常用算法—A*算法
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 of Node(节点类型);
open(总节点数):Integer;
close(待扩展节点编号):Integer;
New-S:Tsituation;(新节点)
＜Init＞
List＜-0;
open＜-1;
close＜-0;
List.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.f then
Begin
交换List和List;
End-If;
End-For;
End;
For I:=1 to TotalExpendMethod do（扩展一层子节点）
Begin
New-S:=ExpendNode(List.Situation,I)
If Not (New-S in List) then
(扩展出的节点未与已扩展的节点重复)
Begin
If Not (New-S in List) then
(扩展出的节点未与待扩展的节点重复)
Begin
open:=open+1;
List.Situation:=New-S;
List.Last:=close;
List.g:=List.g+cost;
List.h:=GetH(List.Situation);
List.f:=List.h+List.g;
End-If
Else Begin
If List.g+cost+GetH(New-S)＜List.f then
(扩展出来的节点的估价函数值小于与其相同的节点)
Begin
List.Situation:= New-S;
List.Last:=close;
List.g:=List.g+cost;
List.h:=GetH(List.Situation);
List.f:=List.h+List.g;
End-If;
End-Else;
End-If
End-For;
End-While;
对A*算法的改进--分阶段A*：
当A*算法出现数据溢出时，从待扩展节点中取出若干个估价函数值较小的节点，然后放弃其余的待扩展节点，从而可以使搜索进一步的进行下去。
中文还有什么需要，请给我留言{:3_49:}
大家还有什么需要，请给我留言{:3_49:}
大家还有什么建模方面需要的资料请留言
页:
[1]