[C++]:A*——A Star算法简介

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 条评论
登录 后参与评论

相关文章

来自专栏性能与架构

算法中描述复杂度的大O是什么意思?

简介 算法是解决问题的方法,通常一个问题会有多种解决方法,就是有多种算法,那么我们如何决定哪个算法更好或者更高效呢? 为了描述一个算法的效率,就用到了这个大O,...

3415
来自专栏AzMark

Matplotlib 系列之「Legend 图例」

Matplotlib 的 Legend 图例就是为了帮助我们展示每个数据对应的图像名称,更好的让读者认识到你的数据结构。

871
来自专栏简书专栏

基于tensorflow+CNN的搜狐新闻文本分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 CNN是convolutional neural netwo...

2922
来自专栏AI研习社

Github 项目推荐 | 用 tf * idf 计算文本之间的相似度

该库是具有 tf * idf 权重的 Ruby 向量空间模型(VSM),它能够用 tf * idf 计算文本之间的相似度。

1404
来自专栏Soul Joy Hub

TensorFlow指南(二)——练习思考:上手TensorFlow

http://blog.csdn.net/u011239443/article/details/79075392 创建一个计算图而不是直接执行计算的主要好处是...

3094
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

1002
来自专栏用户2442861的专栏

一致性hash算法 - consistent hashing

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

1041
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

1031
来自专栏wym

opencv imwrite函数参数详解+例子

cv2.imwrite(1."图片名字.格式",2.Mat类型的图像数据,3.特定格式保存的参数编码,默认值std::vector<int>()  所以一般可以...

8472
来自专栏帮你学MatLab

《Experiment with MATLAB》读书笔记(二)

读书笔记(二) 这是第二部分函数与绘图 将代码复制到m文件即可运行 函数部分需新建m文件保存 %% 函数 % 变量在用之前先赋0站位 % 计数或者...

3027

扫码关注云+社区

领取腾讯云代金券