首页 > 代码库 > 一步一步写算法（之 A*算法）
一步一步写算法（之 A*算法）
原文: 一步一步写算法（之 A*算法）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
在前面的博客当中，其实我们已经讨论过寻路的算法。不过，当时的示例图中，可选的路径是唯一的。我们挑选一个算法，就是说要把这个唯一的路径选出来，怎么选呢？当时我们就是采用穷尽递归的算法。然而，今天的情形有点不太一样了。在什么地方呢？那就是今天的路径有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 = http://www.mamicode.com/(VALUE*)malloc(max * sizeof(VALUE));> 有了上面的函数之后，那么find_path就十分简单了。
void find_path(int x, int y){ while(/* 最短距离不为0 */){ /* 更新列表 */ /* 寻找最近点 */ };}
总结：
（1）A*的重点在于设计权重判断函数，选择最佳下一跳
（2）A*的目标是已知的
（3）A*尤其适合于网格型的路径查找
一步一步写算法（之 A*算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。