Ecoder.使用A*搜索算法实现罗马尼亚问题的求解

it2025-01-13  5

任务描述

了解有信息搜索策略的算法思想;能够运用计算机语言实现搜索算法;应用A*搜索算法解决罗马尼亚问题;

相关知识

A*搜索

算法介绍

A*算法常用于 二维地图路径规划,算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索,从而减少搜索范围,控制搜索规模,降低实际问题的复杂度。

算法原理:

A*算法的原理是设计一个代价估计函数: 其中 :

评估函数F(n) 是从起始节点通过节点n的到达目标节点的最小代价路径的估计值函数G(n)是从起始节点到n节点的已走过路径的实际代价函数H(n)是从n节点到目标节点可能的最优路径的估计代价 。

函数 H(n)表明了算法使用的启发信息,它来源于人们对路径规划问题的认识,依赖某种经验估计。根据 F(n)可以计算出当前节点的代价,并可以对下一次能够到达的节点进行评估。 采用每次搜索都找到代价值最小的点再继续往外搜索的过程,一步一步找到最优路径。

编程要求

罗马尼亚问题:agent在罗马尼亚度假,目前位于 Arad 城市。agent明天有航班从Bucharest 起飞,不能改签退票。 现在你需要寻找到 Bucharest 的最短路径,在右侧编辑器补充void A_star(int goal,node &src,Graph &graph)函数,使用编写的搜索算法代码求解罗马尼亚问题:

测试说明 平台会对你编写的代码进行测试:

预期输出:

solution: 0-> 15-> 14-> 13-> 1-> end cost:418

开始你的任务吧,祝你成功!

编程实现

实现思想

算法维护2个集合,openList用来表示当前扩展节点集合,closeList用来表示当前已经被搜索过的节点。用数组list记录节点v在openList中每次从openList中取出首节点u,并且对当扩展某个节点u的时候,搜索他的子节点v,如果子节点v不在closeList中,并且v在集合openList中那么计算新的<从起始节点到n节点的已走过路径的实际代价>cost,如果cost小于当前的路径消耗g,则更新扩展节点v的消耗 int cost=cur.g+graph.getEdge(cur.name,i); 如果当前节点不在closeList中,并且不在扩展集合中,则将其加入扩展集合,并且排序

代码实现

#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; /* *从n节点到目标节点可能的最优路径的估计代价 */ int h[20] = { 366,0,160,242,161, 178,77,151,226,244, 241,234,380,98,193, 253,329,80,199,374 }; /* *一个节点结构,node */ struct node { int g; //从起始节点到n节点的已走过路径的实际代价 int h; //从n节点到目标节点可能的最优路径的估计代价 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));//图初始化为-1 } 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]; //图数组,用来保存图信息,最多有20个节点 }; bool list[20]; //用于记录节点i是否在openlist集合中 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()) { /*取代价最小的节点*/ node cur = openList[0]; //取首节点,代价最小 if (cur.name == goal) //目标 return; openList.erase(openList.begin()); //从openlist序列中删除这个节点 list[cur.name] = false; //将当前节点标记为不在openList中 closeList[cur.name] = true; //将当前节点加入closeList /*遍历子节点*/ for (int i = 0; i < 20; i++) { if (graph.getEdge(cur.name, i) != -1 && !closeList[i]) //节点相邻并且不在close中,可访问 { if (list[i]) //如果在list序列中,说明属于扩展节点集 { int j=0; for (int j=0; j<openList.size(); j++){ //遍历,找到当前节点的位置 if (openList[j].name == i) break; } /*刷新节点*/ int cost=cur.g+graph.getEdge(cur.name,i); if (cost< openList[j].g) { openList[j].g = cost; //更新g openList[j].f = cost + openList[j].h; //更新f parent[i] = cur.name; //更新parent } } else //节点不在openList,则创建一个新点,加入openList扩展集 { node newNode(i,cur.g+graph.getEdge(cur.name, i), h[i]); parent[i] = cur.name; openList.push_back(newNode); sort(openList.begin(), openList.end()); //排序 list[i]=true; } } } } } 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(); int goal = B; node src(A, 0, h[A]); list[A] = true; memset(parent, -1, sizeof(parent)); memset(list, false, sizeof(list)); A_star(goal, src, graph); print_result(graph); return 0; }
最新回复(0)