HNU-人工智能-实验1-A*算法

2024-05-06 04:12
文章标签 算法 实验 人工智能 hnu

本文主要是介绍HNU-人工智能-实验1-A*算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

人工智能-实验1

计科210x 甘晴void
在这里插入图片描述

一、实验目的

  • 掌握有信息搜索策略的算法思想；

  • 能够编程实现搜索算法；

  • 应用A*搜索算法求解罗马尼亚问题。

二、实验平台

  • 课程实训平台https://www.educoder.net/shixuns/vgmzcukh/challenges

三、实验内容

3.0 题目要求

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

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

在这里插入图片描述

3.1 A*算法原理

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

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

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

3.2 算法实现

根据题目要求，实现A*算法，如下图。
在这里插入图片描述

初始给定出发节点，放入openList队列，然后进行扩展操作

  • 扩展操作：对于所有与该节点相连的节点，计算它们的g()值，然后加上h()值，得到f()值，并加入openList队列。
  • openList队列：该队列本质是一个优先队列，以队列中各元素节点的f()值为键进行排序。给定的程序中使用sort+优先队列来实现，实际上这里直接使用优先队列来进行维护会效率更高，这是可以优化的一个点。
  • 选定操作：在扩展，优先化（也就是题中的sort）之后，选定一个f()值最大的作为下一个访问的节点。
  • 访问节点：任何节点的访问操作只能进行一次，但是扩展操作可以进行多次（这其实也可以理解，再次访问该节点显然比原来访问该节点的代价高）
  • 终止条件：按照上述循环重复执行，直至访问到（不是扩展到）目标终点为止。

基本思路可以用下述伪代码展示

void A_star(int goal, node *src, Graph &graph)
{openList.push_back(src);sort(openList.begin(), openList.end(), cmp);while (!openList.empty()){node *now = new node;now = openList.front();openList.erase(openList.begin());// 选定操作（从优先的openList中获取第一个元素）if (now->name == goal){// 终止条件：到达终点，保存退出return;}for (int i = 0; i < 20; i++){if (graph.getEdge(now->name, i) != -1 && !visited[i])// 有边且未被访问过{node *expand = new node(i, now->g + graph.getEdge(now->name, i), h[i], now);openList.push_back(expand);// 执行扩展操作}}sort(openList.begin(), openList.end(), cmp);// 保证按照键优先化}
}

3.3 源码&分析

#include <algorithm>
#include <iostream>
#include <memory.h>
#include <stack>
#include <vector>
#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 19using 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 **********/node now = openList.front();if (now.name == goal)return;openList.erase(openList.begin());closeList[now.name] = 1;for (int i = 0; i < 20; i++){if (graph.getEdge(now.name, i) != -1 && !closeList[i]){node expand(i, now.g + graph.getEdge(now.name, i), h[i]);openList.push_back(expand);int flag = true;for (unsigned int j = 0; j < openList.size(); j++){if (openList[j].name == expand.name && openList[j].g < expand.g){flag = false;}}if (flag == true)parent[i] = now.name;}}sort(openList.begin(), openList.end());/********** 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;
}int main()
{Graph graph;graph.init();for (int i = 0; i < 20; i++)parent[i] = -1;node src(0, 0, h[0]);A_star(1, src, graph);print_result(graph);
}

