一、实验目的
本实验课程是计算机、智能、物联网等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验报告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。
- 掌握人工智能中涉及的相关概念、算法。
- 熟悉人工智能中的知识表示方法；
- 熟悉盲目搜索和启发式搜索算法的应用；
- 掌握问题表示、求解及编程实现。
- 掌握不同搜索策略的设计思想、步骤、性能。
二、基本要求
1、实验前，复习《人工智能》课程中的有关内容。
2、准备好实验数据。
3、编程要独立完成，程序应加适当的注释。
4、完成实验报告。
三、实验软件
使用C或C++（Visual studio）（不限制语言使用）。
四、实验内容：
(1)
1、在图1，3*3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空。
2、如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态（图1左）到目标状态（图1右）。
3、可自行设计初始状态。目标状态为数字从小到大按顺时针排列。
4、分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（A*算法）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究各个搜索算法的特点。
（2）罗马尼亚问题
根据上图以Zerind为初始状态，Bucharest为目标状态实现搜索，分别以贪婪搜索（只考虑直线距离）和A*算法求解最短路径。 按顺序列出贪婪算法探索的扩展节点和其估价函数值，A*算法探索的扩展节点和其估计值。
选做部分：自行设计一个新的启发式函数,并分析该函数的可采纳性和优势(与启发式函数定义为“Zerind到Bucharest的直线距离”相比较)。
五、学生实验报告要求
1、实验报告需要包含以下几个部分
（1）状态表示的数据结构
实验一：
struct State {
int puzzle[3][3];
int cost; // 从起始状态到当前状态的代价
int heuristic; // 启发式估计的代价
};结构体包含一个3x3的整数数组 puzzle 表示八数码的状态，以及两个整数 cost 和 heuristic 分别表示从起始状态到当前状态的代价和启发式估计的代价。
实验二：
状态使用图（city_graph）和字典（to_B_distance）表示。图（city_graph）是一个列表的列表，其中每个内部列表表示两个城市之间的边以及相应的距离。字典（to_B_distance）存储每个城市到目标城市 'B' 的直线距离。起始城市和结束城市分别定义为 'start_city' 和 'end_city'。
（2）状态扩展规则的表示
状态扩展规则在 greedy 和 A_plus 函数中表示。这些函数基于特定的准则探索相邻城市。对于贪婪算法，它选择距离目标最近的城市。在A*算法中，考虑总成本函数 f(x) = g(x) + h(x)，其中 g(x) 是从开始到当前节点的成本，h(x) 是启发式（到目标的直线距离）
（3）搜索产生的状态空间图
八数码：
罗马尼亚问题：
（4）OPEN表和CLOSE表变化过程
| Expnd.node | Open list |
| {Z} | |
| Z | {O,A} |
| A | {S,T} |
| S | {R,F} |
| R | {P,C} |
| P | {C,B} |
| B(goal) | {G,U} |
（5）程序清单
实验（1）
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// 表示八数码状态的结构体
struct State {
int puzzle[3][3];
int cost; // 从起始状态到当前状态的代价
int heuristic; // 启发式估计的代价
};
// 定义操作：空格左移、右移、上移、下移
State moveLeft(const State& s) {
State newState = s;
int emptyRow, emptyCol;
// 找到空格的位置
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (s.puzzle[i][j] == 0) {
emptyRow = i;
emptyCol = j;
break;
}
}
}
// 左移操作，交换空格和左侧数字的位置
if (emptyCol > 0) {
swap(newState.puzzle[emptyRow][emptyCol], newState.puzzle[emptyRow][emptyCol - 1]);
}
return newState;
}
State moveRight(const State& s) {
State newState = s;
int emptyRow, emptyCol;
// 找到空格的位置
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (s.puzzle[i][j] == 0) {
emptyRow = i;
emptyCol = j;
break;
}
}
}
// 右移操作，交换空格和右侧数字的位置
if (emptyCol < 2) {
swap(newState.puzzle[emptyRow][emptyCol], newState.puzzle[emptyRow][emptyCol + 1]);
}
return newState;
}
State moveUp(const State& s) {
State newState = s;
int emptyRow, emptyCol;
// 找到空格的位置
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (s.puzzle[i][j] == 0) {
emptyRow = i;
emptyCol = j;
break;
}
}
}
// 上移操作，交换空格和上方数字的位置
if (emptyRow > 0) {
swap(newState.puzzle[emptyRow][emptyCol], newState.puzzle[emptyRow - 1][emptyCol]);
}
return newState;
}
State moveDown(const State& s) {
State newState = s;
int emptyRow, emptyCol;
// 找到空格的位置
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (s.puzzle[i][j] == 0) {
emptyRow = i;
emptyCol = j;
break;
}
}
}
// 下移操作，交换空格和下方数字的位置
if (emptyRow < 2) {
swap(newState.puzzle[emptyRow][emptyCol], newState.puzzle[emptyRow + 1][emptyCol]);
}
return newState;
}
// 检查两个状态是否相等
bool isEqual(const State& s1, const State& s2) {
return memcmp(s1.puzzle, s2.puzzle, sizeof(s1.puzzle)) == 0;
}
// 输出状态
void printState(const State& s) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << s.puzzle[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
// 广度优先搜索算法
bool bfs(const State& start, const State& goal) {
queue<State> pq;
pq.push(start);
while (!pq.empty()) {
State current = pq.front();
pq.pop();
if (isEqual(current, goal)) {
// 找到目标状态
cout << "Found solution!" << endl;
return true;
}
// 执行四个操作，将新状态加入优先队列
State next;
next = moveLeft(current);
if (!isEqual(next, current)) {
pq.push(next);
cout << "Move Left:" << endl;
printState(next);
}
next = moveRight(current);
if (!isEqual(next, current)) {
pq.push(next);
cout << "Move Right:" << endl;
printState(next);
}
next = moveUp(current);
if (!isEqual(next, current)) {
pq.push(next);
cout << "Move Up:" << endl;
printState(next);
}
next = moveDown(current);
if (!isEqual(next, current)) {
pq.push(next);
cout << "Move Up:" << endl;
printState(next);
}
}
// 未找到解决方案
cout << "No solution found." << endl;
return false;
}
int main() {
// 设计初始状态和目标状态
State start = { 2, 1, 3, 8, 0, 4, 7, 6, 5 };
State goal = { 1, 2, 3, 8, 0, 4, 7, 6, 5 };
cout << "Initial State:" << endl;
printState(start);
cout << "Goal State:" << endl;
printState(goal);
// 调用广度优先搜索算法
bfs(start, goal);
return 0;
}深度优先搜索算法部分代码(其他代码不变)
// 深度优先搜索算法
bool dfs(const State& start, const State& goal) {
stack<State> s;
s.push(start);
while (!s.empty()) {
State current = s.top();
s.pop();
if (isEqual(current, goal)) {
// 找到目标状态
cout << "Found solution!" << endl;
return true;
}
// 执行四个操作，将新状态加入栈
State next;
next = moveLeft(current);
// 检查是否为合法状态，避免重复搜索
if (!isEqual(next, current)) {
s.push(next);
}
next = moveRight(current);
if (!isEqual(next, current)) {
s.push(next);
}
next = moveUp(current);
if (!isEqual(next, current)) {
s.push(next);
}
next = moveDown(current);
if (!isEqual(next, current)) {
s.push(next);
}
}
}
A*算法
...
// 曼哈顿距离估价函数
int manhattanDistance(const State& s, const State& goal) {
int distance = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
int value = s.puzzle[i][j];
if (value != 0) {
int goalRow, goalCol;
goalRow = (value - 1) / 3;
goalCol = (value - 1) % 3;
distance += abs(i - goalRow) + abs(j - goalCol);
}
}
}
return distance;
}
// 输出状态
void printState(const State& s) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << s.puzzle[i][j] << " ";
}
cout << " ";
}
cout << "Cost: " << s.cost << " Heuristic: " << s.heuristic << endl << endl;
}
// 用于优先队列的比较函数，用于A*算法中选择最小代价的节点
struct CompareStates {
bool operator()(const State& s1, const State& s2) {
return (s1.cost + s1.heuristic) > (s2.cost + s2.heuristic);
}
};
// A*搜索算法
bool aStar(const State& start, const State& goal) {
priority_queue<State, vector<State>, CompareStates> pq;
pq.push(start);
while (!pq.empty()) {
State current = pq.top();
pq.pop();
if (isEqual(current, goal)) {
// 找到目标状态
cout << "Found solution!" << endl;
return true;
}
// 执行四个操作，将新状态加入优先队列
State next;
next = moveLeft(current);
if (!isEqual(next, current)) {
next.cost = current.cost + 1;
next.heuristic = manhattanDistance(next, goal);
pq.push(next);
}
next = moveRight(current);
if (!isEqual(next, current)) {
next.cost = current.cost + 1;
next.heuristic = manhattanDistance(next, goal);
pq.push(next);
}
next = moveUp(current);
if (!isEqual(next, current)) {
next.cost = current.cost + 1;
next.heuristic = manhattanDistance(next, goal);
pq.push(next);
}
next = moveDown(current);
if (!isEqual(next, current)) {
next.cost = current.cost + 1;
next.heuristic = manhattanDistance(next, goal);
pq.push(next);
}
}
// 未找到解决方案
cout << "No solution found." << endl;
return false;
}
...实验（二）
# 罗马利亚图存储
city_graph = [['A', 'Z', 75],
['A', 'T', 118],
['Z', 'O', 71],
['O', 'S', 151],
['A', 'S', 140],
['S', 'F', 99],
['S', 'R', 80],
['R', 'P', 97],
['R', 'C', 146],
['T', 'L', 111],
['L', 'M', 70],
['M', 'D', 75],
['D', 'C', 120],
['C', 'P', 138],
['P', 'B', 101],
['F', 'B', 211],
['B', 'G', 90],
['B', 'U', 85],
['U', 'V', 142],
['V', 'I', 92],
['I', 'N', 87],
['U', 'H', 98],
['H', 'E', 86]]
# B到其他城市的直线距离
to_B_distance = {'A': 366,
'B': 0,
'C': 160,
'D': 242,
'E': 161,
'F': 176,
'G': 77,
'H': 151,
'I': 226,
'L': 244,
'M': 241,
'N': 234,
'O': 380,
'P': 100,
'R': 163,
'S': 253,
'T': 329,
'U': 80,
'V': 199,
'Z': 374}
start_city = 'Z'
end_city = 'B'
# 判断某条路是否走过
def is_visited(A_city, B_city, went_road):
for i in range(len(went_road)):
if went_road[i][0] == A_city and went_road[i][1] == B_city:
return 1
if went_road[i][0] == B_city and went_road[i][1] == A_city:
return 1
return 0
# 根据访问结点打印结果
def print_ans(ans, distance):
print("路径为：", end="")
for i in range(len(ans)):
if i != len(ans) - 1:
print(ans[i], "->", end="")
else:
print(ans[i])
print("路径长度之和为：",distance)
# 贪婪算法，每次寻找离目标城市直线距离最短的城市走
def greedy(start, end):
print("贪婪算法：")
went_road = []
ans_road = [start]
while 1:
# 查找开始结点的所有临近城市及边
start_near_city = []
for item in city_graph:
if item[0] == start:
start_near_city.append([item[1], item[2]])
if item[1] == start:
start_near_city.append([item[0], item[2]])
# 挑选到目标结点直接距离最短的城市
direct_distance = 999
for item in start_near_city:
if to_B_distance[item[0]] < direct_distance and is_visited(start, item[0], went_road) == 0:
direct_distance = to_B_distance[item[0]]
min_distance = item[1]
min_city = item[0]
# 如果找到一条直线距离最短的路且没有访问过，则选择走这条路并记录走过的这条路
if direct_distance != 999:
went_road.append([start, min_city, min_distance])
print(min_city, direct_distance)
start = min_city
ans_road.append(start)
else:
print("终点不可达！")
return 0
# 找到终点返回路径及总长度
if start == end:
ans_distance = 0
for i in range(len(went_road)):
ans_distance += went_road[i][2]
print_ans(ans_road, ans_distance)
return 1
# A*算法，每次寻找f=g+h最小的值走
def A_plus(start, end):
print("A*算法：")
went_road = []
ans_road = [start]
while 1:
# 扫描图，获取与start相连的所有边
go_to_city = []
for item in city_graph:
if item[0] == start:
go_to_city.append([item[1], item[2]])
if item[1] == start:
go_to_city.append([item[0], item[2]])
# 寻找fx最小的可达城市和距离，不能走回访问过的路
hx = 0
for j in went_road:
hx += j[2]
fx_distance = 999
for item in go_to_city:
if hx+item[1]+to_B_distance[item[0]] < fx_distance and is_visited(start, item[0], went_road) == 0:
fx_distance = hx+item[1]+to_B_distance[item[0]]
min_distance = item[1]
min_city = item[0]
# 如果找到可达的最小城市，则将其访问过的路径加入went_road
if fx_distance != 999:
went_road.append([start, min_city, min_distance])
print(min_city, fx_distance)
start = min_city
ans_road.append(start)
else:
print("终点不可达！")
return 0
# 找到终点返回路径及总长度
if start == end:
ans_distance = 0
for i in range(len(went_road)):
ans_distance += went_road[i][2]
print_ans(ans_road, ans_distance)
return 1
greedy(start_city, end_city)
A_plus(start_city, end_city)（6）实验结果讨论
实验（1）
manhattanDistance函数计算了曼哈顿距离，并且在每个状态扩展时计算了启发式估价函数。
估价函数的选择会影响算法的性能。
各搜索算法特点：
BFS：保证找到最短路径，但可能需要较多内存。
DFS：内存需求较低，但可能找到的路径不是最短的。
A*算法：结合了BFS和DFS的优点，通过选择合适的估价函数，可以找到最短路径，并在性能上进行优化。
实验（二）
思考并解答以下问题
1、你所采用的估价函数f(n) = g(n) + h(n)中，g(n)和h(n)的主要作用是什么？
g(n)表示从起始节点到当前节点n的实际代价，h(n)表示从节点n到目标节点的启发式估计代价。g(n)的主要作用是衡量已经花费的代价，h(n)则是启发式地估计剩余的代价。通过这两者的和f(n)，我们可以评估当前节点n的总代价。在A*搜索算法中，选择下一个扩展的节点时，会选择f(n)最小的节点，即综合考虑实际代价和启 发式估计代价。
2、结合本实验举例说明不同启发策略对实验的效果有何影响？（可列出图表说明）
不同的启发策略对实验的效果会产生影响。在A*算法中，估价函数的选择会影响搜索的效率。例如，在罗马尼亚问题中，使用直线距离作为启发式函数可能会更快地找到解决方案，因为它提供了一种更直接的路径选择。然而，选择不同的启发式函数可能导致不同的搜索效果，有的可能更接近实际最优解，有的可能更快速但代价稍高。
3、若问题的初始状态是随机产生的，你的实验程序应该如何改进？（如图形属性的设置、图形队列存入文件等）添加代码，根据实际需要添加其他辅助函数。
- 将实验数据存入文件：可以将每个实验的数据（如搜索路径、代价等）存储在文件中，以便后续分析或可视化。
- 设置随机种子：如果使用了随机数生成器，可以设置随机种子以确保实验可重复。
- 添加统计信息：在程序中加入统计信息，如搜索节点的数量、路径的长度等，以便更全面地评估算法性能。
4、尝试使用一致代价(等代价)搜索, 迭代加深的深度优先搜索算法求解上述问题,并根据实验结果分析深度优先搜索，一致代价(等代价)搜索，迭代加深的深度优先搜索算法, A*搜索的时间和空间复杂度。
- 深度优先搜索：时间复杂度为O(b^m)，其中b是分支因子，m是最大搜索深度；空间复杂度为O(bm)。
- 一致代价(等代价)搜索：时间复杂度和空间复杂度均为O(b^(C*/ε))，其中C*是最优解的代价，ε是最小的代价步长。
- 迭代加深的深度优先搜索：时间复杂度为O(b^d)，其中d是最优解的深度；空间复杂度为O(bd)。
- A*搜索：在最坏情况下，时间复杂度为O(b^d)，其中d是最优解的深度；空间复杂度为O(b^d)。
（5）指出无信息搜索策略和有信息搜索策略的不同并比较其性能。
- 完备性：无信息搜索策略可能在某些情况下无法找到解决方案，而有信息搜索策略通常是完备的。
- 最优性：有信息搜索策略通常更容易找到最优解，而无信息搜索策略通常只能找到可行解。
- 时间和空间效率：有信息搜索策略通常能更快找到解决方案，但在计算和存储信息方面可能需要更多的时间和空间。
- 领域知识要求：有信息搜索策略通常需要对问题领域有一定的了解，而无信息搜索策略对领域知识的要求较低。
在实际应用中，选择无信息搜索还是有信息搜索通常取决于问题的性质和要求。
