2023年12月1日发(作者：360监控摄像头app下载安装)

头歌平台-⼈⼯智能-使⽤搜索算法实现罗马尼亚问题的求解

EduCoder平台：⼈⼯智能导论第3章-通过搜索问题进⾏求解

第1关：使⽤搜索算法实现罗马尼亚问题的求解

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

代码如下：

//

//

// -

罗马尼亚问题搜索算法

//

// Created by MacBook Pro on 2021/10/18.

//

#include

#include

#include

#include

#include

#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]; //iopenlist

⽤于记录节点是否在集合中

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 //openListopenList

节点不在，则创建⼀个新点，加⼊扩展集

{

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()); //f

按照节点的排序

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);

cout<<endl;

return 0;

}