具体分析如下：

  • 结构体定义：结构体 node 定义了节点的属性，包括节点名称 name，从起点到该节点的路径长度 g，该节点到目标节点的估计距离 h，以及综合路径长度和估计距离的总代价 f。重载了小于操作符，以便在优先队列中进行排序。
  • 图的表示：使用二维数组 graph[20][20] 表示图，数组大小为 20x20，即有 20 个节点。数组中存储了节点之间的边的权值。
  • 初始化图：在 Graph 类的 init() 方法中，添加了节点之间的边及对应的权值。
  • A*搜索算法：A_star 函数实现了A*搜索算法。它通过优先队列 openList 来管理待扩展的节点，并且利用数组 closeList 来记录已经访问过的节点。parent 数组用于记录每个节点的父节点，方便后续回溯路径。算法首先将起始节点加入到 openList 中，并进行排序。然后，循环进行以下步骤：
    • 取出 openList 中的首节点 now，如果该节点是目标节点，则搜索结束。
    • 将 now 加入到 closeList 中，表示已经访问过。
    • 遍历与当前节点相邻的节点，如果相邻节点未被访问过，则将其加入到 openList 中，并更新其父节点为当前节点，并根据当前节点到该相邻节点的路径长度以及该节点到目标节点的估计距离计算总代价 f。
    • 最后对 openList 进行排序，以保证优先扩展代价较小的节点。
  • 打印结果：print_result 函数用于打印搜索结果，即输出找到的最短路径以及路径的总代价。
    • 将起始节点压入栈中。
    • 从目标节点开始，通过 parent 数组逐步向上回溯，将经过的节点依次压入栈中，直到回溯到起始节点。
    • 在压入栈的过程中，同时计算路径的总代价。因为 A* 算法是一种启发式搜索算法，搜索到的路径并不一定是最优的，但它会在每一步中选择一个启发性最好的节点进行扩展，因此得到的路径一般是较优的。
    • 最后，从栈中依次弹出节点，打印出完整的路径，并输出路径的总代价。
  • 主函数：在主函数中，首先初始化图，然后调用 A_star 函数进行搜索，并最终打印搜索结果。【注意】主函数是在线平台中没有的，在线平台应该指定了程序入口并做了变量初始化的工作。因此我们用主函数来实现这个工作。

综上所述，这段代码实现了使用A*算法在给定图中寻找从起点到目标点的最短路径，并输出了路径以及路径的总代价。

3.4 基于题目的代码：算法分析

时间复杂度可能趋近于O(n^3)，主要原因与维护parent数组的最新性有关，这个后面在讲想法的时候会具体说明。

空间复杂度应该有O(n^2)，因为使用邻接矩阵来存储图。

3.5 基于题目的代码：困惑思考

基于题目做这道题的时候，我感觉很困惑。

A*算法不是一个非常复杂的算法，但题目中的一些操作让我感觉有点迷。

①parent数组问题

题目使用openList中保存被扩展的节点，然后用closeList来标记被访问的节点，用parent来存储每个节点的父亲这种方式。

这会带来一个挑战：在一个节点被扩展之后，它不一定被立即访问。

如下面这张图，Sibiu节点的四个子节点中，最右子节点Rimnicu Vilcca先被访问，但后来Sibiu的左起第二个子节点Fagaras又被访问到了。此时若该两个子节点都有相同的另一个子节点M，则M可能同时具有Rimnicu Vilcca和Fagaras两个父节点。这样用一个parent数组显然是没办法表示的（注意这里不能是覆盖关系，因为这两个子节点都是“被扩展”的状态而不是“已被访问”的状态，真正被访问的节点有可能从它们之一产生）

在这里插入图片描述

比如，出现下图所示情况。若Bucharest不是最终节点，则它同时又两个parent，这显然无法用一个parent数组存下。

在这里插入图片描述

因此理想的方法是将parent作为一个属性写入该节点的node结构体中去。但这样还没解决一个问题，输出结果会有点烦。

或者使用后面改进的方法，直接用指针来作为属性。这样只需要指针走一遍，就可以把顺序给呈现出来了。

但是，原题中我也想办法解决了，其实观察或者是从题目中可以发现，一个节点如果发现有比它g()值更小的节点，实际上g()值较大的那个显然就没有用了，即使予以保留，最终也会在较低优先级而不会被调用（这个实际上看的是f()值，事实上是一样的，因为f()=g()+h()，h()显然只与节点有关系）。故我直接略去g()值较大的节点，默认它们直接被淘汰掉了，parent数组只保存g()值最小的那个所对应的。

②vector+sort替代priority_queue

题目中使用了vector来保存访问节点的结构体，再加上sort来保证优先级，其实可以直接用priority_queue来实现，效率更高。

3.6 改进代码-结构体

只展示核心代码，略去重复的宏定义部分和graph类。

使用结构体和指针绕开了parent数组的问题

