算法A

‘壹’ A*算法优化

A算法是游戏中路径搜索的常见算法。Dijkstra是最短路径的经典算法，A算法的思路基本上和Dijkstra算法一致，在Dijkstra算法的基础上增加了启发函数，也就是：

f(n) = g(n) + h(n)

其中，n是路径上某一点，g(n)是从出发点到该点的cost，h(n)是关于该点的启发函数，通常是对从该点到目标花费的一个估计，例如到目标的直线距离或者曼哈顿距离。 A算法每次选择f(n)最小的点，然后更新所有g(n)。
如果你明白Dijkstra算法，那么在这里h(n) = 0 的话，A算法就和Dijkstra算法一样了。
本文不详细讲解A算法，需要详细了解A算法的具体过程的，参见以下两篇文章：

理解A*算法的具体过程
A*算法详解

A*算法优化的关键在于h(n)的选择。 一个启发函数h(n)被称为admissible的，是指h(n)的估计，不会超过节点N到目标的实际花费。
如果h(x)满足以下条件，h(x)被称为单调的(monotone, or consistent)。 对于任意一条边(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的长度

如果满足这个条件，就意味着没有任何节点需要被处理多次，也就是说，在Dijkstra算法中，新加入一个节点会导致已添加节点中cost降低的情况不会存在，也就不需要去更新已添加节点(称为close set)。

如果一个启发函数是单调的，那么该启发函数一定是admissible的。如果该启发函数是admissible的，那么可以证明A*在同类算法中搜寻到最短的路径。

问题出在这里：如果我们更在意的是搜索的时间空间花费，而不是最优结果，那么A*算法就有优化空间。所以我们放松要求，修改我们的启发函数，使得我们搜寻到的路径不会比最佳路径差太多，就是优化算法，称为ε-admissible算法。

有多种ε-admissible算法，在此只举例最简单直接的一种： 加权A*(静态加权)算法。

假如ha(n)是一个admissible的启发函数，我们选取新的启发函数hw(n) = ε ha(n)，其中ε>1 作为启发函数。就可以在某种程度上进行优化。 下图1是使用ha(n)作为启发式算法，下图2是使用hw(n)作为启发式算法，其中ε取5.

图1：ha(x)作为启发算法

图2：hn(x)作为启发算法

可以看出，ha(n)可以找到最小路径，但是多了许多无用的搜索；而hw(n)找到的不是最优路径，但是减少了大量无用搜索。
其他的优化算法思路类似都是在于启发函数的选择。详见参考文献。

参考文献：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic

‘贰’ 计算机算法题

如果计算机每秒可执行操作10^5次，0.015*10^5=1500.
对于算法A：n^2+2n+50=1500，解为n=37
对于算法B：20n+10^3=1500，解为n=25
所以，在计算机每秒可执行操作10^5这个条件下算法A更合适。因为在程序响应时间0.015秒里，算法A可以解决n=37规模的问题，比算法B的n=25更大。

如果计算机每秒可执行次数为10^7次，则哪个算法B更合适。
0.015*10^7=150000.
对于算法A：n^2+2n+50=150000，解为n=386
对于算法B：20n+10^3=150000，解为n=7450
所以，在计算机每秒可执行操作10^7这个条件下算法更合适。因为在程序响应时间0.015秒里，算法B可以解决n=7450规模的问题，比算法A的n=386更大。

‘叁’ 人工智能 A*算法原理

A 算法是启发式算法重要的一种，主要是用于在两点之间选择一个最优路径，而A 的实现也是通过一个估值函数

上图中这个熊到树叶的 曼哈顿距离 就是蓝色线所表示的距离，这其中不考虑障碍物，假如上图每一个方格长度为1，那么此时的熊的曼哈顿距离就为9.
起点（X1,Y1）,终点（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我们也可以通过几何坐标点来算出曼哈顿距离，还是以上图为例，左下角为（0，0）点，熊的位置为（1，4），树叶的位置为（7，1），那么H=|7-1|+|1-4|=9。

还是以上图为例，比如刚开始熊位置我们会加入到CLOSE列表中，而熊四周它可以移动到的点位我们会加入到OPEN列表中，并对熊四周的8个节点进行F=G+H这样的估值运算，然后在这8个节点中选中一个F值为最小的节点，然后把再把这个节点从OPEN列表中删除，加入到Close列表中，从接着在对这个节点的四周8个节点进行一个估值运算，再接着依次运算，这样说大家可能不是太理解，我会在下边做详细解释。

从起点到终点，我们通过A星算法来找出最优路径

我们把每一个方格的长度定义为1，那从起始点到5位置的代价就是1，到3的代价为1.41，定义好了我们接着看上图，接着运算

第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算，运算结果如上图，这其中大家看到一个小箭头都指向了起点，这个箭头就是指向父节点，而open列表的G值都是根据这个进行计算的，意思就是我从上一个父节点运行到此处时所需要的总代价，如果指向不一样可能G值就不一样，上图中我们经过计算发现1点F值是7.41是最小的，那我们就选中这个点，并把1点从OPEN列表中删除，加入到CLOSE列表中，但是我们在往下运算的时候发现1点的四周，2点，3点和起始点这三个要怎么处理，首先起始点已经加入到了CLOSE，他就不需要再进行这种运算，这就是CLOSE列表的作用，而2点和3点我们也可以对他进行运算，2点的运算，我们从1移动到2点的时候，他需要的代价也就是G值会变成2.41，而H值是不会变的F=2.41+7=9.41，这个值我们发现大于原来的的F值，那我们就不能对他进行改变（把父节点指向1，把F值改为9.41，因为我们一直追求的是F值最小化），3点也同理。

在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41，此时我们系统就可能随机选择一个点然后进行下一步运算，现在我们选中的是3点，然后对3点的四周进行运算，结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大，所以不发生改变。我们在看整个OPEN列表中，也就2点的7.41值是最小的，那我们就选中2点接着运算。

我们在上一部运算中选中的是1点，上图没有把2点加入OPEN列表，因为有障碍物的阻挡从1点他移动不到2点，所以没有把2点加入到OPEN列表中，整个OPEN列表中3的F=8是最小的，我们就选中3，我们对3点四周进行运算是我们发现4点经过计算G=1+1=2，F=2+6=8所以此时4点要进行改变，F变为8并把箭头指向3点（就是把4点的父节点变为3），如下图

我们就按照这种方法一直进行运算，最后 的运算结果如下图

而我们通过目标点位根据箭头（父节点），一步一步向前寻找最后我们发现了一条指向起点的路径，这个就是我们所需要的最优路径。 如下图的白色选中区域

但是我们还要注意几点

最优路径有2个

这是我对A*算法的一些理解，有些地方可能有BUG，欢迎大家指出，共同学习。

‘肆’ a算法不一定能找到目标节点

A算法不一定能找到目标结点(A)

A.正确

B.错误

算法，是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题。

执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始。

经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题。

并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数。

阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

‘伍’ 排列a的算法是什么

计算方法：

（1）排列数公式

排列用符号A(n,m)表示，m≦n。

计算公式是：A(n,m)＝n(n-1)(n-2)……(n-m+1)＝n!/(n-m)!

此外规定0!=1，n!表示n(n-1)(n-2)…1

例如：6!=6x5x4x3x2x1=720，4!=4x3x2x1=24。

（2）组合数公式

组合用符号C(n,m)表示，m≦n。

公式是：C(n,m)=A(n,m)/m!或C(n,m)=C(n,n-m)。

例如：C(5,2)=A(5,2)/[2!x(5-2)!]=(1x2x3x4x5)/[2x(1x2x3)]=10。

两个常用的排列基本计数原理及应用：

1、加法原理和分类计数法：

每一类中的每一种方法都可以独立地完成此任务。两类不同办法中的具体方法，互不相同(即分类不重)。完成此任务的任何一种方法，都属于某一类(即分类不漏)。

2、乘法原理和分步计数法：

任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务。各步计数相互独立。只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。

‘陆’ A*算法怎么验算

验算步骤如下：
a初值为12时，a+=a-=a*=a结果为0
步骤：
这个表达式的运算是从右向左的：
1.
a*=a：a=a*a=12*12=144
2.
a-=144:
a=a-144=144-144=0
3.
a+=0:
a=a+0=0+0=0。算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、JacquesHerbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年EmilLeonPost的Formulation1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。