做美食有哪些网站,wordpress游戏代练主题,域名网站账号,知名网站建设多少钱A*算法 求最优解
算法一直维护两个表: Open和Close
将起点S加入Open中将所有S可到达的点#xff08;障碍物以及位于Close表中的点均看成不可达#xff09;加入到Open中。将起点从Open中删去#xff0c;并加入到Close中①从Open中删去F值最小的点Min#xff0c;并将其加入到…A*算法 求最优解
算法一直维护两个表: Open和Close
将起点S加入Open中将所有S可到达的点障碍物以及位于Close表中的点均看成不可达加入到Open中。将起点从Open中删去并加入到Close中①从Open中删去F值最小的点Min并将其加入到Close中②将Min点所有可到达的点加入Open中并设这些点的父节点为Min。若某点已经在Open中则比较其F值若新路径F值较小说明从Min走路更短更新其父节点为Min否则不更新此点循环①②直到Open中出现目的点E
公式表示为 f(n)g(n)h(n),
其中 f(n) 是从初始状态经由状态n到目标状态的代价估计
g(n) 是在状态空间中从初始状态到状态n的实际代价
h(n) 是从状态n到目标状态的最佳路径的估计代价。
通俗一点讲:
g(n)代表你从起始点到下一点的实际距离制定到下一点的距离的规则
h(n)是自己设计的函数可以是到目的地大致的距离可将循环过程封装成函数
[cpp] view plaincopy while (isNotEnd()) { Find_deleteMinFromOpen_AddToClose(); putReachableIntoOpen(close.back()); } 举个栗子
对于以下图5行15列
000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
其中x为墙壁s为起点e为终点建立合适的模型调用A star算法找到一条s到e的最短路径。
取直走G值为10斜走G值为14
这里H值设定为无视障碍到达终点所需的 步数*10
我们看开始的几步000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
灰色的点G10H9*10 ,其F值最小加入Close000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000灰色的点G1010H8*10 ,其F值最小加入Close000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000灰色的点G101010H7*10 ,其F值最小加入Close000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000灰色的点G10101010H6*10 ,其F值最小加入Close以此循环直到e在Open中此时只需要沿着父节点往回走就可以到达起点了这条路就是当前情况下最优的解结果000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000C实现
[cpp] view plaincopy#include#include#include#includeusing namespace std; char square[5][15] {//待求数据 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,x,0,0,0,0,0,0,0, 0,0,s,0,0,0,0,x,0,0,0,0,e,0,0, 0,0,0,0,0,0,0,x,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; class point { public: point(char s) { v s; G 0; H 0; F 0; } pair ParentPosi; pair posi; char v;//value int F; int G; int H; int UpdateF() { F G H; return F; } int UpdateH() { int x posi.first - 2; int y posi.second - 12; x * 10; y * 10; if (x 0) { x -x; } if (y 0) { y -y; } H x y; return H; } void setPosi(pair x) { posi x; } void setParentPosi(pair x) { ParentPosi x; } void setG(int g) { G g; } void setH(int h) { H h; } point operator (point s) { (*this).v(s).v; (*this).ParentPosi s.ParentPosi; (*this).posi s.posi; (*this).F s.F; (*this).G s.G; (*this).H s.H; return *this; } }; vector open; vector close; point squ[5][15] { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,x,0,0,0,0,0,0,0, 0,0,s,0,0,0,0,x,0,0,0,0,e,0,0, 0,0,0,0,0,0,0,x,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; bool isInOpenList(pair s) { for (int i 0;iopen.size();i) { if (open[i].posi s) { return true; } } return false; } bool isInCloseList(pair s) { for (int i 0;iclose.size();i) { if (close[i].posi s) { return true; } } return false; } void putReachableIntoOpen(point min) { int x min.posi.first; int y min.posi.second; int direc[8][2] { 0,1, 1,1, 1,0, 1,-1, 0,-1, -1,-1, -1,0, -1,1 }; for (int i 0;i 8;i) { x x direc[i][0]; y y direc[i][1]; if (isInOpenList(make_pair(x, y))close.size()0) { int tempi 0; for (int i 0;i open.size();i) { if (open[i].posi make_pair(x, y)) { tempi i; } } if (direc[i][0] * direc[i][1] ! 0) {//斜向 int G_now close.back().G 14; if (G_now open[tempi].G) { //G比较小就更新路径 open[tempi].ParentPosi make_pair(x, y); squ[open[tempi].posi.first][open[tempi].posi.second].ParentPosi make_pair(x, y); } } else { int G_now close.back().G 10; } continue; } //既不在关闭也不在开启列表中而且可到达 就将其加入开启列表 if ((!isInOpenList(make_pair(x, y))) (!isInCloseList(make_pair(x,y)))x 0 x 5 square[x][y] ! x) { squ[x][y].setParentPosi(min.posi); open.push_back(squ[x][y]); if (direc[i][0] * direc[i][1] ! 0) {//斜向 squ[x][y].setG(squ[x][y].G14); } else { squ[x][y].setG(squ[x][y].G 10); } //cout ( squ[x][y].posi.first , squ[x][y].posi.second ) endl; } x x - direc[i][0]; y y - direc[i][1]; } //cout ------------------------ ( x , y ): ------------------------ endl; } void Find_deleteMinFromOpen_AddToClose() { point min_ open[0]; int tempi 0; for (int i 0;i open.size();i) { if (open[i].UpdateF() min_.UpdateF()) { min_ open[i]; tempi i; } } close.push_back(min_); std::vector::iterator itopen.begin()tempi; open.erase(it); //cout close: ( min_.posi.first , min_.posi.second ) endl; //cout closeSize() close.size() endl; //cout openSize() open.size() endl; } bool isNotEnd() { for (int i0;iopen.size();i) { if (open[i].v e) { open[i].ParentPosiclose.back().posi; return false; } } return true; } void findPath(pair begin,pairend) { //将起点放入open open.push_back(squ[2][2]); putReachableIntoOpen(squ[2][2]); int tempi 0; for (int i 0;i open.size();i) { if (open[i].v s) { tempi i; } } std::vector::iterator it open.begin()tempi;//删除起点 while (isNotEnd()) { Find_deleteMinFromOpen_AddToClose(); putReachableIntoOpen(close.back()); } } void print_path() { for (int i 0;i 5;i) { for (int j 0;j 15;j) { squ[i][j].posi make_pair(i, j);
