启发式搜索——初识A*算法
A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。
一、何谓启发式搜索算法
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
二、初识A*算法
启发式搜索其实有很多的算法，比如：局部择优搜索法（如爬山法）、最好优先搜索法（Best-first）等等，当然A*也是。这些算法都使用了启发函数，但在具体选取最佳搜索节点时，使用的策略不同。比如局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点、父节点，而一直搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳（局部的），并不一定是全局的最佳。最好优先（Best-first）就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中，把当前节点和以前节点的估价值作比较，得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先（Best-first）的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到当前节点的最短路径值，h'(n)是n到目标的最短路经的启发值。g'(n)的值实际上很容易从到目前为止的搜索树上计算出来，不必专门定义计算公式，也就是根据搜索历史情况对g'(n)作出计算，显然g(n)>=g'(n)。h'(n)则依赖于启发信息，通常称为启发函数，是要对未来扩展的方向作出估计。A*算法是按f'(n)递增的顺序来排列可能被扩展的节点，因而优先扩展f'(n)值最小的节点，体现了最好优先（Best-first）的搜索思想。但有一点：h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的算法。实际也是。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。这是一个矛盾体，就看你怎样去掌握这个平衡了！
下面举个例子说明h(n)的不同设计方法：
1）将某一格局与目标格局比较，得到位置不符的数目；
缺点：没有考虑数字移动的距离。
2）计算将数字移动到目的位置所需移动的距离之和；
缺点：没有考虑牌排列的先后顺序，即若两个数字相邻，但与目的位置相比是相反的，则它们至少需要移动3次。
三．深入A*算法
在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短路径搜索的例子。
1、A*算法的程序编写原理
在“初识A*算法”中说过，A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）。
搜索过程中设置两个表：
OPEN和CLOSED。OPEN表保存
了所有已生成而未考察的节
点，CLOSED表中记录已访问过
的节点。算法中有一步是根据
估价函数重排OPEN表的节点。
这样循环中的每一步只考虑
OPEN表中状态最好的节点。具
体搜索过程如下：
1）始状态：OPEN=[A5]; CLOSED=[];
2）估算A5，取得所有子节点，并放入OPEN表中；
OPEN=[B4, C4, D6]; CLOSED=[A5]
3）估算B4，取得所有子节点，并放入OPEN表中；
OPEN=[C4, E5, F5, D6]; CLOSED=[B4, A5]
4）估算C4；取得所有子节点，并放入OPEN表中；
OPEN=[H3, G4, E5, F5, D6]; CLOSED=[C4, B4, A5] 5）估算H3，取得所有子节点，并放入OPEN表中；
OPEN=[O2, P3, G4, E5, F5, D6]; CLOSED=[H3, C4, B4, A5] 6）估算O2，取得所有子节点，并放入OPEN表中；
OPEN=[P3, G4, E5, F5, D6]; CLOSED=[O2, H3, C4, B4, A5] 7）估算P3，已得到解。算法结束
看了具体的过程，再看看伪程序吧。算法的伪程序如下：
Best_First_Search()
{
Open = [起始节点];
Closed = [];
while ( Open表非空 )
{
从Open中取得一个节点X, 并从OPEN表中删除.
if (X是目标节点)
{
求得路径PATH;
返回路径PATH;
}
for (每一个X的子节点Y)
{
if( Y不在OPEN表和CLOSED表中 )
{
求Y的估价值;
并将Y插入OPEN表中; //还没有排序
}
else if( Y在OPEN表中 )
{
if( Y的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值;
}
else //Y在CLOSED表中
{
if( Y的估价值小于CLOSED表的估价值 )
{
更新CLOSED表中的估价值;
从CLOSED表中移出节点, 并放入OPEN表中;
}
}
将X节点插入CLOSED表中;
按照估价值将OPEN表中的节点排序;
} //end for
} //end while
} //end func
伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法的程序与此是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。
下面，我们可以进入另一个重要的话题，用A*算法实现最短路径的搜索。在此之前你最好认真的理解前面的算法。
2、用A*算法实现最短路径的搜索
在实际应用中中，经常要涉及到最短路径的搜索，现在一个比较好的方法就是用A*算法进行设计。
先复习一下，A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分。g(n)是已经走过的代价，h(n)是n到目标的估计代价。在这个例子中g(n)表示在状态空间从起始节点到n节点的深度，h(n)表示n节点所在地图的位置到目标位置的直线距离。一个是状态空间，一个是实际的地图，不要搞错了。再详细点说，有一个物体A，在地图上的坐标是(xa,ya)，A所要到达的目标b的坐标是(xb,yb)。则开始搜索时，设置一个起始节点1，生成八个子节点2 - 9 因为有八个方向。如图：
先看搜索主函数：
void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)
{
NODE *Node, *BestNode;
int TileNumDest;
//得到目标位置，作判断用
TileNumDest = TileNum(sx, sy);
//生成Open和Closed表
OPEN=( NODE* )calloc(1,sizeof( NODE ));
CLOSED=( NODE* )calloc(1,sizeof( NODE ));
//生成起始节点，并放入Open表中
Node=( NODE* )calloc(1,sizeof( NODE ));
Node->g = 0;
//这是计算h值
Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); // should really use sqrt().
//这是计算f值，即估价值
Node->f = Node->g+Node->h;
Node->NodeNum = TileNum(dx, dy);
Node->x = dx;
Node->y = dy;
OPEN->NextNode=Node; // make Open List point to first node
for (;;)
{
//从Open表中取得一个估价值最好的节点
BestNode=ReturnBestNode();
//如果该节点是目标节点就退出
if (BestNode->NodeNum == TileNumDest) // if we've found the end, break and finish break;
//否则生成子节点
GenerateSuccessors(BestNode,sx,sy);
}
PATH = BestNode;
}
再看看生成子节点函数 GenerateSuccessors：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)
{
int x, y;
//依次生成八个方向的子节点
// Upper-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
}
看看最重要的函数GenerateSucc：
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy)
{
int g, TileNumS, c = 0;
NODE *Old, *Successor;
//计算子节点的 g 值
g = BestNode->g+1; // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor
TileNumS = TileNum(x,y); // identification purposes
//子节点再Open表中吗？
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to NULL then not in OPEN list,
// else it returns the Node in Old
{
//若在
for( c = 0; c <8; c++)
if( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's Children
// (or Successors).
break;
BestNode->Child[c] = Old;
//比较Open表中的估价值和当前的估价值（只要比较g值就可以了）
if ( g g ) // if our new g value is Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}
else //在Closed表中吗？
if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to NULL then not in OPEN list
// else it returns the Node in Old
{
//若在
for( c = 0; c<8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's
// Children (or Successors).
break;
BestNode->Child[c] = Old;
//比较Closed表中的估价值和当前的估价值（只要比较g值就可以了）
if ( g g ) // if our new g value is Parent = BestNode;
Old->g = g;
Old->f = g + Old->h; //再依次更新Old的所有子节点的估价值
PropagateDown(Old); // Since we changed the g value of Old, we need
// to propagate this new value downwards, i.e.
// do a Depth-First traversal of the tree!
}
}
else //不在Open表中也不在Close表中
{
//生成新的节点
Successor = ( NODE* )calloc(1,sizeof( NODE ));
Successor->Parent = BestNode;
Successor->g = g;
Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do sqrt(), but since we
// don't really
Successor->f = g+Successor->h; // care about the distance but just which branch
looks Successor->x = x; // better this should suffice. Anyayz it's faster.
Successor->y = y;
Successor->NodeNum = TileNumS;
//再插入Open表中，同时排序。
Insert(Successor); // Insert Successor on OPEN list wrt f
for( c =0; c <8; c++)
if ( BestNode->Child[c] == NULL ) // Add Old to the list of BestNode's
//Children (or Successors).
break;
BestNode->Child[c] = Successor;
}
}
仔细看看这个程序，你会发现，这个程序和前面说的伪程序有一些不同，在GenerateSucc函数中，当子节点在Closed表中时，没有将子节点从Closed表中删除并
放入Open表中。而是直接的重新的计算该节点的所有子节点的估价值（用PropagateDown 函数）。这样可以快一些。
/**************************************************************************/
/***************************** A* Algorithm *******************************/
/**************************************************************************/
struct NODE *FindPath(long sx,long sy,long dx,long dy)
{
struct NODE *Node, *BestNode;
int TileNumDest;
TileNumDest=TileNum((int)dx,(int)dy);
OPEN=(struct NODE *)calloc(1,sizeof( struct NODE ));
CLOSED=(struct NODE *)calloc(1,sizeof( struct NODE ));
Node=(struct NODE *)calloc(1,sizeof( struct NODE ));
Node->g=0;
Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy); // should really use sqrt().
Node->f=Node->g+Node->h;
Node->NodeNum=TileNum((int)sx,(int)sy);
Node->x=sx;
Node->y=sy;
OPEN->NextNode=Node; /* make Open List point to first node */
for (;;)
{
BestNode=(struct NODE *)ReturnBestNode();
if (BestNode->NodeNum == TileNumDest) /* if we've found the end, break and finish */ break;
GenerateSuccessors(BestNode,dx,dy);
}
return (BestNode);
}
struct NODE *ReturnBestNode(void)
{
struct NODE *tmp;
if (OPEN->NextNode == NULL)
{
printf("ERROR: no more nodes on OPEN\n");
RestoreKeyboard(); // restore BIOS keyboard handling
closegraph();
exit(0);
}
/* Pick Node with lowest f, in this case it's the first node in list
because we sort the OPEN list wrt lowest f. Call it BESTNODE. */
tmp=OPEN->NextNode; // point to first node on OPEN
OPEN->NextNode=tmp->NextNode; // Make OPEN point to nextnode or NULL.
/* Next take BESTNODE (or temp in this case) and put it on CLOSED */
tmp->NextNode=CLOSED->NextNode;
CLOSED->NextNode=tmp;
return(tmp);
}
void GenerateSuccessors(struct NODE *BestNode,long dx,long dy)
{
long x,y;
/* Upper-Left */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Upper */
if (FreeTile(x=(long)BestNode->x,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Upper-Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower-Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower */
if (FreeTile(x=(long)BestNode->x,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower-Left */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Left */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y))
GenerateSucc(BestNode,x,y,dx,dy);
}
void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long dy)
{
int g,TileNumS,c=0;
struct NODE *Old,*Successor;
g=BestNode->g+1; /* g(Successor)=g(BestNode)+cost of getting from BestNode to Successor */
TileNumS=TileNum((int)x,(int)y); /* identification purposes */
if ((Old=CheckOPEN(TileNumS)) != NULL) /* if equal to NULL then not in OPEN list, else it returns the Node in Old */ {
for(c=0;c<8;c++)
if(BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */
break;
BestNode->Child[c]=Old;
if (g < Old->g) /* if our new g value is < Old's then reset Old's parent to point to BestNode */
{
Old->Parent=BestNode;
Old->g=g;
Old->f=g+Old->h;
}
}
else if ((Old=CheckCLOSED(TileNumS)) != NULL) /* if equal to NULL then not in OPEN list, else it returns the Node in Old */
{
for(c=0;c<8;c++)
if (BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */
break;
BestNode->Child[c]=Old;
if (g < Old->g) /* if our new g value is < Old's then reset Old's parent to point to BestNode */
{
Old->Parent=BestNode;
Old->g=g;
Old->f=g+Old->h;
PropagateDown(Old); /* Since we changed the g value of Old, we need
to propagate this new value downwards, i.e.
do a Depth-First traversal of the tree! */
}
}
else
{
Successor=(struct NODE *)calloc(1,sizeof( struct NODE ));
Successor->Parent=BestNode;
Successor->g=g;
Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy); // should do sqrt(), but since we don't really
Successor->f=g+Successor->h; // care about the distance but just which branch looks
Successor->x=x; // better this should suffice. Anyayz it's faster.
Successor->y=y;
Successor->NodeNum=TileNumS;
Insert(Successor); /* Insert Successor on OPEN list wrt f */
for(c=0;c<8;c++)
if (BestNode->Child[c] == NULL) /* Add Old to the list of BestNode's Children (or Successors). */ break;
BestNode->Child[c]=Successor;
}
}
struct NODE *CheckOPEN(int tilenum)
{
struct NODE *tmp;
tmp=OPEN->NextNode;
while (tmp != NULL)
{
if (tmp->NodeNum == tilenum)
return (tmp);
else
tmp=tmp->NextNode;
}
return (NULL);
}
struct NODE *CheckCLOSED(int tilenum)
{
struct NODE *tmp;
tmp=CLOSED->NextNode;
while (tmp != NULL)
{
if (tmp->NodeNum == tilenum)
return (tmp);
else
tmp=tmp->NextNode;
}
return (NULL);
}
void Insert(struct NODE *Successor)
{
struct NODE *tmp1,*tmp2;
long f;
if (OPEN->NextNode == NULL)
{
OPEN->NextNode=Successor;
return;
}
/* insert into OPEN successor wrt f */
f=Successor->f;
tmp1=OPEN;
tmp2=OPEN->NextNode;
while ((tmp2 != NULL) && (tmp2->f < f))
{
tmp1=tmp2;
tmp2=tmp2->NextNode;
}
Successor->NextNode=tmp2;
tmp1->NextNode=Successor;
}
void PropagateDown(struct NODE *Old)
{
int c,g;
struct NODE *Child, *Father;
g=Old->g; // alias.
for(c=0;c<8;c++)
{
if ((Child=Old->Child[c])==NULL) // create alias for faster access.
break;
if (g+1 < Child->g)
{
Child->g=g+1;
Child->f=Child->g+Child->h;
Child->Parent=Old; // reset parent to new path.
Push(Child); // Now the Child's branch need to be
} // checked out. Remember the new cost must be propagated down.
}
while (Stack->NextStackPtr != NULL)
{
Father=Pop();
for(c=0;c<8;c++)
{
if ((Child=Father->Child[c])==NULL) /* we may stop the propagation 2 ways: either */ break;
if (Father->g+1 < Child->g) /* there are no children, or that the g value of */
{ /* the child is equal or better than the cost we're propagating */ Child->g=Father->g+1;
Child->f=Child->g+Child->h;
Child->Parent=Father;
Push(Child);
}
}
}
}
/**************************************************************************/ /* STACK FUNCTIONS */ /**************************************************************************/
void Push(struct NODE *Node)
{
struct STACK *tmp;
tmp=( struct STACK *)calloc(1,sizeof(struct STACK));
tmp->NodePtr=Node;
tmp->NextStackPtr=Stack->NextStackPtr;
Stack->NextStackPtr=tmp;
}
struct NODE *Pop()
{
struct NODE *tmp;
struct STACK *tmpSTK;
tmpSTK=Stack->NextStackPtr;
tmp=tmpSTK->NodePtr;
Stack->NextStackPtr=tmpSTK->NextStackPtr;
free(tmpSTK);
return (tmp);
}
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。
实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解8数码问题 （1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n） 其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。 （2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。 实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路 八数码问题的求解算法 （1）盲目搜索 宽度优先搜索算法、深度优先搜索算法 （2）启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)
实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰
一、实验内容： 使用启发式搜索算法求解8数码问题。 1、编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个
1、程序源代码 #include
编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月
南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）：
启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法
The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent https://www.doczj.com/doc/571010110.html,pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency. This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data. Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm
启发式搜索——初识A*算法
A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
启发式图搜索算法 摘要：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。进行搜索技术一般需要某些有关具体问题领域的特性的信息。 关键词：启发式搜索；估价函数；有序搜索；A*算法； 正文： 启发式图搜索的意义因为无信息图搜索算法的效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。所以引入了启发式图搜索算法。 启发式图搜索算法就是进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。关于图搜索的启发式搜索算法就叫做启发式图搜索算法。 启发式图搜索策略：假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。 启发信息按其用途可分为下列3种： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。 (3) 用于决定某些应该从搜索树中抛弃或修剪的节点。 启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。所谓的估价函数就是为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 有序搜索应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索 (best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 有序状态空间搜索算法 (1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。
启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，
以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型
人工智能基础实验报告 实验名称：八数码问题 姓名：张俊 学号：2220092333 指导老师：邓安生
启发式搜索算法 1. 实验内容： 使用启发式搜索算法求解8数码问题。 ⑴ 编制程序实现求解8数码问题A *算法，采用估价函数 ()()()() w n f n d n p n ??=+???， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 ⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 2. 实验目的 熟练掌握启发式搜索A *算法及其可采纳性。 3. 实验原理 八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。 4.源代码 #include
实验二：A*算法 一、实验目的 了解启发式搜索算法的基本思想，掌握A*算法的基本原理和步骤。学会对于算法的正确应用，解决实际生活中的问题。学会区分与盲目搜索算法的不同之处。 二、实验环境 PC机一台，VC++6.0 三、实验原理 A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC （Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS 一样，进行启发式的搜索。 A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 A*算法的公式为：f(n)=g(n)+h(n)，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。 对于函数h(n)，估算距离常用的方法有： 曼哈顿距离：定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|。
人工智能技术报告 启发式搜索 产生背景： 何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 定义： 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径， 可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)
是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了。 算法举例 启发算法有：蚁群算法，遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。 分析：蚁群算法 蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，指的是一种源于自然现象的算法，也是一种meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。 蚂蚁觅食原理： 自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后， 它们仍然能很快重新找到新的最佳路线。
启发式搜索A和A*搜索算法 首先什么是启发式搜索？启发式搜索就是利用当前问题有关的信息作为启发式信息，这些信息是能够提升查找效率、减少搜索时间和减少查询次数的。为了利用这些信息，我们定义了一个估价函数h(x)，h(x)是对当前状态x的一个估计，它表示x状态到目标点的距离。那么由它表示的意义我们可以知道，当h(x)等于0时，说明到达了目标点。 一、A和A*搜搜算法介绍 A搜索算法就是使用了估价函数的搜索算法，估价函数的一般形式是f(x)=g(x)+h(x)。其任务就是估计待搜索有希望程度，赢一次给它们排定次序。其中g(x)代表从初始结点到x结点的实际代价，h(x)是从当前结点到目标结点的代价，这个代价是估计出来的。 A*搜索算法是估价函数满足一定条件的算法，其限制条件是f(x)=g(x)+h(x)，代价函数g(x)大于0，h(x)的值不大于x到目标结点的实际代价h*(x)。 二、A和A*搜索算法运用 搜索算法如下： ①将初始节点S0放入Open表中。 ②如Open表为空，则搜索失败，退出。 ③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n。 ④如果节点n是目标节点，则搜索成功，求得一个解，退出。 ⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出相应的估价函数值。 ⑥把节点n的子节点放到Open表中。 ⑦对Open表中的各节点按估价函数值从小到大排列；。 ⑧转到②。 启发式通常用于资讯充份的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定
Heuristic Search 启发式搜索 译 by 陈雪(QQ:53352894) 必要条件 ?递归算法 主要概念 启发式搜索的主要目标是使用一个估价函数去判断所有状态的“好坏”，以提高搜索找到解的效率。 通常，估价函数表示成一个函数或是一个状态，这个函数叫做“估价函数”例如：?迷宫寻找出路的时候，到出口的欧几里德距离 D=[(xI-xj)^2+(yI-yj)^2]1/2。式中，D是点i和点j之间的距离； xI xj 是第i个点的坐标；yI yj是第j个点的坐标。（译者注） ?当尝试在一场跳棋比赛中获胜时，能吃掉对手的最多棋子子 设计估价函数 直观地看，估价函数越优秀，搜索就更好（快）。问题是：怎么评价估价函数的好坏呢？ 估价函数的好坏，取决于它评估一个状态好坏的能力。例如，迷宫的例子，怎么计算到出口的距离？欧几里德距离也许非常的坏，甚至是非常小的迷宫，它也可能绕很多的路： 一般来说，估价函数越好，搜索就越快。一般来说，搜索时间和估价函数的准确性如下图： 注意！一个似乎很“傻”的估价函数可以大大地提高程序的效率！（如果它非常完美地被使用）
另一个重要概念是“可接受”，一个可接受的估价函数表示对于每个点都不存在“低估”的情况。例如，迷宫的欧几里德距离启发函数是“低估”的，刚才的图例很清楚地说明了这一点。 方法1：启发式剪枝 最简单也是最常用的启发式搜索是利用估价函数来剪枝。假设我们的问题是要求找最小总花费。对于一个可接受的估价函数，当前花费是A，启发函数返回了B，当前子问的最优解是A+B。如果找到的一个解一个花费是C，C 随机启发式搜索算法的性能分析 随机启发式搜索算法如演化算法、蚁群算法及人工免疫算法等是通过模拟大自然现象、过程及一些生物特性等提出的一类通用算法。实践证明,这类随机启发式搜索算法在科学研究及工程实际问题中获得了极大的成功,尤其是针对一些结构不清晰的复杂优化问题,以及在计算资源有限的情况下表现出了卓越的性能。 为了更好的理解随机启发式搜索算法的工作机制,进一步指导算法设计及应用,研究人员迫切希望为这类算法建立严密的理论基础。然而,由于随机启发式搜索算法的随机性、群体性等特点,使得算法在运行过程中表现出非常复杂的动态随机行为,增加了理论研究的难度。 当前,理论研究成果相对偏少。本文从随机启发式搜索算法的理论研究角度出发,关注随机启发式搜索算法求解优化问题的时间复杂性,以及在NP-完全(难)优化问题上的近似性能;研究问题类型与算法特征之间的关系;进一步探索随机 启发式搜索算法求解典型优化问题的有效性,以期完善和增强随机启发式搜索算法的理论基础。 本文的主要工作如下:(1)研究了演化算法求解最多叶子生成树问题(MLST) 的性能。最多叶子生成树问题是NP完全理论中一个经典的组合优化问题,在网络设计及电路布局等实际问题上有较强的应用背景。 该问题是在一个无向连通图中找出一棵生成树,使得生成树中所含叶子节点最多。许多启发式算法如演化算法用于求解该问题。 然而,对于演化算法在NP难问题的求解性能方面我们仍知之甚少。本文从理论上研究了演化算法求解MLST问题的近似性能。 指出对于MLST问题,算法(1+1)EA能够分别在期望多项式时间2O(nm)和 4O(nm)内获得5近似比和3近似比,其中n为无向连通图中的节点数,m为边数。同时,我们研究了(1+1)EA算法在两个MLST问题实例上的性能,并且指出局部搜索算法在该实例上容易陷入局部最优,而(1+1)EA算法能够逃脱局部最优并最终获得最优解。 (2)研究了蚁群算法在二次指派问题(QAP)上的性能。二次指派问题是最具挑战性的组合优化问题之一。 该问题在物流运输和选址等许多实际问题中有着广泛的应用。理论上研究了ACO算法在极其难的QAP问题上的性能。 给出了一个简单的(1+1)MMAA算法在QAP问题上的最坏情况界。并指出对于QAP问题,(1+1)MMAA算法能够获得一定的近似保证。 最后,通过构建一个QAP实例,表明蚁群优化算法在该实例上要优于 2-exchange局部搜索算法,进一步证实了蚁群算法的有效性。(3)分析比较了基于免疫的超变异算子与标准位变异算子在优化问题上的性能。 人工免疫系统在许多复杂的真实优化问题中获得了广泛的应用并取得了极大成功。然而,人工免疫算法的理论研究远远滞后于其在许多领域的应用研究。 对于人工免疫算法的运行机制以及其有效性研究还处于探索的初级阶段,当前也迫切需要为这类算法建立坚实的理论基础。本文从理论上分析了一种被用于免疫算法中的连续高频变异算子在优化问题上的性能,并在两个拟布尔函数及两个真实组合优化问题的实例上分析比较了连续高频变异算子与标准位变异算子、局部变异算子的性能,证明了连续高频变异算子在这些实例上要优于标准位变异算子及局部变异算子。 也进一步揭示了问题类型与算法特征之间的关系,从理论上证实了连续高频 人工智能导论 启发式图搜索 院系名称：地球物理与信息工程学院 专业名称：计算机科学与技术 学号： 姓名： 完成日期2015年 6月 16 日 一、过程A描述： ①OPEN := (s), f(s) := g(s) + h(s); ②LOOP : IF OPEN=() THEN EXIT(FAIL); ③n := FIRST(OPEN); ④IF GOAL(n) THEN EXIT(SUCCESS); ⑤REMOVE(n, OPEN) , ADD(n, CLOSED); ⑥EXPAND(n) {} , 计算f(n,) = g(n, ) + h(); g(n, )是从s通过n到的耗散值，f(n,)是从s通过n、到目标节点耗散值的估计； ·ADD( , OPEN), 标记到n的指针。 ·IF f(n,) 第23卷 第3期华侨大学学报(自然科学版)Vo l.23 N o.3 2002年7月Journal of Huaqiao U niver sity(N atural Science)Jul.2002 文章编号 1000-5013(2002)03-0313-04 启发搜索算法在运筹学中的应用 汤永清 张银明 (华侨大学信息科学与工程学院,泉州362011) 摘要 运筹学中的运输、指派问题具有广泛的应用性.启发式的搜索算法的核心问题是构造启发 函数,用启发函数的思想去解决传统的运筹学问题,可以提高求解的效率.文中从启发式的搜索 算法角度出发,介绍了如何构造启发函数,并用其解决运筹学中的运输与指派问题. 关键词 人工智能,启发函数,运筹学 中图分类号 T P18∶O22文献标识码 A 运筹学是一门系统科学.运筹学是运用科学方法,尤其是用数学方法去研究各种系统,优化途径及方案,为决策者提供科学决策的依据.运筹学中有一类问题具有特殊性,如运输问题、调运问题,且有很多解决的方法.其本质,就是通过多次迭代获得一个最优分配解.如对于运输问题,解决方法较多地使用表上作业法的最小元素法.分配问题多采用整数规划的匈牙利法.分配问题可以认为是供需为1的运输问题的特例来处理. 1 启发式搜索算法 启发式的搜索算法广泛应用于人工智能,是用来寻找最优解的一种方法.它的本质是部分的放弃了算法“一般化、通用化”的概念,把所要解的问题的具体领域内的知识加入到算法中去,以提高算法的效率.其基本原理是在搜索的过程中对遇到的新状态,先利用估值函数得到1个估计值.然后,根据估计值的大小来,确定下一步的状态将从哪一步开始继续前进,以此来实行最佳优先搜索.每一步的搜索都是根据估计值来判断下一步的搜索方向,因此如何设计估值函数就成为问题求解的核心.用数学公式描述,f(x)=(1- (x))g(x)+ (x)h(x).其中f(x)代表估值函数,g(x)为从初始结点到n个结点的最小代价, (x)为权函数(可以是一个动态值,也可以为常数,一般情况下可以取值为1或0),h(x)表示从n结点到目标结点的最小代价,也称之为启发函数. 目前比较流行的有两种方法.(1)令h(x)≡0,即仅以已经花费的代价g(x)来进行估计,这有点接近于广度优先法.它虽说能找到完备解,但花费的工作量不一定是最小的.这是因为它不利用任何启发式信息.(2)与上一种完全相反,不是舍弃h(x)而是舍弃g(x),即令f(x) =h(x).这种方法的实质,在于把解的最优性置于次要地位,首先考虑的是如何尽快地求得一 收稿日期 2001-12-09 作者简介 汤永清(1974-),男,助教 1、程序源代码 #include <> #include<> struct node{ i nt a[3][3];//用二维数组存放8数码 int hx;//函数h（x）的值，表示与目标状态的差距 s truct node *parent;//指向父结点的指针 s truct node *next;//指向链表中下一个结点的指针 }; //------------------hx函数-------------------// int hx(int s[3][3]) {//函数说明：计算s与目标状态的差距值 i nt i,j; i nt hx=0; i nt sg[3][3]={1,2,3,8,0,4,7,6,5}; f or(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++; return hx; } //-------------hx函数end----------------------// //-------------extend扩展函数----------------// struct node *extend(node *ex) { //函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值 i nt i,j,m,n; //循环变量 i nt t; //临时替换变量 i nt flag=0; i nt x[3][3];//临时存放二维数组 s truct node *p,*q,*head; head=(node *)malloc(sizeof(node));//head p=head; q=head; h ead->next=NULL;//初始化 f or(i=0;i<3;i++)//找到二维数组中0的位置 { for(j=0;j<3;j++)随机启发式搜索算法的性能分析
人工智能导论 启发式图搜索
人工智能中的启发搜索算法在运筹学中的应用
启发式搜索算法解决八数码问题(C语言)
相关主题
文本预览