网站建设收费分几次,苍南哪里有网站建设公司,广告设计公司是做什么的,wordpress 5.0文章编辑教程1.任务描述
本关任务#xff1a;
了解有信息搜索策略的算法思想#xff1b;能够运用计算机语言实现搜索算法#xff1b;应用A*搜索算法解决罗马尼亚问题#xff1b;
2.相关知识
A*搜索
算法介绍
A*算法常用于 二维地图路径规划#xff0c;算法所采用的启发式搜索可以…1.任务描述
本关任务
了解有信息搜索策略的算法思想能够运用计算机语言实现搜索算法应用A*搜索算法解决罗马尼亚问题
2.相关知识
A*搜索
算法介绍
A*算法常用于 二维地图路径规划算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索从而减少搜索范围控制搜索规模降低实际问题的复杂度。
算法原理
A*算法的原理是设计一个代价估计函数其中 **评估函数F(n)**是从起始节点通过节点n的到达目标节点的最小代价路径的估计值函数G(n)是从起始节点到n节点的已走过路径的实际代价函数H(n)是从n节点到目标节点可能的最优路径的估计代价 。
函数 H(n)表明了算法使用的启发信息它来源于人们对路径规划问题的认识依赖某种经验估计。根据 F(n)可以计算出当前节点的代价并可以对下一次能够到达的节点进行评估。
采用每次搜索都找到代价值最小的点再继续往外搜索的过程一步一步找到最优路径。
3.编程要求
罗马尼亚问题agent在罗马尼亚度假目前位于 Arad 城市。agent明天有航班从Bucharest 起飞不能改签退票。
现在你需要寻找到 Bucharest 的最短路径在右侧编辑器补充void A_star(int goal,node src,Graph graph)函数使用编写的搜索算法代码求解罗马尼亚问题 4.测试说明
平台会对你编写的代码进行测试
预期输出
solution: 0- 15- 14- 13- 1- end
cost:4185.实验过程
下面是关于非补充部分的代码解释
1.宏定义每个城市名和编号
#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 192.记录启发函数h数组即从n节点到目标节点可能的最优路径的估计代价
int h[20] //从n节点到目标节点可能的最优路径的估计代价
{ 366,0,160,242,161,
178,77,151,226,244,
241,234,380,98,193,
253,329,80,199,374 };3.定义城市节点的结构体
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; }
};4.定义图结构记录图中各节点和边的信息
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个节点
};5.一些数据结构的定义
bool list[20]; //用于记录节点i是否在openList集合中
vectornode openList; //扩展节点集合
bool closeList[20]; //已访问节点集合
stackint road; //路径
int parent[20]; //父节点用于回溯构造路径1.补充void A_star(int goal, node src, Graph graph)函数
主要思想是利用一个估价函数f(n)来评估每个节点n的优先级f(n)由两部分组成g(n)表示从起点到节点n的实际代价h(n)表示从节点n到终点的预估代价。A*算法每次选择f(n)最小的节点进行扩展直到找到终点或者没有可扩展的节点为止
代码如下
void A_star(int goal, node src, Graph graph)//A*搜索算法
{openList.push_back(src); //扩展集合加入起始节点sort(openList.begin(), openList.end()); //排序扩展集合的节点以取出代价最小的节点while (!openList.empty()){/********** Begin **********/node curNode openList[0]; //取出扩展集合第一个节点即代价最小的节点if (curNode.name goal) { //如果当前节点就是目标节点则退出return;}openList.erase(openList.begin()); //将当前节点从扩展列表中删除closeList[curNode.name] true; //将当前节点加入已访问节点list[curNode.name] false; //标记当前节点已不在扩展集合中for (int i 0; i 20; i) { //开始扩展当前节点即找到其邻居节点if (graph.getEdge(i, curNode.name) -1) { //若不是当前节点的邻居节点跳到下一个节点continue;}if (closeList[i]) { //若此节点已加入已访问集合closeList也跳到下一个节点continue;}int g1 curNode.g graph.getEdge(i, curNode.name); //计算起始节点到当前节点i的g值int h1 h[i]; //获得当前节点i的h值if (list[i]) { //如果节点i在openList中for (int j 0; j openList.size(); j) {if (i openList[j].name) { //首先找到节点i的位置即jif (g1 openList[j].g) { //如果新的路径的花销更小则更新openList[j].g g1;openList[j].f g1 openList[j].h;parent[i] curNode.name; //记录父节点break;}}}}else { //如果节点i不在openList则将其加入其中因为扩展时访问了它node newNode(i, g1, h1); //创建新节点其参数已知openList.push_back(newNode); //新节点加入openList中parent[i] curNode.name; //记录父节点list[i] true; //记录节点i加入了openList}}sort(openList.begin(), openList.end()); //扩展完当前节点后要对openList重新排序/********** End **********/}
}首先扩展起始节点将扩展集合中的节点按照优先级进行排序。接着按照优先级不断扩展扩展集合中的节点直到找到终点或者没有可扩展的节点为止。
每次扩展首先取出扩展集合第一个节点判断其是否为目标节点若是则退出。扩展该节点后需要将其加入已访问集合并从扩展集合中删除同时用list数组标记其已扩展。
接着扩展该节点即寻找其邻居节点。
如果邻居节点在扩展集合中则查看其更新后代价是否比原本的代价更优优则更新它。同时记录父节点以用于回溯生成路径
如果邻居节点不在扩展集合中则将其加入扩展集合中记录父节点并用list数组标记为在扩展集合中
每次扩展完节点后都要对扩展集合里的节点进行一次优先级的排序用于下一个循环来取出当前优先级最高的节点
6.void print_result(Graph graph)函数
用于打印路径和开销
void print_result(Graph graph) //用于打印路径和开销
{int p openList[0].name; //p即为目标节点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;
}6.完整代码
#includeiostream
#includevector
#includememory.h
#includestack
#includealgorithm#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] //从n节点到目标节点可能的最优路径的估计代价
{ 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集合中
vectornode openList; //扩展节点集合
bool closeList[20]; //已访问节点集合
stackint road; //路径
int parent[20]; //父节点用于回溯构造路径void A_star(int goal, node src, Graph graph)//A*搜索算法
{openList.push_back(src); //扩展集合加入起始节点sort(openList.begin(), openList.end()); //排序扩展集合的节点以取出代价最小的节点while (!openList.empty()){/********** Begin **********/node curNode openList[0]; //取出扩展集合第一个节点即代价最小的节点if (curNode.name goal) { //如果当前节点就是目标节点则退出return;}openList.erase(openList.begin()); //将当前节点从扩展列表中删除closeList[curNode.name] true; //将当前节点加入已访问节点list[curNode.name] false; //标记当前节点已不在扩展集合中for (int i 0; i 20; i) { //开始扩展当前节点即找到其邻居节点if (graph.getEdge(i, curNode.name) -1) { //若不是当前节点的邻居节点跳到下一个节点continue;}if (closeList[i]) { //若此节点已加入已访问集合closeList也跳到下一个节点continue;}int g1 curNode.g graph.getEdge(i, curNode.name); //计算起始节点到当前节点i的g值int h1 h[i]; //获得当前节点i的h值if (list[i]) { //如果节点i在openList中for (int j 0; j openList.size(); j) {if (i openList[j].name) { //首先找到节点i的位置即jif (g1 openList[j].g) { //如果新的路径的花销更小则更新openList[j].g g1;openList[j].f g1 openList[j].h;parent[i] curNode.name; //记录父节点break;}}}}else { //如果节点i不在openList则将其加入其中因为扩展时访问了它node newNode(i, g1, h1); //创建新节点其参数已知openList.push_back(newNode); //新节点加入openList中parent[i] curNode.name; //记录父节点list[i] true; //记录节点i加入了openList}}sort(openList.begin(), openList.end()); //扩展完当前节点后要对openList重新排序/********** End **********/}
}void print_result(Graph graph) //用于打印路径和开销
{int p openList[0].name; //p即为目标节点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; //目标节点Bnode src(A, 0, h[A]); //起始节点Alist[A] true;memset(parent, -1, sizeof(parent)); //初始化parentmemset(list, false, sizeof(list)); //初始化listA_star(goal, src, graph);print_result(graph);return 0;
}运行结果
