A搜索算法的基本思想是什么

❶ 搜索算法中,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星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

❸ A*算法的原理

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*搜寻算法的简介

速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用于测量（scales）：
g’(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A*工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用，然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。
你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。
速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。
在游戏中，路径潜在地花费了许多存储空间，特别是当路径很长并且有很多物体需要寻路时。路径压缩，导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路径仍然用了许多存储空间，可以限制路径长度，这就回到了经典的时间-空间折衷法：为了节省空间，信息可以被丢弃，稍后才重新计算它。

❺ 什么是局部搜索算法

局部搜索算法是从爬山法改进而来的。
简单来说，局部搜索算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
在计算机科学中，局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。
1、局部搜索算法的基本思想：
在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
2、局部搜索的优点：
简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。
3、局部搜索广泛应用：
计算机科学（主要是人工智能）、数学、运筹学、工程学、生物信息学中各种很难找到全局最优解的计算问题。

❻ A*搜寻算法的算法描述

f(x) = g(x) + h(x)
function A*(start,goal)
var closed := the empty set
var q := make_queue(path(start))
while q is not empty
var p := remove_first(q)
var x := the last node of p
if x in closed
continue
if x = goal
return p
add x to closed
foreach y in successors(x)
enqueue(q, p, y)
return failure A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。假设你的游戏有两种地形，平原和山地，在平原中的移动代价是1而在山地的是3，那么A星算法就会认为在平地上可以进行三倍于山地的距离进行等价搜寻。 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较，这并不比把3和1比较差。然而，在山地上行动有时可能会优于绕过山脚下进行行动。所以花费更多时间寻找一个绕过山的算法并不经常是可靠的。 同样的，想要达成这样的目标，你可以通过减少在山脚下的搜索行为来打到提高A星算法的运行速率。弱项如此可以将A星算法的山地行动耗费从3调整为2即可。这两种方法都会给出可靠地行动策略 。

❼ 选择排序算法的思想是什么

次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。

直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此继续，最后a[1]与a[10]比较，如果a[1]<a[10]，则将a[1]与a[10]交换，否则不交换。这样在a[1]中得到的数就是数组a的最大值（一共进行了9次比较）。

为了在a[2]中得到次大值，应将a[2]与它后面的元素a[3]，a[4]，...，a[10]进行比较。这样经过8次比较，在a[2]是将得到次大值。

如此继续，直到最后a[9]与a[10]比较，将大数放于a[9]，小数放于a[10]，全部排序到此结束。
从上面可以看出，对于10个数，需进行9趟比较，每一趟的比较次数是不一样的。第一趟需比较9次，第二趟比较8次，...，最后一趟比较1次。

以上数组元素的排序，用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素，第一个元素与外循环i有关的，用a[i]标识，第二个元素是与内循环j有关的，用a[j]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为i+1,i+2,...。