人工智能实验一

实验名称

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

实验目的

了解有信息搜索策略的算法思想；
能够运用计算机语言实现搜索算法；
应用A*搜索算法解决罗马尼亚问题；

实验原理

A*搜索

算法介绍

A* 算法常用于二维地图路径规划，算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索，从而减少搜索范围，控制搜索规模，降低实际问题的复杂度。

算法原理：

A* 算法的原理是设计一个代价估计函数：其中 评估函数 F(n) 是从起始节点通过节点 n 的到达目标节点的最小代价路径的估计值，函数 G(n) 是从起始节点到 n 节点的已走过路径的实际代价，函数 H(n) 是从 n 节点到目标节点可能的最优路径的估计代价。

函数 H(n) 表明了算法使用的启发信息，它来源于人们对路径规划问题的认识，依赖某种经验估计。根据 F(n) 可以计算出当前节点的代价，并可以对下一次能够到达的节点进行评估。

采用每次搜索都找到代价值最小的点再继续往外搜索的过程，一步一步找到最优路径。

罗马尼亚问题

罗马尼亚问题：agent 在罗马尼亚度假，目前位于 Arad 城市。agent明天有航班从 Bucharest 起飞，不能改签退票。

现在你需要寻找到 Bucharest 的最短路径，补充void A_star(int goal,node &src,Graph &graph)函数，使用编写的搜索算法代码求解罗马尼亚问题：

实验步骤

阅读平台上除需补充部分的其他部分代码，理清代码思路，为接下来的代码编写打下基础
理清代码思路后，按照 A* 搜索算法的思想一步步填写需补充的部分
填写完成后，点击实训平台上的“评测”按钮对填写的代码进行评测

实验结果与分析

首先对实训平台上的代码进行分析

#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

这是将罗马尼亚地图上每个城市用首字母进行替代，然后将其按照字符顺序宏定义成对应的数字，主要目的只是为了后面代码的编写更加方便

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;
    }
};

h 数组储存了每个城市到目标城市的直线距离，定义了一个 node 的结构体结点，中间包含了城市编号，对应的 g ，f ，h 值，并且对 < 进行了重构，主要是为了在后续排序选出边缘点集中 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];
};

这一段是定义了一个图类，并且进行了初始化，构成了罗马尼亚地图，并且提供了函数 getEdge 用来得到两个城市之间的距离，若城市之间无边则为 0

bool list[20];//记录城市 i 是否在边缘点集中
vector<node> openList;//存放边缘结点
bool closeList[20];//记录城市 i 是否在探索集中
stack<int> road;
int parent[20];//记录城市 i 的父结点

定义一个 bool 型的 list 数组用来记录城市 i 是否在边缘点集中；openList 是边缘点集，用来存放边缘结点；bool 型的 closeList 数组用来记录城市 i 是否在探搜集中，栈 road 用来记录路径，数组 parent 用来记录到城市 i 的上一个城市

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;
}

print_result 函数用来打印出结果，经过 A* 搜索后，边缘结点集 openList 中的 openList[0] 即为找到的目标结点，将对应的城市编号压入 road 栈中，循环查找父结点，并将城市编号压入 road 栈，将栈中元素弹出得到的就是路径，但是由于还要输出路径消耗，所以用变量 LastNodeNum 来表示上一城市编号，用 getEdge 函数来求得其和栈顶部城市编号的路径消耗，进行累加

编写的 A* 搜索代码如下：

void A_star(int goal,node &src,Graph &graph)
{
    openList.push_back(src);
    sort(openList.begin(), openList.end());//按 f 值从小到大排序
    
    while (!openList.empty())
    {
        /********** Begin **********/
        node current = openList[0];
        if(current.name == goal) return;
        openList.erase(openList.begin());
        list[current.name] = false;
        closeList[current.name] = true;

        for(int to=0;to<20;to++) {//遍历每个结点
            //判断结点是否和扩展结点有边，并且未被探索
            if(graph.getEdge(current.name,to)!=-1&&closeList[to]==false) {
                //如果在边缘点集
                if(list[to] == true) {
                    int j=0;//找到边缘点集对应的点
                    for(;j<openList.size();j++) {
                        if(openList[j].name == to) break;
                    }
                    int cost = current.g + graph.getEdge(current.name,to);
                    //从扩展结点到这个点的 g 值要小，则更新边缘点集中这个点的 g , f 值，并且记录父结点
                    if(cost < openList[j].g) {
                        openList[j].g = cost;
                        openList[j].f = cost + openList[j].h;
                        parent[to] = current.name;
                    }
                }
                //如果不在边缘点集
                else {
                    //直接创建一个结点将其加入边缘点集，并记录父结点
                    node newn(to,current.g+graph.getEdge(current.name,to),h[to]);
                    openList.push_back(newn);
                    parent[to] = current.name;
                    //按 f 值从小到大排序
                    sort(openList.begin(),openList.end());
                    //
                    list[to] = true;
                }
            }
        }
		/********** End **********/  
    }
}

