1.任務(wù)描述

本關(guān)任務(wù)：

• 了解有信息搜索策略的算法思想；
• 能夠運用計算機語言實現(xiàn)搜索算法；
• 應(yīng)用A*搜索算法解決羅馬尼亞問題；

2.相關(guān)知識

A*搜索

• 算法介紹

A*算法常用于 二維地圖路徑規(guī)劃，算法所采用的啟發(fā)式搜索可以利用實際問題所具備的啟發(fā)式信息來指導(dǎo)搜索，從而減少搜索范圍，控制搜索規(guī)模，降低實際問題的復(fù)雜度。

• 算法原理：

A*算法的原理是設(shè)計一個代價估計函數(shù)：其中 **評估函數(shù)F(n)**是從起始節(jié)點通過節(jié)點n的到達(dá)目標(biāo)節(jié)點的最小代價路徑的估計值，函數(shù)G(n)是從起始節(jié)點到n節(jié)點的已走過路徑的實際代價，函數(shù)H(n)是從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價 。

函數(shù) H(n)表明了算法使用的啟發(fā)信息，它來源于人們對路徑規(guī)劃問題的認(rèn)識，依賴某種經(jīng)驗估計。根據(jù) F(n)可以計算出當(dāng)前節(jié)點的代價，并可以對下一次能夠到達(dá)的節(jié)點進(jìn)行評估。

采用每次搜索都找到代價值最小的點再繼續(xù)往外搜索的過程，一步一步找到最優(yōu)路徑。

3.編程要求

羅馬尼亞問題：agent在羅馬尼亞度假，目前位于 Arad 城市。agent明天有航班從Bucharest 起飛，不能改簽退票。

現(xiàn)在你需要尋找到 Bucharest 的最短路徑，在右側(cè)編輯器補充void A_star(int goal,node &src,Graph &graph)函數(shù)，使用編寫的搜索算法代碼求解羅馬尼亞問題：

4.測試說明

平臺會對你編寫的代碼進(jìn)行測試：

預(yù)期輸出：

solution: 0-> 15-> 14-> 13-> 1-> end
cost:418

5.實驗過程

下面是關(guān)于非補充部分的代碼解釋：

1.宏定義每個城市名和編號

#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define L 9
#define M 10
#define N 11
#define O 12
#define P 13
#define R 14
#define S 15
#define T 16
#define U 17
#define V 18
#define Z 19

2.記錄啟發(fā)函數(shù)h數(shù)組，即從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價

int h[20] =//從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價
{ 366,0,160,242,161,
178,77,151,226,244,
241,234,380,98,193,
253,329,80,199,374 };

3.定義城市節(jié)點的結(jié)構(gòu)體

struct node
{int g;                              //從起始節(jié)點到n節(jié)點的已走過路徑的實際代價int h;                              //從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價int f;                              //代價估計函數(shù)int name;node(int name, int g, int h) {       //構(gòu)造函數(shù)this->name = name;this->g = g;this->h = h;this->f = g + h;};//重載運算符bool operator <(const node& a)const { return f < a.f; }
};

4.定義圖結(jié)構(gòu)，記錄圖中各節(jié)點和邊的信息

