C++算法之A*算法
发布时间:2020-12-16 07:44:26 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 在前面的博客当中,其实我们已经讨论过寻路的算法。不过,当时的示例图中,可选的路径是唯一的。我们挑选一个算法,就是说要把这个唯一的路径选出来,
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
在前面的博客当中,其实我们已经讨论过寻路的算法。不过,当时的示例图中,可选的路径是唯一的。我们挑选一个算法,就是说要把这个唯一的路径选出来,怎么 选呢?当时我们就是采用穷尽递归的算法。然而,今天的情形有点不太一样了。在什么地方呢?那就是今天的路径有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* 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,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*尤其适合于网格型的路径查找 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |