# 人工智能实验一：搜索算法问题求解
## 一、实验目的
• 了解4种无信息搜索策略和2种有信息搜索策略的算法思想；
• 能够运用计算机语言实现搜索算法；
• 应用搜索算法解决实际问题(如罗马尼亚问题)；
• 学会对算法性能的分析和比较
## 二、实验的硬件、软件平台
硬件：计算机
软件：操作系统：WINDOWS／Linux
应用软件：C, Java或者MATLAB
## 三、实验内容及步骤
使用搜索算法实现罗马尼亚问题的求解
1．创建搜索树；
2．实现搜索树的宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法；
3．实现贪婪最佳优先搜索和A*搜索
4．使用编写的搜索算法代码求解罗马尼亚问题；
5．记录各种算法的时间复杂度并绘制直方图
# 实验步骤：
## 一、数据的预处理以及初始化
将各个顶点取首字母进行标号：
```
#define A 0
#define B 1
#define C 2
#define D 3
……
```
初始化之后需要用到的启发式函数值：
```
int h[20] = {366, 0, 160, 242, 161, 178, 77, 151, 226, 244,
241, 234, 380, 98, 193, 253, 329, 80, 199, 374};
```
为了便于输出格式的控制，将每个城市标号值对应的名称存放在label数组内：
```
string label[20] = {
"Arad", "Bucharest", "Craiova", "Dobreta", "Eforie",
"Fagaras", "Giurgiu", "Hirsova", "Iasi", "Lugoj",
"Mehadia", "Neamt", "Oradea", "Pitesti", "Rimnicu Vilcea",
"Sibiu", "Timisoara", "Urziceni", "Vaslui", "Zerind"
};
```
#### 二、无向图的建立以及搜索树的建立
构建Graph类来存放图和搜索树
```
class Graph {
public:
Graph() {
memset(graph, -1, sizeof(graph));
}
int getEdge(int from, int to) { // 计算搜索算法消耗时使用的邻接矩阵
return graph[from][to];
}
vector<PII> getAction(int from) { // 获得当前行动的子结点集
return edge[from];
}
void addEdge(int from, int to, int cost) { // 图中添加边
if (from >= 20 || from < 0 || to >= 20 || to < 0)
return;
graph[from][to] = cost;
edge[from].push_back({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);
……
}
private:
int graph[20][20]; // 邻接矩阵
vector<PII> edge[20]; // 搜索树
};
```
通过邻接矩阵graph存图，graph[i][j]即顶点i到顶点j的边，为-1则表示两点间没有边的存在。使用edge存放搜索树，edge[i]存放结点i的子结点即，结点的值为标号和路径消耗。
## 三、无信息搜索策略
#### 1.宽度优先搜索BFS
1)算法描述：
先扩展根节点，接着扩展根节点的所有后继，然后再扩展他们的后继，以此类推。在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。
2)算法步骤：
使用FIFO队列维护待扩展的结点集，设置父结点集fa，用于最终输出路径。
a) 源节点入队，标记为已访问；
b) 若队列非空，则继续进行，否则结束；
c) 取队首元素并从队列中弹出，判断是否到达目标结点，若是目标结点则结束算法；
d) 生成当前结点的子结点，若子结点未被访问过，则将其加入队列，并设置为已访问，同时将子结点的父结点前驱指向当前结点，重复b)。
3)代码实现：
```
class BFS {
private:
int vis[20]; // 标记结点是否被访问过
int cost; // 搜索消耗
int fa[20]; // 第i个结点的父节点（用于之后路径输出）
int flag;
queue<int> q; // 维护队列保存已扩展结点
public:
BFS() {
cost = 0;
flag = 1;
memset(vis, 0, sizeof(vis));
memset(fa, -1, sizeof(fa));
while (!q.empty())
q.pop();
}
void bfs(int goal, int src, Graph &graph) {
vis[src] = 1; // 源节点设置为已访问
q.push(src); // 源节点入队
while (!q.empty()) { // 从队列中取元素直到队列为空或搜索到目标节点
int now = q.front(); // 取队首元素
q.pop();
if (now == goal) { // 找到目标节点，结束
flag = 0;
break;
}
vector<PII> nxt = graph.getAction(now); // 获取子结点
for (auto w : nxt) {
int weight = w.second;
int i = w.first;
if (vis[i] == 0) { // 未放问过
q.push(i); // 入队
vis[i] = 1; // 设置为已访问
fa[i] = now;
}
}
}
}
void print_result(int goal, Graph &graph) { // 路径输出及消耗计算函数，当然这不重要
cout << "BFS: " << endl;
if (flag) { // 未能找到目标结点
cout << "Failed" << endl;
return;
}
cout << "Path: ";
stack<int> s; // 维护访问过的结点集合，从后向前
s.push(goal);
int father = fa[goal]; // 寻找父结点
cost += graph.getEdge(father, goal); // 计算路径消耗
while (father != -1) { // 直到找到根节点结束
s.push(father);
cost += graph.getEdge(father, fa[father]);
father = fa[father];
}
while (!s.empty()) { // 路径输出
cout << label[s.top()] << "->";
s.pop();
}
cout << "end" << endl;
cout << "Cost: " << cost << endl;
}
};
```
4)算法分析：
a) 完备性：BFS是完备的，如果最浅的目标节点处于有限深度d，那么在扩展比他浅的结点之后一定能够找到该目标节点。
b) 最优性：不是最优的，因为最浅的目标节点不一定是最优的目标节点，在路径代价是基于结点深度的非递减函数时，BFS是最优的
c) 复杂度分析：假设每一个状态都有b个后继，解得深度为d，那么在最坏情况下，解是该层的最后一个结点，时间复杂度为O(b^d)；边缘结点集中会存放b^d个状态，所以空间复杂度取决于边缘结点集，为O(b^d)。
#### 2.深度优先搜索DFS
1)算法描述：
扩展搜索树的当前边缘结点集中最深的结点，当结点扩展完之后，将其从边缘结点集中去掉，之后搜索算法回溯到下一个还未扩展后继的深度稍浅的结点。
2)算法步骤：
使用栈（LIFO队列）来维护边缘结点集。
a) 源节点生成后继结点，并压入栈中；
b) 栈为非空，则从栈顶弹出结点作为当前结点，设置为已访问；
c) 若当前结点为目标结点，算法结束，否则生成其后继节点，若后继节点未被访问，压入栈中；
d) 重复b）直到搜索到解或栈为空。
3)代码实现：
```
class DFS {
private:
int vis[20]; // 标记结点是否被访问
int cost; // 搜索消耗
vector<int> road; // 搜索过程的路径
public:
DFS() {
memset(vis, 0, sizeof(vis));
cost = 0;
road.clear();
}
bool dfs_version2(
int goal, int src, Graph &graph) { // 当前结点首先扩展其所有子结点，但只访问目前最深的子结点
if (src == goal) { // 搜索到目标结点
road.push_back(goal);
return 1;
}
bool flag = 0; // 判断是否搜索到解
vis[src] = 1; // 当前结点设置为已访问
road.push_back(src);
stack<int> s; // 用于保存当前结点的所有子结点
vector<PII> nxt = graph.getAction(src); // 获取子结点集
for (auto w : nxt) {
int i = w.first;
if (vis[i]
