一步一步写算法(之 A算法).doc

软件英才网软件行业驰名招聘网站有需要请联系我们一步一步写算法(之 A* 算法) 在前面的博客当中, 其实我们已经讨论过寻路的算法。不过, 当时的示例图中, 可选的路径是唯一的。我们挑选一个算法, 就是说要把这个唯一的路径选出来, 怎么选呢?当时我们就是采用穷尽递归的算法。然而, 今天的情形有点不太一样了。在什么地方呢?那就是今天的路径有 n 条,这条路径都可以达到目的地,然而我们在挑选的过程中有一个要求,那就是挑选的路径距离最短?有没有什么办法呢? 那么,这时候就要 A* 算法就可以排上用场了。 A* 算法和普通的算法有什么区别呢?我们可以用一个示例说明一下: [cpp] view plain copy ?/* ?*00000 ?*11111 ?*10001 ?*10001 ?*A1111 ?*/ 这是一个 5*5 的数组。假设我们从 array[1][0] 出发,目标为 A 点。我们发现,在图中有两种方法可以到达目的地, 但是往下直达的方法最短。那么怎么找到这个最短的算法呢?朋友们可以好好思考一下。我们可以把时光回到到达的前几个步骤?我们为什么要选方向朝下的点, 而不选水平方向的点?原因不复杂, 就是因为所有点中, 当时我们要选的这个点和目标点之间距离最短。那么这中间,路径的选择有没有发生改变呢?其实是有可能的,因为选路的过程本省就是一个 pk 的过程, 我们所能做的就是寻找当时那个离目标最近的点而已,而这个点是时刻变化的,所以最后选出来的路应该是这样的。[cpp] view plain copy ?/* ?*00000 ??*10000 ??*10000 ??*10000 ??*A0000 ??*/ 算法编程算法,应该怎么修改呢?当然首先定义一个数据结构? [cpp] view plain copy ?? typedef struct _VALUE ??{ 软件英才网软件行业驰名招聘网站有需要请联系我们?? int x; ?? int y; ??}VALUE; 然后呢,寻找到和目标点距离最短的那个点, [cpp] view plain copy ?? 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; ?? c