算法学习之A算法（python实现）_pythona算法输出open和close表

作者：你好赵伟 | 2024-05-13 00:05:29

踩

pythona*算法输出open和close表

A*算法学习

A*算法伪代码
步骤一：
创建地图。
解释：A*算法中的地图多以栅格图法构建，在代码中可以用数组或者说列表来实现，一般采用二维数组索引表示每个节点的坐标，索引内容 0代表地图可通过，1代表地图中的障碍物。
步骤二：
设定起始点，以及目标点即终点。将起始点添加进开放列表中（openlist），此过程可以视为初始化。
解释： openlist是一个存放待检测节点的列表，列表中是有一个或者多个待检测节点，待检测节点需要检测计算的信息有：
1、从起始点到待检测的当前节点的移动代价（成本），通常用G表示
2、从当前节点到终点的估算成本，通常用H表示
3、总成本，通常用F表示，F(总成本)= G(移动成本)+H(估算成本) 。
步骤三：
如果openlist不为空，说明还有待检测节点，则循环进行以下步骤：
1）找出openlist表中代价最小的节点，也就是F最小，将此节点作为当前节点。
解释：当前节点就是closelist列表中的一个元素， closelist列表是一组已经检测过的节点，每次检测都是以当前节点为中心，检测周围的8个节点（检测8个节点的话，通常成为8邻域搜索法，也有24邻域搜索法）用比较官方的语言表达的话就是，将已经检测过的当前节点，添加进closelist中，同时将当前节点的8个邻域坐标添加进openlist中。此时要注意，如果当前节点的邻域某个元素是终点，是障碍，或者与之前第一个当前节点的邻域有重复，那么进行下一步判断。还要注意步骤二中只添加了一个起始点在openlist中，那么无论怎么计算，起始点的代价都将视为最小，也就是说第一轮循环的时候，起始点作为当前点。
2）判断当前节点的邻域状态：
a.邻域是地图中的障碍物，则不进行操作（添加进openlist中的才进行下一步操作）
b.邻域是终点，跳出循环，将当前节点作为此邻域的父节点
解释：父节点概念在下面，父节点的作用是为了从终点开始找到一条反向到起点的路径
c.邻域是closelist中的元素，不进行操作
d.邻域不是openlist中的元素，则将当前节点作为此邻域的父节点，同时将这个邻域添加进openlist中。
解释：邻域不是openlist中的元素，即openlist表中没有相同的元素，但这个邻域元素却挨着当前节点，那么说明这个邻域有成为下一个路径的潜力，即当前节点下一步可能就走到了这个邻域点。所以这里引申出来父节点的概念，因为当前节点下一步可能就走到了这个邻域点，所以将当前点作为这个邻域的父节点。同时，这个邻域到底有没有可能成为下一个路径节点呢，因此需要将这个邻域添加进openlist中检测它的F代价。
e.邻域是openlist中的元素，此时要进行再次判断。若目前邻域到达终点的代价小于openlist中已存在的代价，则将openlist中已存在的邻域删除，添加成目前邻域，同时将当前节点作为这个目前邻域的父节点。若不小于，则不进行操作。
解释：这里需要仔细思考，定义当前节点的邻域为E，那么要知道openlist中是有这个邻域的，openlist中的这个元素是谁的邻域呢？是上一个作为当前节点的邻域，定义openlist中有的邻域为E_Last(上一次的值)，E和E_Last都有自己通往终点的代价，原因是他们的移动代价G是不一样的。因此就可以通过比较F来判断谁是最优路径。
f.通过以上判断会得出一个新的openlist表，循环步骤三。
步骤四：
完成以上循环后，如果已经找到路径，则从目标终点开始，依次查找每个节点的父节点，直到找到起始点，这样就形成了一条路径。
解释：在代码测试过程中发现，closelist列表中存放的每一个元素就是路径，但是在理论上是不对的，待验证。
代码工程如下：

# -*- coding: UTF-8 -*-
'''*******************************
@ 开发人员：Mr.Zs
@ 开发时间：2020/5/1710:34
@ 开发环境：PyCharm
@ 项目名称：A-star算法->my_Astar_test.py
******************************'''
print(r'''**********算法伪代码*****************
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.完成以上循环后，如果已经找到路径，则从目标点开始，依次查找每个节点的父节点，直到找到开始点，这样就形成了一条路径。 
**********算法伪代码*****************
''')
import random
#将地图中的点抽象化成类
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other): #函数重载  #判断两个坐标  的  值 是否一样
        if((self.x == other.x )and (self.y == other.y)):
            return  True
        else:
            return False
    def __ne__(self, other):
        pass

class Map():          #首先定义地图类 创建地图
    obstacle_num = 50  # 障碍物的个数 实际障碍可能小于50
    def __init__(self,row,col):#构造方法  参数为行和列
        self.row = row
        self.col = col
        self.data = []
        self.data = [[0 for i in range(col)]for j in range(row)]   #列表推导式 创建地图的初始值为0
        # print(self.deta)
    def map_show(self):     #显示地图
        for i in range(self.row):
            for j in range(self.col):
                print(self.data[i][j],end =' ')
            print(' ')
    def obstacle(self,x,y):#在地图中设置障碍物
        self.data[x][y] = 1     #障碍用1
    def map_obstacleshow(self,user,usec):#显示带有障碍的地图
        for x in range(self.obstacle_num):  # 循环obstacle_num次  随机生成障碍
            i = random.randint(0, (user-1))
            j = random.randint(0, (usec-1))
            self.obstacle(i,j)
        # self.map_show()

    def draw(self,point):
        self.data[point.x][point.y] = "*"
