C++算法之A*算法

在前面的博客當中，其實我們已經討論過尋路的算法。不過，當時的示例圖中，可選的路徑是唯一的。我們挑選一個算法，就是說要把這個唯一的路徑選出來，怎么 選呢？當時我們就是采用窮盡遞歸的算法。然而，今天的情形有點不太一樣了。在什么地方呢？那就是今天的路徑有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 
*/  

</pre> 

     這是一個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 
*/

</pre> 

     算法編程算法，應該怎么修改呢？當然首先定義一個數據結構？

 
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;

}


</pre> 

     尋找到這個點，一切都好辦了，那么現在我們就需要重新對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 = (VALUE*)malloc(max * sizeof(VALUE));  
memset(pData, 0, 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;  

}
</pre> 

     有了上面的函數之后，那么find_path就十分簡單了。


void find_path(int x, int y)

{

  while(/ 最短距離不為0 /){


  /* 更新列表 */  

  /* 尋找最近點 */  


};

}
</pre> 

 總結：

     （1）A的重點在于設計權重判斷函數，選擇最佳下一跳

     （2）A的目標是已知的

     （3）A*尤其適合于網格型的路徑查找