文中提及的一些观点和理论，并非全部个人原创，而是自己的总结和心得， 仅供个人学习编程使用！ 

启发式搜索算法从听说有这个名字开始到正真学习她，应该间隔了一年多的时间吧！当我接触他之后，就有种相见恨晚的感觉！因为她完美的剪枝思想，不仅弥补了通常盲目搜索算法的不足，提高了程序的运行效率，而且给了我一种处理搜索问题的“优化思想”！

下面就让我简单的说一下个人对两种启发式搜索算法，A*和ID_A*算法的理解。开始之前，先推荐比较好的几份资料。

• 《A*算法详解》  Sunway；个人认为他的这篇介绍性的文章写的非常到位，由浅入深的带领我们进入A*算法的世界。强烈建议，学习启发搜索先看这篇文章。（推荐）
• 《A*算法》(ppt) 尚福华； 从理论层面上分析了A*算法的正确性。很值得我们在学了A*算法一段时间之后，回过来分析和思考的。（推荐♦♦♦♦♦）
• 《算法艺术与信息学竞赛》（刘如佳，黄亮 著）P168。介绍的比较笼统，适合有一定基础的人来体会。

先给出一个A*算法的模型Sunway。

Best_First_Search() {
    Open = [起始节点S0];  Closed = [NULL];
    while (Open表非空) {
        从Open中取得一个节点X，并从OPEN表中删除。
        if (X是目标节点) {
            求得一组最优路径PATH；返回路径PATH；
        }
        for (每一个X的子节点Y) {
            if (Y不在OPEN表和CLOSE表中) {
                求Y的估价值；并将Y插入OPEN表中；//还没有排序  
            }
            else
                if (Y在OPEN表中) {
                     if (Y的估价值小于OPEN表的估价值)
                         更新OPEN表中的估价值；
                }
                else {//Y在CLOSE表中  
                    if (Y的估价值小于CLOSE表的估价值) {
                        更新CLOSE表中的估价值；
                        从CLOSE表中移出节点，并放入OPEN表中；
                    }
                }
        }//end for  
        将X节点插入CLOSE表中；
        按照估价值f()将OPEN表中的节点排序；        
    }//end while  
}//end func  

谈到A* 算法，就要涉及到三个函数：估价函数f()  =  实际代价函数g()  +   启发函数 h();

对于状态空间中的某个节点n定义：f*(n)为初始节点src， 约束警告过节点n到达目标节点的最小代价值（f(n)是对f(n)的一个估价，因此成为估价函数）。则f*(n)应包含两部分：一是：从目标节点到达节点N时的最小代价，记为g*() (g() 是g*()的一个上界)；另外一部分是从节点n到达目标节点的最小代价，记为h*(), (因为h()使我们事先无法知晓的，所以，我们用h()来估计，因此，称为估价函数h())。所以，g()是对g*()的一个估价，h()是对h*()的一个估价。

  对于实际代价函数g()，我们在搜索到当前节点的时候，有可能最小代价的路径还没有找到，所以 有g() >= g*(), 即 g() 是g*()的一个上界。

 对于估价函数g(), 这里要重点介绍一下了，尚福华的ppt里面说的很清晰，这里就引用一下。h(n)的单调限制： 

Procedure Expand(State: StateType);
Begin
    for i := 1 to OperandCount(State) do
    Begin
         NewState := DoOperand(State, i);
         NewState.h := CalculateH(NewState);
         NewState.g := State.g + 1;
         NewState.f := NewState.g + NewState.h;
         NewState.f := State;
         NewState.LastOp := OperandCount;
         i := FindInsertTableTwo(NewState);  // 在表二中查找，找不到就插入
         If i = 0 then
             InsertToTableOne(NewState);
         ELse if NewState.f < State[i].f then // 新状态优于原状态就替换。
             ReplaceInTableOne(NewState, i);
    End;
End;

procedure Astar(depth: integer);
begin
    Calculate of InitialState;
    TableOne := [InitialState];            // 表一：待扩展节点集
    TableTwo := [initialState];            // 表二：待扩展和已扩展节点集
    ok := false;
    while not ok and not TableOne Empty do // 没有找到解且待扩展节点非空
    begin
         State := ExtractMinInTableOne;    // 找f值最小的待扩展节点
         If IsAnswer(State) then           // 找到解并输出解
             Begin
                 PrintState(state);
                 ok := true;
             End
        Else Expand(State);                //扩展节点
    End;
    If not Ok then NoAnswer;
End;
             

Procedure IDAstar(StartState);
Begin 
     PathLimit := H(startState) -1;  //限定每次搜索的最大深度，初始值为初始状态h();
     Success := false;
     Repeat
          inc(PathLimit);
	  StartState.g = 0;
          Push(OpenStack, StartState);
          Repeat
		CurrentState := Pop(OpenStack);
		If Solution(CurrentState) then  // 判定当前状态是否是目的状态
			Success = True;         // 是的话，玲标记为真。
		Else if PathLimit >= CurrentState.g = H(CurrentState) then
			ForEach Child(CurrentState) do // 计算所有子状态的f()并入列。
				Push(OpenState, Child(CurrentState));
          Untill Success or empty of OpenStack
      Untill Success or ResourceLimitsReached;
End;