HNU人工智能第一次实验报告
实验报告
1. 实验方法和步骤
本实验旨在实现A*搜索算法，并通过一个示例图进行路径规划。以下是实验的步骤：
-
实现A*搜索算法：首先需要实现A搜索算法的核心部分，包括节点的定义、图的表示、启发函数的定义以及A算法的主要流程。
-
构建示例图：在示例图中定义节点以及它们之间的连接关系，这些连接关系代表路径的代价。
-
调用A*算法：选择一个起始节点和目标节点，调用A*算法进行路径搜索，并输出搜索结果。
2. 算法原理说明
A*搜索算法是一种启发式搜索算法，用于在图或图形化的网络中找到从起始节点到目标节点的最佳路径。其基本原理是通过评估函数（评估函数通常由节点到目标节点的估计代价和节点到起始节点的实际代价组成）来指导搜索方向。
算法步骤：
- 初始化起始节点，并将其放入Open列表中。
- 从Open列表中选择评估函数值最小的节点，并将其移至Close列表中。
- 对于所选节点的相邻节点，计算它们的实际代价，并根据需要更新它们的估计代价和评估函数值。
- 重复步骤2和3，直到找到目标节点或Open列表为空。
3. 算法源程序
#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]={true}; //标记是否已经在集合内
vector<node> openList; //可访问节点集合
bool closeList[20]={false}; //已访问删除集合
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 **********/
node curr = openList[0];
if(curr.name == goal)
return;
closeList[curr.name]=true;
list[curr.name]=false;
openList.erase(openList.begin());
for(size_t i =0; i<20; i++){ //扩展相邻节点
if(graph.getEdge(curr.name,i)!=-1 && ! closeList[i]){
if (list[i]) //存在node,可直接扩展更新
{
size_t j;
for (j=0; j<openList.size(); j++){ //找到当前节点
if (openList[j].name == i)
break;
}
/*更新节点*/
int cost=curr.g+graph.getEdge(curr.name,i);
if (cost< openList[j].g)
{
openList[j].g = cost; //更新g
openList[j].f = cost + openList[j].h; //更新f
parent[i] = curr.name; //父节点为当前节点
}
}
else //节点未扩展,创建加入节点集合
{
node newNode(i,curr.g+graph.getEdge(curr.name, i), h[i]);
parent[i] = curr.name;
openList.push_back(newNode);
sort(openList.begin(), openList.end()); //排序
list[i]=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;
}
4. 实验结果分析
通过实验程序，我们成功地实现了A*搜索算法，并在给定的示例图上进行了路径规划。算法输出了从起始节点到目标节点的最佳路径，并计算了路径的代价。
实验结果表明，A*搜索算法能够有效地在图中找到最佳路径，并且在实际应用中具有广泛的适用性。通过合理选择启发函数，可以更好地引导搜索，提高搜索效率，同时保证了搜索结果的最优性。
5.时间复杂度分析
分析给出的代码段的时间复杂度，我们需要考虑几个关键的部分：图的初始化、A*搜索算法的主体循环、以及与数据结构（如优先队列）相关的操作。
1. 图的初始化
图的初始化通过init函数中一系列的addEdge调用完成。这里有固定数量的边被添加，每次添加边的操作可以认为是常数时间O(1)的。因此，对于给定的边数E，初始化的时间复杂度是O(E)。
2.A*搜索算法
A*搜索算法的时间复杂度依赖于几个因素：
-
节点的数目（N）：在最坏的情况下，算法可能访问图中的每个节点。
-
每个节点的邻居数量：平均每个节点的邻居数量可以用
E/N表示，其中E是边的总数。 -
向量插入（openList）操作：包括插入（push_back followed by sort）和删除最小元素（erase(begin)）。插入操作包括
push_back的O(1)，后跟一个sort操作的O(N*logN)（因为在最坏情况下，列表可能几乎包含所有节点）。删除操作是O(1)的，但是，由于在每次迭代后都对openList进行排序，这导致了较高的复杂度。
考虑到这些，主循环的时间复杂度主要由对openList的操作支配，特别是排序操作，它在每次循环迭代中都会执行。在最坏的情况下，如果openList几乎包含了图中的所有节点，那么每次排序的时间复杂度是O(N*logN)。由于这可能发生在算法的每一步，且每个节点至少被访问一次，总体复杂度可以是O(N^2*logN)。
因此，整体的时间复杂度主要由A*搜索算法中对openList的排序操作支配，即O(N^2*logN)。这不考虑特定的启发式函数可能对实际性能的影响，启发式函数的好坏可以显著影响搜索的效率，可能使得实际运行时间远低于最坏情况复杂度。此外，使用更高效的数据结构（如斐波那契堆）代替简单数组加排序，可以将优先队列的插入和删除操作优化到接近O(1)，大大改善算法的时间复杂度。
6.思考题解答
1. 宽度优先搜索、深度优先搜索、一致代价搜索、迭代加深的深度优先搜索算法哪种方法最优？
-
宽度优先搜索(BFS) 是按照节点的宽度进行遍历，保证了如果有解，将在最少步骤内找到解，适合寻找最短路径问题，但是空间复杂度较高。
-
深度优先搜索(DFS) 是沿着路径深入直到无法继续，然后回溯到上一个节点继续搜索，它的空间复杂度较低，但可能不会找到最优解。
-
一致代价搜索(UCS) 是一种扩展代价最低的节点的策略，保证找到的第一个解是最低代价的解，适用于路径代价不同的图。
-
迭代加深的深度优先搜索(IDDFS) 结合了DFS的空间效率和BFS找到最短路径的优点，逐渐增加深度限制，直到找到解。
-
最优性选择：没有绝对的最优搜索策略，每种策略根据不同的应用场景和需求具有不同的优势。例如，如果目标是找到最短路径，则BFS或UCS更优；如果内存空间有限，DFS或IDDFS可能更适用。
2. 贪婪最佳优先搜索和A*搜索那种方法最优？
-
贪婪最佳优先搜索 仅基于启发式信息（从当前节点到目标节点的估计代价）进行搜索，它忽略了起点到当前节点的实际代价，因此可能不会找到最低代价的路径。
-
A*搜索 结合了起点到当前节点的实际代价和当前节点到目标节点的估计代价，如果启发式函数是可采纳的（admissible），则保证找到最低代价的路径。
-
最优性选择：A*搜索通常比贪婪最佳优先搜索更优，因为它考虑了从起点到当前节点的代价，能够找到最优路径。但贪婪搜索在某些情况下可能在时间上更有效，尤其是当正确路径非常明显时。
3. 分析比较无信息搜索策略和有信息搜索策略。
-
无信息搜索策略（如BFS、DFS和UCS）不使用关于目标的任何先验知识。这些搜索策略仅仅基于问题的结构进行搜索。它们通常不考虑节点到目标节点的任何估计代价，因此可能在找到解的过程中探索大量不必要的路径。
-
优点：简单、直接，对所有问题通用。
-
缺点：效率低下，特别是在大搜索空间中，可能会探索大量无关路径。
-
-
有信息搜索策略（如贪婪最佳优先搜索和A*搜索）使用启发式函数来估计从当前节点到目标节点的代价，这种策略能更有效地指导搜索方向，减少搜索空间。
-
优点：效率更高，通过启发式函数减少了搜索空间和时间。
-
缺点：依赖于启发式函数的选择，如果启发式函数选择不当，可能会导致搜索效率低下或找不到最优解。
-
-
比较：有信息搜索策略通常比无信息搜索策略更优，因为它们能够利用额外的信息（启发式）来指导搜索过程，减少不必要的搜索。然而，选择合适的启发式函数是实现有效有信息搜索的关键。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
4
0- 0
已为社区贡献5条内容
所有评论(0)