其实这就是优先队列求解的思路，首先将边缘点集按照 f 值从小到大排序，选择其中 f 值最小的进行扩展，对这二十个城市进行遍历，判断和扩展结点的城市编号之间是否有边，是否在探索集中，如果之间有边，并且未探索，就要将其生成该城市编号对应的结点，并且将其加入到 openList ，但其实这不是完全正确的，我们还得考虑这样一种情况，该城市编号对应的结点已经在边缘点集中了。这时我们就要判断是否要进行更新结点，如果从该扩展结点到这个结点路径消耗更小，那么就要更新结点，也就是更新结点的 g ，f 值。当然了，还得做一些必要的操作，比如扩展结点，要将其从 openList 中移去，并且将其对应城市加入探索集，还有就是要记录父结点。当 openList 为空，或者扩展结点对应的城市编号是目标城市时，就退出 A* 搜索程序

思考题

1：宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法哪种方法最优？

我认为，没有哪种方法可以说是最优的，在不同的场合有不同的最优方法，那么在这次实验中，这几个无信息策略搜索哪个最优呢？

宽度优先搜索：

宽度优先搜索是简单搜索策略，先扩展根结点，接着扩展根结点的所有后继，然后再扩展它们的后继，依此类推。一般地，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。

宽度优先搜索是一般图搜索算法的一个实例，每次总是扩展深度最浅的结点。这可以通过将边缘组织成 FIFO 队列来实现。就是说，新结点（结点比其父结点深）加入到队列尾，这意味着浅层的老结点会在深层结点之前被扩展。

宽度优先搜索算法具有一般的图搜索框架，忽视所有到边缘结点或已经扩展结点的新路径，可以看出这样的路径至少和已经找到的一样深，所以，宽度优先搜索总是有到每一个边缘结点的最浅路径。

如果最浅的目标结点处于一个有限深度 d，那么宽度优先搜索是完备的，宽度优先搜索在扩展完比它浅的所有结点之后最终一定能找到该目标结点。但是，最浅的目标结点不一定是最优的目标结点。

时间复杂度：$O(b^d)$

空间复杂度：$O(b^d)$

一致代价搜索：

当每一步的行动代价都相等时宽度优先搜索是最优的，因为它总是先扩展深度最浅的未扩展结点。更进一步，我们可以找到一个对任何单步代价函数都是最优的算法。不再扩展深度最浅的结点，一致代价搜索扩展的是路径消耗最小的结点。这可以通过将边缘结点集组织成按单步代价值排序的优先队列来实现。

除了按路径代价对队列进行排序外，一致代价搜索和宽度优先搜索有两个显著不同。第一是目标检测应用于结点被选择扩展时，而不是在结点生成的时候进行。理由是第一个生成的目标结点可能在次优的路径上。第二个不同是如果边缘中的结点有更好的路径到达该结点那么会引入一个测试。

引入 $C^*$ 表示最优解的代价，假设每个行动的代价至少为 $ε$

时间复杂度：$O(b^{1+\frac{C^*}{ε}})$

空间复杂度：$O(b^{1+\frac{C^*}{ε}})$

深度优先搜索：

深度优先搜索总是扩展搜索树的当前边缘结点集中最深的结点。搜索很快推进到搜索树的最深层，那里的结点没有后继。当那些结点扩展完之后，就从边缘结点集中去掉，然后搜索算法回溯到下一个还有未扩展后继的深度稍浅的结点。

宽度优先搜索使用 FIFO 队列，深度优先搜索使用 LIFO 队列。LIFO 队列指的是最新生成的结点最早被选择扩展。这一定是最深的未被扩展的结点，因为它比它的父结点深 1 ，上一次扩展的则是这个父结点因为它最深。

