一步一步写算法（之 A*算法）

    在前面的博客当中，其实我们已经讨论过寻路的算法。不过，当时的示例图中，可选的路径是唯一的。我们挑选一个算法，就是说要把这个唯一的路径选出来，怎么选呢？当时我们就是采用穷尽递归的算法。然而，今天的情形有点不太一样了。在什么地方呢？那就是今天的路径有n条，这条路径都可以达到目的地，然而我们在挑选的过程中有一个要求，那就是挑选的路径距离最短？有没有什么办法呢？

    那么，这时候就要A*算法就可以排上用场了。A*算法和普通的算法有什么区别呢？我们可以用一个示例说明一下：

view plaincopy to clipboardprint?

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的过程，我们所能做的就是寻找当时那个离目标最近的点而已，而这个点是时刻变化的，所以最后选出来的路应该是这样的。

view plaincopy to clipboardprint?

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. */  

    算法编程算法，应该怎么修改呢？当然首先定义一个数据结构？

view plaincopy to clipboardprint?

1. typedef struct _VALUE  
2. {  
3.     int x;  
4.     int y;  
5. }VALUE;  

    然后呢，寻找到和目标点距离最短的那个点，

view plaincopy to clipboardprint?

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进行处理，毕竟有些点需要弹出，还有一些新的点需要压入处理的。

view plaincopy to clipboardprint?

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就十分简单了。

view plaincopy to clipboardprint?

1. void find_path(int x, int y)  
2. {  
3.   while(/* 最短距离不为0 */){  
4.   
5.       /* 更新列表 */  
6.   
7.       /* 寻找最近点 */  
8.   
9.   };  
10. }  

总结：

    （1）A*的重点在于设计权重判断函数，选择最佳下一跳

    （2）A*的目标是已知的

    （3）A*尤其适合于网格型的路径查找

分享到：

上一篇：一步一步写算法（之克鲁斯卡尔算法 下）

下一篇：一步一步写算法（之 可变参数）