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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2