A* 算法及伪代码

超、凢脫俗 2021-12-14 09:27 312阅读 0赞

Q:

1. 手工写出 A\* 算法找到最短路的过程

2. 写出算法伪代码

A:

**1. A\*****算法过程：**

1.首先把起始位置点加入到一个称为“open List”的列表，在寻路的过程中，目前，我们可以认为open List这个列表会存放许多待测试的点，这些点是通往目标点的关键，以后会逐渐往里面添加更多的测试点，同时，为了效率考虑，通常这个列表是个已经排序的列表。

2.如果open List列表不为空，则重复以下工作：

（1）找出open List中通往目标点代价最小的点作为当前点；

（2）把当前点放入一个称为close List的列表；

（3）对当前点周围的4个点每个进行处理（这里是限制了斜向的移动），如果该点是可以通过并且该点不在close List列表中，则处理如下；

4）如果该点正好是目标点，则把当前点作为该点的父节点，并退出循环，设置已经找到路径标记；

（5）如果该点也不在open List中，则计算该节点到目标节点的代价，把当前点作为该点的父节点，并把该节点添加到open List中；

6）如果该点已经在open List中了，则比较该点和当前点通往目标点的代价，如果当前点的代价更小，则把当前点作为该点的父节点，同时，重新计算该点通往目标点的代价，并把open List重新排序；

3.完成以上循环后，如果已经找到路径，则从目标点开始，依次查找每个节点的父节点，直到找到开始点，这样就形成了一条路径。

**2.****算法的伪代码**

First create a data structure Node:

struct Node\{

**int** g; // the g value of the node

**int** h; // the h value of the node

**int** f; // the f value of the node

Node\*pre; // pre node of the node

\};

AStar\_Search()\{

struct Node start\_node;

start\_node.g = 0;

start\_node.h = H(start);

start\_node.f = start\_node.h;

start\_node.pre = NULL;

OPEN = \[start\_node\]; CLOSE = \[\];

**while** ( OPEN is not empty ) \{

The node with the smallest F value is obtained from the OPEN linked list,

which is called x\_node, and the corresponding node is called x;

Remove x\_node from the OPEN list;

**if** (x is the end node)\{

Return the path

according to the pre pointer of the node structure corresponding to each node;

\}

**for** (each successor node y of x)\{

struct Node y\_node;

y\_node.g = x\_node.g+w(x,y);

y\_node.h = H(y);

y\_node.f = y\_node.g+y\_node.h;

y.pre = x\_node;

**if**(y is not in the OPEN table and not in the CLOSE table)\{

Put y\_node in the OPEN table;

\}**else** **if**(y is in the OPEN table)\{

Take out the Node structure corresponding to the y node in the OPEN table,

which is called y\_open;

**if**( y\_node.f < y\_open.f) \{

y\_open.g = y\_node.g;

y\_open.h = y\_node.h;

y\_open.f = y\_node.f;

y\_open.pre = y\_node.pre;

\}

\}**else**\{

Take out the Node structure corresponding to the y node in the CLOSE table,

which is called y\_close;

**if**(y\_node.f < y\_close.f)\{

Remove y\_close from the CLOSE list

Put y\_node in the OPEN table;

\}

\}

\} //end for

Put x\_node into the CLOSE table;

\} //end while

\} // end AStar\_Search

发表评论取消回复

表情：

评论列表（有 0 条评论，312人围观）

还没有评论，来说两句吧...

相关阅读

相关伪彩色处理及算法

伪色彩（false color）是指将真实世界的中无法被肉眼观察到的色彩通过计算机或其他技术转换为可见光，从而使人们能够看到这些原本无法看到的色彩。这种技术被广泛应用于军事、医

深藏阁楼爱情的钟/ 2024年03月23日 18:04/ 0 赞/ 89 阅读

相关伪代码规范

在伪代码中，每一条指令占一行(else if 例外)，指令后不跟任何符号书写上的缩进表示程序中的分支结构；同一模块中的语句具有相同的缩进量，通常每个算法开始时都要描述它的

布满荆棘的人生/ 2023年10月02日 12:49/ 0 赞/ 5 阅读

相关伪多项式算法

如何评价一个伪随机数生成算法的优劣？谈到随机性，这大概是一个令人困惑哲学问题吧。随机行为精确地说究竟指的是什么，最好是有定量的定义。Kolmogorov曾提出一种判定随

偏执的太偏执、/ 2023年09月25日 08:51/ 0 赞/ 42 阅读

相关强化学习算法伪代码

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

ゝ一纸荒年。/ 2022年11月30日 04:09/ 0 赞/ 193 阅读

相关 A*算法附c++代码

一.什么是a\ 一种十分常用的寻路算法，它能够依据某个或某些优化准则，在空间中找到一个从起始点到目标点能避开障碍物的最优路径。二.算法以下图为例，敌人要绕过中

深藏阁楼爱情的钟/ 2022年10月11日 12:27/ 0 赞/ 23 阅读

相关《算法导论》第六章-堆排序（伪代码）

堆排序根据《算法导论》中的伪代码，改写如下，可能更好理解伪代码： //建堆,运行时间的界T(n) =O(N) BuildHeap(A) n = len

蔚落/ 2022年08月13日 07:00/ 0 赞/ 404 阅读

相关伪异步I/O编程及代码实现

伪异步I/O编程为了改进这种一连接一线程的模型，我们可以使用线程池来管理这些线程（需要了解更多请参考前面提供的文章），实现1个或多个线程处理N个客户端的模型（但

桃扇骨/ 2022年06月08日 09:47/ 0 赞/ 232 阅读

相关 A*算法—java代码

[https://blog.csdn.net/ruils/article/details/40780657][https_blog.csdn.net_ruils_article

比眉伴天荒/ 2022年05月14日 08:48/ 0 赞/ 233 阅读

相关最大团问题及伪代码

给定无向图 G=(V, E)，其中 V 是非空集合，称为顶点集； E 是 V 中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )

忘是亡心i/ 2021年12月16日 08:15/ 0 赞/ 393 阅读

相关 A* 算法及伪代码

Q: 1. 手工写出 A\ 算法找到最短路的过程 2. 写出算法伪代码 A: 1. A\算法过程： 1.首先把起始位置点加入到一个称为“open List”的列表，在

超、凢脫俗/ 2021年12月14日 09:27/ 0 赞/ 313 阅读