[C++]:A*——A Star算法简介
A*算法 求最优解算法一直维护两个表: Open和Close将起点S加入Open中将所有S可到达的点（障碍物以及位于Close表中的点均看成不可达）加入到Open中。将起点从Open中删去，并加入到Close中①从Open中删去F值最小的点Min，并将其加入到Close中②将Min点所有可到达的点加入Open中，并设这些点的父节点为Min。若某点已经在Ope
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)是自己设计的函数，可以是到目的地大致的距离
可将循环过程封装成函数：
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
灰色的点G=10，H=9*10 ,其F值最小，加入Close
000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
灰色的点G=10+10，H=8*10 ,其F值最小，加入Close
000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
灰色的点G=10+10+10，H=7*10 ,其F值最小，加入Close
000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
灰色的点G=10+10+10+10，H=6*10 ,其F值最小，加入Close
以此循环，直到e在Open中，此时只需要沿着父节点往回走就可以到达起点了，这条路就是当前情况下最优的解
结果：
000000000000000
0000000x0000000
00s0000x0000e00
0000000x0000000
000000000000000
C++实现：
#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;i<open.size();i++) {
if (open[i].posi == s) {
return true;
}
}
return false;
}
bool isInCloseList(pair s) {
for (int i = 0;i<close.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].G+14);
}
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 it=open.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 i=0;i<open.size();i++) {
if (open[i].v == 'e') {
open[i].ParentPosi=close.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);
squ[i][j].UpdateH();//算出所有H
}
}//初始化point.posi
findPath(make_pair(2,2),make_pair(2,12));
point temp = squ[2][12];
vector<pair> point_out;
while (temp.posi!=squ[2][2].posi) {
//cout << "(" << temp.posi.first << "," << temp.posi.second << ")" << endl;
point_out.push_back(temp.posi);
temp=squ[temp.ParentPosi.first][temp.ParentPosi.second];
}
point_out.push_back(squ[2][2].posi);
while (point_out.size() != 0) {
cout << "(" << point_out.back().first<< "," << point_out.back().second<< ")" << endl;
point_out.pop_back();
}
}
void print() {
for (int i = 0;i < 5;i++) {
for (int j = 0;j < 15;j++) {
cout << square[i][j] << ' ';
}
cout << endl;
}
}
int main() {
//print();
print_path();
return 0;
}
加入社区！打开量化的大门，首批课程上线啦！
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)