一步一步写算法（之 A*算法）
大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
【 声明：版权全部，欢迎转载，请勿用于商业用途。】
在前面的博客其中，事实上我们已经讨论过寻路的算法。只是，当时的演示样例图中，可选的路径是唯一的。我们挑选一个算法，就是说要把这个唯一的路径选出来，怎么选呢？当时我们就是採用穷尽递归的算法。然而，今天的情形有点不太一样了。在什么地方呢？那就是今天的路径有n条，这条路径都能够达到目的地，然而我们在挑选的过程中有一个要求，那就是挑选的路径距离最短？有没有什么办法呢？
那么，这时候就要A*算法就能够排上用场了。A*算法和普通的算法有什么差别呢？我们能够用一个演示样例说明一下：
/*
* 0 0 0 0 0
* 1 1 1 1 1
* 1 0 0 0 1
* 1 0 0 0 1
* A 1 1 1 1
*/这是一个5*5的数组。如果我们从array[1][0]出发，目标为A点。我们发现，在图中有两种方法能够到达目的地，可是往下直达的方法最短。那么怎么找到这个最短的算法呢？朋友们能够好好思考一下。
我们能够把时光回到到达的前几个步骤？我们为什么要选方向朝下的点，而不选水平方向的点？原因不复杂，就是由于全部点中，当时我们要选的这个点和目标点之间距离最短。那么这中间，路径的选择有没有发生改变呢？事实上是有可能的，由于选路的过程本省就是一个pk的过程，我们所能做的就是寻找当时那个离目标近期的点而已，而这个点是时刻变化的，所以最后选出来的路应该是这种。
/*
* 0 0 0 0 0
* 1 0 0 0 0
* 1 0 0 0 0
* 1 0 0 0 0
* A 0 0 0 0
*/算法编程算法，应该怎么改动呢？当然首先定义一个数据结构？
typedef struct _VALUE
{
int x;
int y;
}VALUE;然后呢，寻找到和目标点距离最短的那个点，
int find_most_nearest_neigh(VALUE data[], int length, int x, int y)
{
int index;
int number;
int current;
int median;
if(NULL == data || 0 == length)
return -1;
current = 0;
number = (int) sqrt((data[0].x - x) * (data[0].x - x)+ (data[0].y - y) * (data[0].y - y));
for(index = 1; index < length; index ++){
median = (int) sqrt((data[index].x - x) * (data[index].x - x)+ (data[index].y - y) * (data[index].y - y));
if(median < number){
number = median;
current = index;
}
}
return current;
}寻找到这个点，一切都好办了，那么如今我们就须要又一次对data进行处理，毕竟有些点须要弹出，另一些新的点须要压入处理的。
VALUE* updata_data_for_queue(VALUE* data, int length, int* newLen)
{
int index;
int count;
int max;
VALUE* pData;
if(NULL == data || 0 == length || NULL == newLen)
return NULL;
max = length << 2;
pData = (VALUE*)malloc(max * sizeof(VALUE));
memset(pData, 0, max * sizeof(VALUE));
count = 0;
for(index = 0; index < length; index ++){
if(check_pos_valid(data[index].x, data[index].y - 1)){
pData[count].x = data[index].x;
pData[count].y = data[index].y -1;
count ++;
}
if(check_pos_valid(data[index].x -1, data[index].y)){
pData[count].x = data[index].x -1;
pData[count].y = data[index].y;
count ++;
}
if(check_pos_valid(data[index].x, data[index].y + 1)){
pData[count].x = data[index].x;
pData[count].y = data[index].y +1;
count ++;
}
if(check_pos_valid(data[index].x + 1, data[index].y)){
pData[count].x = data[index].x + 1;
pData[count].y = data[index].y;
count ++;
}
}
*newLen = count;
return pData;
}有了上面的函数之后，那么find_path就十分简单了。
void find_path(int x, int y)
{
while(/* 最短距离不为0 */){
/* 更新列表 */
/* 寻找近期点 */
};
}总结：
（1）A*的重点在于设计权重推断函数，选择最佳下一跳
（2）A*的目标是已知的
（3）A*尤其适合于网格型的路径查找
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/118546.html原文链接：https://javaforall.cn