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

相关文章

来自专栏蜉蝣禅修之道

CMU算法求网络瓶颈链路

1346
来自专栏智能算法

数据异常到底该如何检测?(一)

小编在正式进入工作之后,面对的第一个需要去解决的问题:在网络安全监测中,如何发现异常数据?如异常用户登录,异常操作等。对于网络上的问题我确实是第一次接触这样类型...

2877
来自专栏CreateAMind

深度学习框架TensorFlow 官方文档中文版

573
来自专栏AI科技评论

用于规划的分层有限状态控制器| IJCAI2016杰出论文详解

导读:2016国际人工智能联合会议(IJCAI2016)于7月9日至7月15日举行,今年会议聚焦于人类意识的人工智能,本文是IJCAI2016杰出论文(Dist...

3034
来自专栏牛肉圆粉不加葱

Spark SQL,DataFrame以及 Datasets 编程指南 - For 2.0

Spark SQL 是 Spark 用来处理结构化数据的一个模块。与基础的 Spark RDD API 不同,Spark SQL 提供了更多数据与要执行的计算的...

682
来自专栏AI派

TensorFlow修炼之道(3)——计算图和会话(Graph&Session)

在计算图中,节点表示计算单位,边表示计算用到和产生的数据。 例如,在TensorFlow图中,tf.matmul操作将对应于具有两个输入边(要乘以的矩阵)和一个...

2884
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

1593
来自专栏华章科技

以卖香蕉为例,从4个方面了解SQL的数据汇总

导读:面对一个新数据集时,人们往往会关心数据中的异常值、数据的分布形式、行列之间的关系等。SQL是一种专为数据计算设计的语言,其中已经内置了许多数据汇总函数,也...

613
来自专栏CSDN技术头条

使用hadoop进行大规模数据的全局排序

1. Hellow hadoop~~! Hadoop(某人儿子的一只虚拟大象的名字)是一个复杂到极致,又简单到极致的东西。 说它复杂,是因为一个hadoop...

2265
来自专栏CSDN技术头条

Weiflow:微博也有机器学习框架?

本文从开发效率(易用性)、可扩展性、执行效率三个方面,介绍了微博机器学习框架Weiflow在微博的应用和最佳实践。 在上期《基于Spark的大规模机器学习在微博...

2378

扫描关注云+社区