数学建模常用算法—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[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*算法出现数据溢出时，从待扩展节点中取出若干个估价函数值较小的节点，然后放弃其余的待扩展节点，从而可以使搜索进一步的进行下去。

百年孤独

中文还有什么需要，请给我留言

百年孤独

大家还有什么需要，请给我留言

百年孤独

大家还有什么建模方面需要的资料请留言