本文目录一览：
- 1、估价函数不唯一吗
- 2、估价函数中,hx表示什么意思
- 3、估价函数就是启发式函数吗
- 4、什么是估价函数
- 5、star值怎么算
- 6、A算法的好处
- 7、A算法野人传教士问题，估价函数h（n）为什么等于m+n-2b？
- 8、A算法 和 最佳优先搜索算法（Best-First-Search）
- 9、急求井字游戏的编程源代码(MFC格式)
估价函数不唯一吗
是。估价函数需要根据题意来设计，并没有唯一标准，所以估价函数不唯一。用来估计结点重要性，定义为从初始结点S0出发，约束经过结点n到达目标结点Sg的所有路径中最小路径代价的估计值，一般形式:f(n)=g(n)+h(n)，其中，g(n)是从初始结点S0到结点n的实际代价，h(n)是从结点n到目标结点Sg的最优路径的估计代价。
估价函数中,hx表示什么意思
节点x到目标节点Sg的最优路径的估计代价。估价函数是目前状态到最终状态所需代价的估计值。估价函数中，hx表示节点x到目标节点Sg的最优路径的估计代价。在估价函数中g(x)为初始节点S0到节点x已实际付出的代价。h(x)是从节点x到目标节点Sg的最优路径的估计代价。主要由h(x)来体现所以h(x)称作启发函数。
估价函数就是启发式函数吗
是。根据查询估价函数相关资料得知，估价函数就是启发式函数。启发式指的是一个在一个搜寻树的节点上定义的函数，用于评估从此节点到目标节点最便宜的 路径。启发式通常用于资讯充分的搜寻算法。
什么是估价函数
star值怎么算
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}
上图是和上面Dijkstra算法使用同一个路网，相同的起点终点，用A*算法的情况，计算的点数从起始点逐渐向目标点方向扩展，计算的节点数量明显比Dijkstra少得多，效率很高，且能得到最优解。
A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。
A算法的好处
其实A*算法也是一种最好优先的算法只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但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)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
A算法野人传教士问题，估价函数h（n）为什么等于m+n-2b？
h(n)表示状态转换后左岸剩余人数的最小值。
当前状态是（m,n,b），
当b = 1 时，船在左岸，船最多可以坐2人，所以状态转换后左岸最少剩余人数为m+n-2*b，即m+n-2；
当b = 0 时，船在右岸，此时需要修道士或者野人从右岸划船到左岸，最少过去1人，因此状态转换后左岸最少剩余人数为m+n+1；
综合两种情况，状态转变后左岸剩余人数大于等于m+n-2*b，最小值是m+n-2*b，因此h(n)设定为h(n) = m+n-2*b
A算法 和 最佳优先搜索算法（Best-First-Search）
最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。 BFS算法不能保证找到的路径是一条最短路径，但是其计算过程相对于Dijkstra 算法会快很多 。
最佳优先搜索是一种启发式搜索算法。广度优先搜索和深度优先搜索都属于穷举类型的搜索，需要依次遍历所有的节点，当空间非常大的时候，这种方式的效率就会非常差。而启发式的搜索是对状态控件中的每个点进行评估，然后选出最好的位置。
启发估价函数公式为：
n表示当前的点，g(n)为从起始点到点n的实际代价，h(n)为从点n到目标点的估价。
（图片来源于网络）
A*算法将BFS算法和Dijkstra算法结合在一起，结合两算法的优点，既可以查找最短路径的，有拥有和BFS差不多的效率。
（图片来源于网络）
A*算法详解
模拟寻路的地址
急求井字游戏的编程源代码(MFC格式)
“井字棋”游戏（又叫“三子棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。“井字棋”的棋盘很简单，是一个3×3的格子，很像中国文字中的“井”字，所以得名“井字棋”。“井字棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“井字棋”是一方首先三子连成一线就胜利。
井字棋（英文名Tic-Tac-Toe）
井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。
想起小时候上课喜欢玩井字棋，只要一张草稿纸、一支笔、同桌两人就可以玩了。上体育课，也可以拿着树枝在沙坑里玩。但一直感觉这游戏太简单了，后来接触了五子棋，着迷了一阵，但水平总是很差，便也不玩了。
一字棋游戏极小极大分析法
设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。
用叉号表示MAX，用圆圈代表MIN。
比如右图中就是MIN取胜的棋局。
为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：
设棋局为P，估价函数为e(P)。
(1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)
(2) 若P是MAX必胜的棋局，则e(P)＝+∞。
(3) 若P是B必胜的棋局，则e(P)＝-∞。
比如P如右图示,则e(P)=6-4=2
要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局
都是相同的棋局(在博弈中，一宇棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。图3.15画出了经过两层搜索生成的博弈树，静态估值记在端节点下面，倒推值记在圆圈内。
由于右图所示位置具有最大的倒推值，它应当选取为MAX的第一步（正好是MAX的最好的优先走步）。
现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层，产生如图3.16所示的搜索图。
现在图中MAX有两个可能“最好的”优先走步，假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索，产生如图3.17所示的树。
在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为—∞。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。
按极大极小算法编程下一字棋的演示(右图，可以点击操作)．．．
我们就利用Visual Basic编写一个“井字棋”的小游戏。
【设计思路】
首先，我们要知道，“井字棋”游戏是一款典型的棋类游戏，游戏时一方式是电脑，另一方是玩家。所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。这是我们要考虑的第一个问题。
其次，由于与玩家对战的是计算机，所以我们要编写一个过程（Chuqi），它可以使程序模拟人的思维与人下棋（其实就是“人工智能”的体现），这个Chuqi过程也是本游戏软件的关键。此外，我们还要编写两个过程（Lianxian和Shuying），Lianxian过程用来时刻判断棋盘中是否有三个棋子连成一线；Shuying过程用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。
以上几个问题就是该“井字棋”游戏实现的关键思路。....
