首页 一步一步写算法(之_A算法)

一步一步写算法(之_A算法)

举报
开通vip

一步一步写算法(之_A算法) 一步一步写算法(之 A*算法) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     在前面的博客当中,其实我们已经讨论过寻路的算法。不过,当时的示例图中,可选的路径是唯一的。我们挑选一个算法,就是说要把这个唯一的路径选出来,怎么选呢?当时我们就是采用穷尽递归的算法。然而,今天的情形有点不太一样了。在什么地方呢?那就是今天的路径有n条,这条路径都可以达到目的地,然而我们在挑选的过程中有一个要求,那就是挑选的路径距离最短?有没有什么办法呢?     那...

一步一步写算法(之_A算法)
一步一步写算法(之 A*算法) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     在前面的博客当中,其实我们已经讨论过寻路的算法。不过,当时的示例图中,可选的路径是唯一的。我们挑选一个算法,就是说要把这个唯一的路径选出来,怎么选呢?当时我们就是采用穷尽递归的算法。然而,今天的情形有点不太一样了。在什么地方呢?那就是今天的路径有n条,这条路径都可以达到目的地,然而我们在挑选的过程中有一个要求,那就是挑选的路径距离最短?有没有什么办法呢?     那么,这时候就要A*算法就可以排上用场了。A*算法和普通的算法有什么区别呢?我们可以用一个示例说明一下: [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. /*  2. *       0  0  0  0  0  3. *       1  1  1  1  1  4. *       1  0  0  0  1    5. *       1  0  0  0  1     6. *       A  1  1  1  1  7. */       这是一个5*5的数组。假设我们从array[1][0]出发,目标为A点。我们发现,在图中有两种方法可以到达目的地,但是往下直达的方法最短。那么怎么找到这个最短的算法呢?朋友们可以好好思考一下。     我们可以把时光回到到达的前几个步骤?我们为什么要选方向朝下的点,而不选水平方向的点?原因不复杂,就是因为所有点中,当时我们要选的这个点和目标点之间距离最短。那么这中间,路径的选择有没有发生改变呢?其实是有可能的,因为选路的过程本省就是一个pk的过程,我们所能做的就是寻找当时那个离目标最近的点而已,而这个点是时刻变化的,所以最后选出来的路应该是这样的。 [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. /*  2. *       0  0  0  0  0  3. *       1  0  0  0  0  4. *       1  0  0  0  0    5. *       1  0  0  0  0     6. *       A  0  0  0  0  7. */       算法编程算法,应该怎么修改呢?当然首先定义一个数据结构? [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. typedef struct _VALUE   2. {   3.     int x;   4.     int y;   5. }VALUE;       然后呢,寻找到和目标点距离最短的那个点, [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. int find_most_nearest_neigh(VALUE data[], int length, int x, int y)   2. {   3.     int index;   4.     int number;   5.     int current;   6.     int median;   7.    8.     if(NULL == data || 0 == length)   9.         return -1;   10.    11.     current = 0;   12.     number = (int) sqrt((data[0].x - x) * (data[0].x - x)+ (data[0].y - y) *  (data[0].y - y));   13.    14.     for(index = 1; index < length; index ++){   15.         median = (int) sqrt((data[index].x - x) * (data[index].x - x)+ (data[index].y - y) *  (data[index].y - y));   16.            17.         if(median < number){   18.             number = median;   19.             current = index;   20.         }   21.     }   22.    23.     return current;   24. }       寻找到这个点,一切都好办了,那么现在我们就需要重新对data进行处理,毕竟有些点需要弹出,还有一些新的点需要压入处理的。 [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. VALUE* updata_data_for_queue(VALUE* data, int length, int* newLen)   2. {   3.     int index;   4.     int count;   5.     int max;   6.     VALUE* pData;   7.    8.     if(NULL == data || 0 == length || NULL == newLen)   9.         return NULL;   10.    11.     max = length << 2;   12.     pData = (VALUE*)malloc(max * sizeof(VALUE));   13.     memset(pData, 0, max * sizeof(VALUE));   14.    15.     count = 0;   16.     for(index = 0; index < length; index ++){   17.         if(check_pos_valid(data[index].x, data[index].y - 1)){   18.             pData[count].x = data[index].x;   19.             pData[count].y = data[index].y -1;   20.             count ++;   21.         }   22.    23.         if(check_pos_valid(data[index].x -1, data[index].y)){   24.             pData[count].x = data[index].x -1;   25.             pData[count].y = data[index].y;   26.             count ++;    27.         }   28.    29.         if(check_pos_valid(data[index].x, data[index].y + 1)){   30.             pData[count].x = data[index].x;   31.             pData[count].y = data[index].y +1;   32.             count ++;   33.         }   34.    35.         if(check_pos_valid(data[index].x + 1, data[index].y)){   36.             pData[count].x = data[index].x + 1;   37.             pData[count].y = data[index].y;   38.             count ++;    39.         }   40.     }   41.    42.     *newLen = count;   43.     return pData;   44. }       有了上面的函数之后,那么find_path就十分简单了。 [cpp] view plain HYPERLINK "http://blog.csdn.net/feixiaoxing/article/details/6982932" \o "copy" copy 1. void find_path(int x, int y)   2. {   3.   while(/* 最短距离不为0 */){   4.    5.       /* 更新列 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf  */   6.    7.       /* 寻找最近点 */   8.    9.   };   10. }   总结:     (1)A*的重点在于 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 权重判断函数,选择最佳下一跳     (2)A*的目标是已知的     (3)A*尤其适合于网格型的路径查找
本文档为【一步一步写算法(之_A算法)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_448426
暂无简介~
格式:doc
大小:51KB
软件:Word
页数:0
分类:互联网
上传时间:2018-09-10
浏览量:4