class Graph        //圖結(jié)構(gòu)
{
public:Graph() {memset(graph, -1, sizeof(graph));   //圖初始化為-1，代表無邊}int getEdge(int from, int to) {       //獲取邊的開銷return graph[from][to];}void addEdge(int from, int to, int cost) {    //新增一條邊及其開銷if (from >= 20 || from < 0 || to >= 20 || to < 0)return;graph[from][to] = cost;}void init() {                        //圖初始化addEdge(O, Z, 71);addEdge(Z, O, 71);addEdge(O, S, 151);addEdge(S, O, 151);addEdge(Z, A, 75);addEdge(A, Z, 75);addEdge(A, S, 140);addEdge(S, A, 140);addEdge(A, T, 118);addEdge(T, A, 118);addEdge(T, L, 111);addEdge(L, T, 111);addEdge(L, M, 70);addEdge(M, L, 70);addEdge(M, D, 75);addEdge(D, M, 75);addEdge(D, C, 120);addEdge(C, D, 120);addEdge(C, R, 146);addEdge(R, C, 146);addEdge(S, R, 80);addEdge(R, S, 80);addEdge(S, F, 99);addEdge(F, S, 99);addEdge(F, B, 211);addEdge(B, F, 211);addEdge(P, C, 138);addEdge(C, P, 138);addEdge(R, P, 97);addEdge(P, R, 97);addEdge(P, B, 101);addEdge(B, P, 101);addEdge(B, G, 90);addEdge(G, B, 90);addEdge(B, U, 85);addEdge(U, B, 85);addEdge(U, H, 98);addEdge(H, U, 98);addEdge(H, E, 86);addEdge(E, H, 86);addEdge(U, V, 142);addEdge(V, U, 142);addEdge(I, V, 92);addEdge(V, I, 92);addEdge(I, N, 87);addEdge(N, I, 87);}private:int graph[20][20];              //圖數(shù)組，用來保存圖信息，最多有20個節(jié)點
};

5.一些數(shù)據(jù)結(jié)構(gòu)的定義

bool list[20];                          //用于記錄節(jié)點i是否在openList集合中
vector<node> openList;                  //擴展節(jié)點集合
bool closeList[20];                     //已訪問節(jié)點集合
stack<int> road;                        //路徑
int parent[20];                         //父節(jié)點，用于回溯構(gòu)造路徑

1.補充void A_star(int goal, node& src, Graph& graph)函數(shù)

主要思想是利用一個估價函數(shù)f(n)來評估每個節(jié)點n的優(yōu)先級，f(n)由兩部分組成：g(n)表示從起點到節(jié)點n的實際代價，h(n)表示從節(jié)點n到終點的預(yù)估代價。A*算法每次選擇f(n)最小的節(jié)點進(jìn)行擴展，直到找到終點或者沒有可擴展的節(jié)點為止

代碼如下：

void A_star(int goal, node& src, Graph& graph)//A*搜索算法
{openList.push_back(src);                    //擴展集合加入起始節(jié)點sort(openList.begin(), openList.end());     //排序擴展集合的節(jié)點，以取出代價最小的節(jié)點while (!openList.empty()){/********** Begin **********/node curNode = openList[0];             //取出擴展集合第一個節(jié)點，即代價最小的節(jié)點if (curNode.name == goal) {             //如果當(dāng)前節(jié)點就是目標(biāo)節(jié)點，則退出return;}openList.erase(openList.begin());       //將當(dāng)前節(jié)點從擴展列表中刪除closeList[curNode.name] = true;         //將當(dāng)前節(jié)點加入已訪問節(jié)點list[curNode.name] = false;             //標(biāo)記當(dāng)前節(jié)點已不在擴展集合中for (int i = 0; i < 20; i++) {          //開始擴展當(dāng)前節(jié)點，即找到其鄰居節(jié)點if (graph.getEdge(i, curNode.name) == -1) {     //若不是當(dāng)前節(jié)點的鄰居節(jié)點，跳到下一個節(jié)點continue;}if (closeList[i]) {                             //若此節(jié)點已加入已訪問集合closeList，也跳到下一個節(jié)點continue;}int g1 = curNode.g + graph.getEdge(i, curNode.name);    //計算起始節(jié)點到當(dāng)前節(jié)點i的g值int h1 = h[i];                                          //獲得當(dāng)前節(jié)點i的h值if (list[i]) {                                          //如果節(jié)點i在openList中for (int j = 0; j < openList.size(); j++) {if (i == openList[j].name) {                    //首先找到節(jié)點i的位置，即jif (g1 < openList[j].g) {                   //如果新的路徑的花銷更小，則更新openList[j].g = g1;openList[j].f = g1 + openList[j].h;parent[i] = curNode.name;               //記錄父節(jié)點break;}}}}else {                        //如果節(jié)點i不在openList，則將其加入其中（因為擴展時訪問了它）node newNode(i, g1, h1);                    //創(chuàng)建新節(jié)點，其參數(shù)已知openList.push_back(newNode);                //新節(jié)點加入openList中parent[i] = curNode.name;                   //記錄父節(jié)點list[i] = true;                             //記錄節(jié)點i加入了openList}}sort(openList.begin(), openList.end());     //擴展完當(dāng)前節(jié)點后要對openList重新排序/********** End **********/}
}

首先擴展起始節(jié)點，將擴展集合中的節(jié)點按照優(yōu)先級進(jìn)行排序。接著按照優(yōu)先級不斷擴展擴展集合中的節(jié)點，直到找到終點或者沒有可擴展的節(jié)點為止。

每次擴展首先取出擴展集合第一個節(jié)點，判斷其是否為目標(biāo)節(jié)點，若是則退出。擴展該節(jié)點后需要將其加入已訪問集合，并從擴展集合中刪除，同時用list數(shù)組標(biāo)記其已擴展。

接著擴展該節(jié)點，即尋找其鄰居節(jié)點。

如果鄰居節(jié)點在擴展集合中，則查看其更新后代價是否比原本的代價更優(yōu)，優(yōu)則更新它。同時記錄父節(jié)點以用于回溯生成路徑

如果鄰居節(jié)點不在擴展集合中，則將其加入擴展集合中，記錄父節(jié)點，并用list數(shù)組標(biāo)記為在擴展集合中

每次擴展完節(jié)點后都要對擴展集合里的節(jié)點進(jìn)行一次優(yōu)先級的排序，用于下一個循環(huán)來取出當(dāng)前優(yōu)先級最高的節(jié)點

6.void print_result(Graph& graph)函數(shù)

用于打印路徑和開銷

void print_result(Graph& graph)     //用于打印路徑和開銷
{int p = openList[0].name;       //p即為目標(biāo)節(jié)點int lastNodeNum;road.push(p);                   //目標(biāo)節(jié)點壓入棧中，之后最后才輸出while (parent[p] != -1)         //不斷回溯獲得一條完整路徑{road.push(parent[p]);p = parent[p];}lastNodeNum = road.top();       //起始節(jié)點int cost = 0;                   //總開銷cout << "solution: ";while (!road.empty())           //棧不為空就繼續(xù)循環(huán){cout << road.top() << "-> ";if (road.top() != lastNodeNum)  //如果棧頂元素不是終點{cost += graph.getEdge(lastNodeNum, road.top());     //添加花銷lastNodeNum = road.top();       //更新棧頂元素}road.pop();     //彈出棧頂元素}cout << "end" << endl;cout << "cost:" << cost;
}

6.完整代碼

#include<iostream>
#include<vector>
#include<memory.h>
#include<stack>
#include<algorithm>#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define L 9
#define M 10
#define N 11
#define O 12
#define P 13
#define R 14
#define S 15
#define T 16
#define U 17
#define V 18
#define Z 19using namespace std;int h[20] =//從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價
{ 366,0,160,242,161,
178,77,151,226,244,
241,234,380,98,193,
253,329,80,199,374 };/*
*一個節(jié)點結(jié)構(gòu)，node
*/
struct node
{int g;                              //從起始節(jié)點到n節(jié)點的已走過路徑的實際代價int h;                              //從n節(jié)點到目標(biāo)節(jié)點可能的最優(yōu)路徑的估計代價int f;                              //代價估計函數(shù)int name;node(int name, int g, int h) {       //構(gòu)造函數(shù)this->name = name;this->g = g;this->h = h;this->f = g + h;};//重載運算符bool operator <(const node& a)const { return f < a.f; }
};class Graph        //圖結(jié)構(gòu)
{
public:Graph() {memset(graph, -1, sizeof(graph));   //圖初始化為-1，代表無邊}int getEdge(int from, int to) {       //獲取邊的開銷return graph[from][to];}void addEdge(int from, int to, int cost) {    //新增一條邊及其開銷if (from >= 20 || from < 0 || to >= 20 || to < 0)return;graph[from][to] = cost;}void init() {                        //圖初始化addEdge(O, Z, 71);addEdge(Z, O, 71);addEdge(O, S, 151);addEdge(S, O, 151);addEdge(Z, A, 75);addEdge(A, Z, 75);addEdge(A, S, 140);addEdge(S, A, 140);addEdge(A, T, 118);addEdge(T, A, 118);addEdge(T, L, 111);addEdge(L, T, 111);addEdge(L, M, 70);addEdge(M, L, 70);addEdge(M, D, 75);addEdge(D, M, 75);addEdge(D, C, 120);addEdge(C, D, 120);addEdge(C, R, 146);addEdge(R, C, 146);addEdge(S, R, 80);addEdge(R, S, 80);addEdge(S, F, 99);addEdge(F, S, 99);addEdge(F, B, 211);addEdge(B, F, 211);addEdge(P, C, 138);addEdge(C, P, 138);addEdge(R, P, 97);addEdge(P, R, 97);addEdge(P, B, 101);addEdge(B, P, 101);addEdge(B, G, 90);addEdge(G, B, 90);addEdge(B, U, 85);addEdge(U, B, 85);addEdge(U, H, 98);addEdge(H, U, 98);addEdge(H, E, 86);addEdge(E, H, 86);addEdge(U, V, 142);addEdge(V, U, 142);addEdge(I, V, 92);addEdge(V, I, 92);addEdge(I, N, 87);addEdge(N, I, 87);}private:int graph[20][20];              //圖數(shù)組，用來保存圖信息，最多有20個節(jié)點
};bool list[20];                          //用于記錄節(jié)點i是否在openList集合中
vector<node> openList;                  //擴展節(jié)點集合
bool closeList[20];                     //已訪問節(jié)點集合
stack<int> road;                        //路徑
int parent[20];                         //父節(jié)點，用于回溯構(gòu)造路徑void A_star(int goal, node& src, Graph& graph)//A*搜索算法
{openList.push_back(src);                    //擴展集合加入起始節(jié)點sort(openList.begin(), openList.end());     //排序擴展集合的節(jié)點，以取出代價最小的節(jié)點while (!openList.empty()){/********** Begin **********/node curNode = openList[0];             //取出擴展集合第一個節(jié)點，即代價最小的節(jié)點if (curNode.name == goal) {             //如果當(dāng)前節(jié)點就是目標(biāo)節(jié)點，則退出return;}openList.erase(openList.begin());       //將當(dāng)前節(jié)點從擴展列表中刪除closeList[curNode.name] = true;         //將當(dāng)前節(jié)點加入已訪問節(jié)點list[curNode.name] = false;             //標(biāo)記當(dāng)前節(jié)點已不在擴展集合中for (int i = 0; i < 20; i++) {                      //開始擴展當(dāng)前節(jié)點，即找到其鄰居節(jié)點if (graph.getEdge(i, curNode.name) == -1) {     //若不是當(dāng)前節(jié)點的鄰居節(jié)點，跳到下一個節(jié)點continue;}if (closeList[i]) {                             //若此節(jié)點已加入已訪問集合closeList，也跳到下一個節(jié)點continue;}int g1 = curNode.g + graph.getEdge(i, curNode.name);    //計算起始節(jié)點到當(dāng)前節(jié)點i的g值int h1 = h[i];                                          //獲得當(dāng)前節(jié)點i的h值if (list[i]) {                                          //如果節(jié)點i在openList中for (int j = 0; j < openList.size(); j++) {if (i == openList[j].name) {                    //首先找到節(jié)點i的位置，即jif (g1 < openList[j].g) {                   //如果新的路徑的花銷更小，則更新openList[j].g = g1;openList[j].f = g1 + openList[j].h;parent[i] = curNode.name;               //記錄父節(jié)點break;}}}}else {                        //如果節(jié)點i不在openList，則將其加入其中（因為擴展時訪問了它）node newNode(i, g1, h1);                    //創(chuàng)建新節(jié)點，其參數(shù)已知openList.push_back(newNode);                //新節(jié)點加入openList中parent[i] = curNode.name;                   //記錄父節(jié)點list[i] = true;                             //記錄節(jié)點i加入了openList}}sort(openList.begin(), openList.end());     //擴展完當(dāng)前節(jié)點后要對openList重新排序/********** End **********/}
}void print_result(Graph& graph)     //用于打印路徑和開銷
{int p = openList[0].name;       //p即為目標(biāo)節(jié)點int lastNodeNum;road.push(p);                   //目標(biāo)節(jié)點壓入棧中，之后最后才輸出while (parent[p] != -1)         //不斷回溯獲得一條完整路徑{road.push(parent[p]);p = parent[p];}lastNodeNum = road.top();       //起始節(jié)點int cost = 0;                   //總開銷cout << "solution: ";while (!road.empty())           //棧不為空就繼續(xù)循環(huán){cout << road.top() << "-> ";if (road.top() != lastNodeNum)  //如果棧頂元素不是終點{cost += graph.getEdge(lastNodeNum, road.top());     //添加花銷lastNodeNum = road.top();       //更新棧頂元素}road.pop();     //彈出棧頂元素}cout << "end" << endl;cout << "cost:" << cost;
}int main()
{Graph graph;graph.init();int goal = B;                           //目標(biāo)節(jié)點Bnode src(A, 0, h[A]);                   //起始節(jié)點Alist[A] = true;memset(parent, -1, sizeof(parent));     //初始化parentmemset(list, false, sizeof(list));      //初始化listA_star(goal, src, graph);print_result(graph);return 0;
}

運行結(jié)果：