实验一：搜索算法求解问题
一、实验目的
掌握有信息搜索策略的算法思想；
能够编程实现搜索算法；
应用A*搜索算法求解罗马尼亚问题。
二、实验平台
课程实训平台https://www.educoder.net/paths/369
三、实验内容及步骤
实训内容：2-1第三章 通过搜索进行问题求解
1：创建搜索树；
2：实现A搜索算法；
3：使用编写的搜索算法代码求解罗马尼亚问题；
4：分析算法的时间复杂度。
四、思考题
1：宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法哪种方法最优？
2：贪婪最佳优先搜索和A搜索那种方法最优？
3：分析比较无信息搜索策略和有信息搜索策略。
五、实验报告要求
1．说明实验的方法和步骤；
2. 对算法的原理进行说明；
3．给出算法源程序；
4．对实验结果进行分析。

实验一：搜索算法求解问题

实验目的
1、掌握有信息搜索策略的算法思想；
2、能够编程实现搜索算法；
3、应用A*搜索算法求解罗马尼亚问题。

实验内容及步骤
实训内容：通过搜索进行问题求解
1：创建搜索树；
2：实现A搜索算法；
3：使用编写的搜索算法代码求解罗马尼亚问题；
4：分析算法的时间复杂度。
算法原理：
A*搜索算法综合了最佳优先搜索算法（Best-first search）和Dijkstra算法的优点，通过一个成本估算函数来指导路径的搜索过程：F(n) = G(n) + H(n)。
其中函数F(n)是从起始节点通过节点n到达目标节点的最小代价路径的估计值，函数G(n)是从起始节点到n节点所走过路径的实际代价，函数H(n)是从n节点到目标节点可能的最优路径的估计代价 。
在算法的每次迭代中，会从一个优先队列open set中取出n值最小（估算成本最低）的节点作为下次待遍历的节点；然后相应地更新其领域节点的F(n)和G(n)值，并将这些领域节点添加到优先队列中；最后把遍历过的节点放到一个集合close set中。直到目标节点的F(n)值小于队列中的任何节点的F(n)值为止（或者说直到队列为空为止）。
罗马尼亚问题：
agent在罗马尼亚度假，目前位于 Arad 城市。agent明天有航班从Bucharest 起飞，不能改签退票。现在你需要寻找到 Bucharest 的最短路径。

算法源程序

#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 19
using namespace std;

int h[20] =
{ 366,0,160,242,161,
178,77,151,226,244,
241,234,380,98,193,
253,329,80,199,374 };

struct node
{
    int g;
    int h;
    int f;
    int name;
    node(int name, int g, int h)
    {
        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
{
public:
    Graph()
    {
        memset(graph, -1, sizeof(graph));
    }
    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];
};

bool list[20];
vector<node> openList;
bool closeList[20];
stack<int> road;
int parent[20];

void A_star(int goal,node &src,Graph &graph)
{
    openList.push_back(src);
    sort(openList.begin(), openList.end());
    
    while (!openList.empty())
    {
        /********** Begin **********/
        sort(openList.begin(), openList.end());
		int v = openList[0].name;
        int vg = openList[0].g;
        if(v == goal) break;
        openList.erase(openList.begin());
        closeList[v] = 1;
        for(int i = 0;i < 20;i++){
            if(graph.getEdge(v,i)!=-1&&!closeList[i]){
            	 openList.push_back(node(i,vg+graph.getEdge(v,i),h[i]));
				 if(!list[i]) {
				 	parent[i] = v;
				 	list[i] = 1;
				 }              
            }          
        }
		/********** End **********/  
    }
}

void print_result(Graph &graph)
{
    int p = openList[0].name;
    int lastNodeNum;
    road.push(p);
    while (parent[p] != -1)
    {
        road.push(parent[p]);
        p = parent[p];
    }
    lastNodeNum = road.top();
    int cost = 0;
    cout << "solution: ";
    while (!road.empty())
    {
        cout << road.top() << "-> ";
        if (road.top() != lastNodeNum)
        {
            cost += graph.getEdge(lastNodeNum, road.top());
            lastNodeNum = road.top();
        }
        road.pop();
    }
    cout << "end" << endl;
    cout << "cost:" << cost;
}

结果分析
能得到最优解。

思考题
1、宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法哪种方法最优？
一致代价搜索。
2、贪婪最佳优先搜索和A* 搜索哪种方法最优？
A*搜索。
3、分析比较无信息搜索策略和有信息搜索策略。
无信息搜索是指我们不知道接下来要搜索的状态哪一个更加接近目标的搜索策略，因此也常被成为盲目搜索；而有信息搜索则是用启发函数f（n）来衡量哪一个状态更加接近目标状态，并优先对该状态进行搜索，因此与无信息搜索相比往往能够更加高效得解决问题。