class Astar:    #A*算法
    class Node:
        def __init__(self,point,end_point,g):   #节点坐标
            '''
            :当前节点 current_point:#节点信息  包括坐标 父节点 移动代价g 估算代价h 总代价f
            :终点 end_point:
            :g  初始代价
            '''
            self.point = point  #当前位置
            self.end_point = end_point          #终点
            self.father = None      #父节点
            self.g = g              #g 为从起点到当前点的移动代价
            self.h = (abs(end_point.x - point.x) + abs(end_point.y - point.y)) * 10  # 计算h值 #曼哈顿算法算出当前点到终点的估算代价
            self.f = self.g + self.h  #计算总代价
        def near_Node(self,ur,ul):  #附近节点
            '''
            :左右移动 ur:
            :上下移动 ul:
            :返回值   return: 附近节点信息 继承Node 的信息
            '''
            nearpoint = Point(self.point.x+ur,self.point.y+ul)
            if abs(ur)==1 and abs(ul) == 1 :
                self.g = 5         #对角线 移动代价 为14
            else:                   #横着  或者 竖着走  代价为10
                self.g = 10

            nearnode = Astar.Node(nearpoint,self.end_point,self.g) #计算临近节点
            return nearnode  #返回临近节点信息
    def __init__(self,start_point,end_point,map):
        '''
        :起始坐标 start_point:
        :终点 end_point:
        :地图信息 map:
        '''
        self.start_point = start_point  #起点
        self.end_point = end_point  #终点
        self.current = 0        #当前节点
        self.map = map          #地图
        self.openlist = []      #打开节点  待测试的节点
        self.closelist = []     #已经测试过的节点
        self.path = []          #路径  存储每次选择的路径信息
    def select_node(self):  #选择一个代价最小的节点作为当前点
        '''
        在openlist中选择代价最小的节点  存放进closelist中
        :return:当前节点信息
        '''
        f_min = 1000   #初始设置  代价为1000
        node_temp = 0  #缓存节点
        for each in self.openlist:      #在openlist 中遍历 找出最小的代价节点
            if each.f < f_min:
                f_min = each.f
                node_temp = each
        self.path.append(node_temp)         #路径信息中存入这个路径
        self.openlist.remove(node_temp)     #将节点从待测试节点中删除
        self.closelist.append(node_temp)    #将节点加入到closelist中 表示已测试过
        return node_temp    #返回当前选择的节点   下一步开始寻找附近节点
    def isin_openlist(self,node):
        '''
        判断节点是否存在于openlist中 存在返回openlist中的原来的节点信息   不存在返回0
        :节点 node:
        :return:存在返回openlist中的原来的节点信息   不存在0
        '''
        for opennode in self.openlist:
            if opennode.point == node.point:
                return opennode
        return 0
    def isin_closelist(self,node):
        '''
        判断节点是否存在于closelist中 存在返回1   不存在返回0
        :节点 node:
        :return:存在返回1   不存在0
        '''
        for closenode in self.closelist:
            if closenode.point == node.point:
                return 1
        return 0
    def is_obstacle(self,node):#判断是否是障碍物
        if self.map.data[node.point.x][node.point.y]==1 :
            return  1
        return  0
    def search_nextnode(self,node):

        ud = 1
        rl = 0

        node_temp = node.near_Node(ud,rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = -1
        rl = 0
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = 0
        rl = 1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = 0
        rl = -1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = 1
        rl = 1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = 1
        rl = -1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = -1
        rl = 1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        ud = -1
        rl = -1
        node_temp = node.near_Node(ud, rl)  # 在调用另一个类的方法时（不论是子类还是在类外定义的类），都要进行实例化才能调用函数
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.openlist.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.openlist.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.openlist.append(node_temp)

        return 0

start_point = Point(1,0)
end_point = Point(12,13)


userow = 15     #实际使用的行
usecol = 15     #实际使用的列
mapshow = Map(userow,usecol)        #地图 实例化
# mapshow.map_show()#显示地图
# print('__________________________')
mapshow.map_obstacleshow(userow,usecol)
mapshow.draw(start_point)
mapshow.draw(end_point)
# mapshow.map_show()#显示地图
#初始化设置
astar = Astar(start_point,end_point,mapshow)  #实例化 A*算法
start_node = astar.Node(start_point,end_point,0)  #获取到当前节点  也就是起始点的所有信息
astar.openlist.append(start_node)           #将起始点添加进openlist中

flag = 0
while flag!=1:
    astar.current = astar.select_node()#从openlist中选取一个代价最小的node节点 作为当前节点
    flag=astar.search_nextnode(astar.current)#对选中的当前node进行周边探索
#画出地图路径
for node_path in astar.closelist:
    mapshow.draw(node_path.point)
mapshow.map_show()#显示地图


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/561077

算法学习之A*算法（python实现）_pythona*算法输出open和close表

A*算法学习

算法学习之A算法（python实现）_pythona算法输出open和close表