#include <algorithm>
#include <iostream>
#include <memory.h>
#include <stack>
#include <vector>
#define A-Z (略)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 *parent;node() {}node(int name, int g, int h, node *parent){this->name = name;this->g = g;this->h = h;this->f = g + h;this->parent = parent;};bool operator<(const node a) const{return f < a.f;}
};class Graph //（略）vector<node *> openList;
node *des;
bool visited[20];bool cmp(node *a, node *b) { return a->f < b->f; }
void A_star(int goal, node *src, Graph &graph)
{openList.push_back(src);sort(openList.begin(), openList.end(), cmp);while (!openList.empty()){node *now = new node;now = openList.front();openList.erase(openList.begin());visited[now->name] = 1;// cout << now->name << endl;// system("pause");if (now->name == goal){des = now;return;}for (int i = 0; i < 20; i++){if (graph.getEdge(now->name, i) != -1 && !visited[i]){node *expand = new node(i, now->g + graph.getEdge(now->name, i), h[i], now);openList.push_back(expand);// cout << "expand: " << expand->name << endl;}}sort(openList.begin(), openList.end(), cmp);}
}void print_result(Graph &graph)
{cout << "solution: ";stack<int> ans;node *now = des;while (now != NULL){ans.push(now->name);// cout << now->name << endl;now = now->parent;}while (!ans.empty()){cout << ans.top() << "-> ";ans.pop();}cout << "end" << endl;cout << "cost:" << des->g << endl;
}int main()
{Graph graph;graph.init();memset(visited, 0, sizeof(visited));node *src = new node(0, 0, h[0], NULL);A_star(1, src, graph);print_result(graph);
}

3.7 改进代码2-<priority_queue>

只需要在上面代码的基础上更改部分即可，但考虑到这里使用的其实是结构体的指针，故重载运算符其实不太好操作。我采取使用比较函数的方法来完成大小的判断。

bool cmp(node *a, node *b) { return a->f > b->f; }
priority_queue<node *, vector<node *>, decltype(&cmp)> openList(&cmp);void A_star(int goal, node *src, Graph &graph)
{openList.push(src);while (!openList.empty()){node *now = new node;now = openList.top();openList.pop();visited[now->name] = 1;// cout << now->name << endl;// system("pause");if (now->name == goal){des = now;return;}for (int i = 0; i < 20; i++){if (graph.getEdge(now->name, i) != -1 && !visited[i]){node *expand = new node(i, now->g + graph.getEdge(now->name, i), h[i], now);openList.push(expand);// cout << "expand: " << expand->name << endl;}}}
}

3.8 运行截图

在这里插入图片描述

四、思考题

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

首先分析这四种算法，

  • 宽度优先搜索（BFS）：通常在最短路径问题上表现优异，但是空间复杂度很高，因为需要保存所有已经访问的节点。
  • 深度优先搜索（DFS）：解空间较大，在解相对较浅的问题上可能更有效率，但是可能会陷入无限深度的分支。
  • 迭代加深深度优先搜索（IDDFS）：结合了DFS和BFS的优点，在不断增加的深度限制上调用深度受限搜索。对于深度搜索问题而言，是一种比较有效的方法。
  • 一致代价搜索（UCS）：保证在图中搜索的每一步都是最小代价的算法，通常在无启发式的情况下用于解决最短路径问题。

对于一般的问题而言，一致代价搜索是更优的。但对于不同问题要具体问题具体分析，如问题的时间或空间限制等。

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

首先分析这两种算法，

  • 贪婪最佳优先搜索：根据启发式函数h()所提供的信息，每次选择看起来最有希望的节点进行扩展，但是它不能保证找到最优解，因为它没有考虑到节点到目标的真实代价。
  • A*搜索算法：通过综合考虑节点的实际代价g()和启发式函数h()的估计值，保证了在每一步都能选择到最优的节点进行扩展，从而保证找到最优解。

A*搜索算法通常在需要找到最优解的问题上更为优秀，因为它考虑了实际代价。

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

无信息搜索策略和有信息搜索策略是指搜索算法是否利用额外的信息来指导搜索方向：

  • 无信息搜索策略，如深度优先搜索（DFS）、宽度优先搜索（BFS）和一致代价搜索（UCS），只利用当前节点的信息进行搜索，不考虑节点到目标的距离或代价，因此可能需要更多的搜索步骤来找到解。
  • 有信息搜索策略，如A*搜索算法和贪婪最佳优先搜索，利用启发式函数提供的额外信息（如节点到目标的估计距离）来指导搜索方向，从而更快地找到解。有信息搜索策略通常能更快地找到最优解，但是需要在空间和时间上付出更多的代价来计算和存储启发式函数的值。

这篇关于HNU-人工智能-实验1-A*算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/963408。

相关文章

使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
Springboot实现推荐系统的协同过滤算法

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品（如商品、电影、音乐等）的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法（Collaborativ
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2