深度优先搜索算法的效率严重依赖于使用的是图搜索还是树搜索。避免重复状态和冗余路径的图搜索，在有限状态空间是完备的，因为它至多扩展所有结点。而树搜索，则不完备，算法会陷入死循环。同样的原因，无论是基于图搜索还是树搜索的深度优先搜索都不是最优的。深度优先搜索的时间复杂度受限于状态空间的规模。

时间复杂度：$O(b^m)$

空间复杂度：$O(bm)$

迭代加深的深度优先搜索：

迭代加深的深度优先搜索是一种常用策略，它经常和深度优先搜索结合使用来确定最好的深度界限。做法是不断地增大深度限制——首先为 0，接着为 1，然后是 2，以此类推直到找到目标。当深度界限达到 d，即最浅的目标结点所在深度时，就能找到目标结点。

迭代加深的深度优先搜索算法结合了深度优先搜索和宽度优先搜索的优点，它的空间需求是合适的：$O(bd)$。和宽度优先搜索一样，当分支因子有限时是该搜索算法是完备的，当路径代价是结点深度的非递减函数时该算法是最优的。

也许迭代加深的深度优先搜索看起来比较浪费，因为状态被多次重复生成。但事实上代价并不是多大。原因是在分支因子相同（或者近似）的搜索树中，绝大多数的结点都在底层，所以上层的结点重复生成多次影响不大。

时间复杂度：$O(b^d)$

如果你确实担忧状态的重复生成，可以混合使用两种搜索算法，先用宽度优先搜索直到有效内存耗尽，然后对边缘集中的所有结点应用迭代加深的深度优先搜索。一般来讲，当搜索空间较大并且不知道解所在的深度时，迭代加深的深度优先搜索是首选的无信息搜索算法。

看完以上几种算法的介绍就知道了，没有一种算法在罗马尼亚问题下是最优的，也就是说这几种无信息搜索算法都很难直接找到最优解，所以很难说这几种算法谁最优，如果硬是要选择一个那就是迭代加深的深度优先搜索算法，因为迭代加深的深度优先搜索算法结合了深度优先搜索和宽度优先搜索的优点，当搜索空间较大并且不知道解所在的深度时，迭代加深的深度优先搜索是首选的无信息搜索算法。

2：贪婪最佳优先搜索和 A* 搜索哪种方法最优？

贪婪最佳优先搜索：

有信息搜索策略使用问题本身的定义之外的特定知识，比无信息的搜索策略更有效的进行问题求解。一般考虑的算法称为最佳优先搜索。最佳优先搜索中，结点是基于评价函数值被选择扩展的。评价函数被看作是代价评估，因此评估值最低的结点被选择首先进行扩展。最佳优先图搜索的实现与一致代价搜索类似，不过最佳优先是根据评价函数值对优先级队列进行排队。

大多数的最佳优先搜索算法的评价函数是由启发函数构成：启发函数 = 结点到目标结点的最小代价路径的代价评估值

贪婪最佳优先搜索试图扩展离目标最近的结点，理由是这样可能可以很快找到解。因此，它只用启发式信息。对应到罗马尼亚问题中，使用直线距离启发式

时间复杂度：$O(b^m)$

空间复杂度：$O(b^m)$

A* 搜索：

最佳优先搜索的最广为人知的形式称为 A* 搜索。它对结点的评估结合了到达此结点已经花费的代价，和从该结点到目标结点所花代价。由于结合了从开始结点到结点 n 的路径代价和从结点 n 到目标结点的最小代价路径的评估值，因此评估函数值等于经过结点 n 的最小代价解的估计代价。

这样，如果我们想要找到最小代价的解，首先扩展评估函数值最小的结点是合理的。可以发现这个策略不仅仅合理：假设启发式函数满足特定的条件，A* 搜索既是完备的也是最优的。

其中，A* 搜索算法的最优性取决于：如果启发式函数是可采纳的，那么 A* 的树搜索版本是最优的，如果启发式函数是一致的，那么图搜索的 A* 算法是最优的。

很明显，在罗马尼亚问题中，h 用的是城市到目标城市的直线距离，所以，很容易证明启发式函数是一致的，所以在这个问题中 A* 搜索算法是最优的，可以找到最优解，但是贪婪优先搜索就不一定了，所以 A* 搜索算法最优

3：分析比较无信息搜索策略和有信息搜索策略。

无信息搜索的结束条件是遍历整个状态空间直到找到一个解。其特点如下：

除了问题定义中提供的状态信息外没有任何附加信息
算法只能区分状态是不是目标状态
无法比较非目标状态的好坏

