a算法

‘壹’ 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算法a* 算法有什么特点

A*算法：A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好
A* （A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。
公式表示为： f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n) 是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。
如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

‘叁’ 搜索算法中,A算法A*算法的区别（急）

A算法一般指某个搜索算法的朴素的思路
A*指使用了启发式搜索之后的算法,也就是运算速度会快很多,但不一定能保证最后得到最优解

‘肆’ A*算法的介绍

A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。

‘伍’ A*算法的时间复杂度是多少

从数学上定义，给定算法A，如果存在函数F(n)，当n=k时，F(k)表示算法A在输入规模为k的情况下的运行时间，则称F(n)为算法A的时间复杂度。这里首先要明确输入规模的概念。关于输入规模，不是很好下定义，非严格的讲，输入规模是指算法A所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数。为了简单起见，总是假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,……,k,…… 对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为了解决这个问题，做以下两个说明： 1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。 2.对于输入特性的差异，将从数学上进行精确分析并带入函数解析式。

‘陆’ 矩阵a*算法是什么

矩阵A*表示A矩阵的伴随矩阵。

伴随矩阵的定义：某矩阵A各元素的代数余子式，组成一个新的矩阵后再进行一下转置，叫做A的伴随矩阵。

某元素代数余子式就是去掉矩阵中某元素所在行和列元素后的形成矩阵的行列式，再乘上-1的（行数+列数）次方。

伴随矩阵的求发：当矩阵是大于等于二阶时：

主对角元素是将原矩阵该元素所在行列去掉再求行列式。

非主对角元素是原矩阵该元素的共轭位置的元素去掉所在行列求行列式乘以(-1)^(x+y) x,y为该元素的共轭位置的元素的行和列的序号，序号从1开始的。

主对角元素实际上是非主对角元素的特殊情况，因为x=y,所以(-1)^(x+y)=(-1)^(2x)=1,一直是正数，没必要考虑主对角元素的符号问题。

‘柒’ A*算法的其它算法

启发式搜索其实有很多的算法
比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。像局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，并没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？

‘捌’ 爬山算法 与A算法有什么不同

爬山算法从当前的节点开始，和周围的邻居节点的值进行比较。
A*把所有节点分成2组，一组已访问，一组未访问，然后选择其中最优点加入已访问组。
爬山算法速度比A*快，但会舍弃部分最优解。

‘玖’ 排列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步才能完成此任务。各步计数相互独立。只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。