A* 算法及伪代码

超、凢脫俗 2021-12-14 09:27 255阅读 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 条评论，255人围观）

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

相关阅读

相关伪彩色处理及算法

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

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

相关强化学习算法伪代码

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

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

相关【算法】just-copy（伪代码改写，归并排序）

根据伪代码写程序，实现的功能为归并排序，并输出res（res可能是用来记录元素交换了多少次，本人不是很确定，当然这并不影响做出这一题） ![在这里插入图片描述][dab27

我就是我/ 2022年08月28日 06:49/ 0 赞/ 101 阅读

相关《算法导论》第七章-快速排序（伪代码）

快速排序伪代码： QuickSort(A,p,r) if p<r q = Partition(A,p,r) //确定划分位置 QuickSort(A,p,q

旧城等待，/ 2022年08月13日 08:28/ 0 赞/ 275 阅读

相关《算法导论》第六章-优先级队列（伪代码）

优先级队列伪代码： //返回优先级队列的最大值 Heap\_Max(A) return A\[1\] end 运行时间为Θ(1) //去

蔚落/ 2022年08月13日 07:58/ 0 赞/ 137 阅读

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

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

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

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

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

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

相关 A*算法—java代码

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

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

相关最大团问题及伪代码

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

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

相关 A* 算法及伪代码

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

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