有信息搜索算法（其中一般的算法称为最佳优先搜索）算法性能取决于启发式函数的质量（选择的算法未改变的情况下）。

有信息搜索算法在能找到最优解的情况下无论时间还是空间复杂度都优于无信息搜索，但有时由于启发式函数的不正确会导致无法得到最优解而是局部最优，或者根本无法得到一个解。所以大多情况下会对有信息搜索进行改进使其得到最优解。

实验总结

通过这次实验，我了解有信息搜索策略的算法思想，提升了运用计算机语言实现搜索算法的能力，并且知道了应用 A* 搜索算法解决罗马尼亚问题。其实这次实验并不难，最关键的点就是要先把代码看懂，然后再进行补充，看懂代码可以说这个实验就已经完成了一半了，根据我们课上对 A* 搜索算法思想的了解，想要看懂其实也并不困难。但是在 A* 搜索算法的实现过程中还有一个容易被忽视的小问题，没有考虑到这个小问题，就会导致算法的不正确，我自己也是一直踩雷后来才发现我忽视了这个小问题，也就是这个问题让我评测刚开始一直通不过。这个问题就是扩展结点的后继结点得判断它是否已经在边缘点集中，如果在的话再进行判断看是否需要更新结点。我刚开始就是没有进行判断，直接将其加入边缘点集中了，这样就会导致，如果这个结点本来就在边缘点集中，再添加就会有多个这个城市对应的结点。还有很重要的一点是，在操作完后，要即使更新 list，closeList 的状态，还有扩展结点后要记得将结点从边缘点集中删除，这些虽然都是小问题，但是在实现算法的过程中看的往往就是这些小问题对不对，因为一个算法已经告诉你大概的实现方法了，你要做的不就是怎么去处理好这些小问题吗，所以说细心真的很重要。希望自己以后也能细心一点，少出现这样的小问题，也不用花太多时间放在修 BUG 上了这次实验让我们将 A* 搜索算法写成 c++ 代码实现，作为一个计算机人，写代码的能力是很重要的，只会算法的大概却不知道怎么写成代码，这是很尴尬的，而实验就刚好训练了我们这一能力，所以要认真对待每一次实验，这样我们的能力才能得到提升

实验代码

user.h

#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];//记录结点 i 是否在边缘点集中
vector<node> openList;//存放边缘结点
bool closeList[20];//记录结点 i 是否在探索集中
stack<int> road;
int parent[20];//记录结点 i 的父结点

void A_star(int goal,node &src,Graph &graph)
{
    openList.push_back(src);
    sort(openList.begin(), openList.end());//按 f 值从小到大排序
    
    while (!openList.empty())
    {
        /********** Begin **********/
		node current = openList[0];
        if(current.name == goal) return;
        openList.erase(openList.begin());
        list[current.name] = false;
        closeList[current.name] = true;

        for(int to=0;to<20;to++) {//遍历每个结点
            //判断结点是否和扩展结点有边，并且未被探索
            if(graph.getEdge(current.name,to)!=-1&&closeList[to]==false) {
                //如果在边缘点集
                if(list[to] == true) {
                    int j=0;//找到边缘点集对应的点
                    for(;j<openList.size();j++) {
                        if(openList[j].name == to) break;
                    }
                    int cost = current.g + graph.getEdge(current.name,to);
                    //从扩展结点到这个点的 g 值要小，则更新边缘点集中这个点的 g , f 值，并且记录父结点
                    if(cost < openList[j].g) {
                        openList[j].g = cost;
                        openList[j].f = cost + openList[j].h;
                        parent[to] = current.name;
                    }
                }
                //如果不在边缘点集
                else {
                    //直接创建一个结点将其加入边缘点集，并记录父结点
                    node newn(to,current.g+graph.getEdge(current.name,to),h[to]);
                    openList.push_back(newn);
                    parent[to] = current.name;
                    //按 f 值从小到大排序
                    sort(openList.begin(),openList.end());
                    //
                    list[to] = true;
                }
            }
        }
		/********** 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;
}

run.cpp

#include "user.h"


int main()
{
    Graph graph;
    graph.init();
    int goal = B;
    node src(A, 0, h[A]);
    list[A] = true;
    memset(parent, -1, sizeof(parent));
    memset(list, false, sizeof(list));
    A_star(goal, src, graph);
    print_result(graph);
    return 0;
}

A* 搜索算法求解罗马尼亚问题