图论经典A-Star(A*) Algorithm最短路径，networkx，Python（1）

A-Star Algorithm，即为A*（A星）算法，图的最短路径。

（1）A-Star(A*)算法需要事先知道起点和终点才能求出最优路径。A-Star算法大量运用在游戏编程中的人物角色选路AI程序中。现代游戏编程，涉及到路径选择和规划的，大部分基于A*算法实现。然而，如果算法启动前不知道终点（起点已知），那么无法使用A-Star算法。

（2）A*算法核心是启发函数 F = G+H，启发函数驱动A*算法。假设当前节点是V，G是节点V到出发点的距离，H是节点V到终点的距离。A*算法应用在空间平面的距离计算，通常由两种：欧几里德解析几何距离，曼哈顿距离。用的较多的是曼哈顿距离。

（3）A*算法工作过程：出发点start和终点goal已经知道，假设现在选定了某个节点V，对于某个节点V，V到出发点start的曼哈顿距离算出为G，V到终点goal的曼哈顿距离为H，则节点V的启发函数值F=G+H。

A*需要维护两个列表：open_list和close_list，当选定节点V后，把所有与V邻接的节点放入open_list中，把这些新加入的点的父记为V，然后把节点V放入到close_list。此时查找open_list中所有节点的具有最小F值的节点 V' （此处是 V' 撇，不是 V，表示V选好后，进行第二轮选点的那个节点），V' 选出来后，再次把 V' 所有相邻的节点加入到open_list中，同时把 V' 从open_list中删掉，并把V' 加入到close_list中去。

在查找 V' 的邻接节点步骤中，如果邻接的节点已经在close_list中，则忽略，同时，如果 V' 的某一个邻接点N已经在open_list中，则比较当前节点 V' 到N的距离

（4）最终路径的产生：从终点开始。逆向的从终点开始，找出终点保存的父节点指向谁，然后逆向，然后再找到终点的父节点的父节点......，一路逆行查找，直到查找到父节点为出发点为止，即为A*选出来的路径。

现在，我用python简单写了一个A-Star算法的实现，networkx主要用来绘制图和装配与节点相关的内容：

import random
import timeimport networkx as nx
import matplotlib.pyplot as pltG_DIS = 'g_dis'
H_DIS = 'h-dis'
F = 'F'
WALKABLE = 'walkable'
PARENT = 'parent'def my_graph():M = 7N = 9G = nx.grid_2d_graph(m=M, n=N)pos = nx.spring_layout(G, iterations=100)nx.draw_networkx(G, pos=pos,# labels=labels, #labels = dict(((i, j), 'Phil') for i, j in G.nodes())font_size=8,font_color='white',node_color='green',node_size=500,width=1)START = (2, 1)GOAL = (M - 1 - 1, N - 1 - 1)obstacle = 20  # 障碍物（断点、不可达点）数量road_closed_nodes = dummy_nodes(G)  # obstacle_nodes(G, START, GOAL, obstacle, M, N)nx.draw_networkx_nodes(G, pos,nodelist=road_closed_nodes,node_size=500,node_color="red",node_shape="x",# alpha=0.3,label='x')print('G.nodes(data=True)', G.nodes(data=True))print('G.edges(data=True)', G.edges(data=True))path = a_star(G, START, GOAL)print('路线', path)nx.draw_networkx_nodes(G, pos,nodelist=path,node_size=400,node_color="red",node_shape='o',# alpha=0.3,# label='NO')# 逆向的从父节点找出A*选的路。path_edges = []for i in range(len(path)):if (i + 1) == len(path):breakpath_edges.append((path[i], path[i + 1]))print('path_edges', path_edges)# 把path着色加粗重新描边nx.draw_networkx_edges(G, pos,edgelist=path_edges,width=8,alpha=0.5,edge_color="r")plt.axis('off')plt.show()# 障碍物点
def obstacle_nodes(G, START, GOAL, obstacle, M, N):road_closed_nodes = []for i in range(obstacle):time.sleep(0.01)n = (random.randint(0, M - 1), random.randint(0, N - 1))if n == START or n == GOAL:continueif n in road_closed_nodes:continueG.nodes[n][WALKABLE] = Falseroad_closed_nodes.append(n)return road_closed_nodesdef dummy_nodes(G):fun_nodes = []n1 = (1, 3)G.nodes[n1][WALKABLE] = Falsefun_nodes.append(n1)n2 = (1, 4)G.nodes[n2][WALKABLE] = Falsefun_nodes.append(n2)n3 = (1, 5)G.nodes[n3][WALKABLE] = Falsefun_nodes.append(n3)n4 = (1, 6)G.nodes[n4][WALKABLE] = Falsefun_nodes.append(n4)n5 = (2, 6)G.nodes[n5][WALKABLE] = Falsefun_nodes.append(n5)n6 = (3, 6)G.nodes[n6][WALKABLE] = Falsefun_nodes.append(n6)n7 = (4, 6)G.nodes[n7][WALKABLE] = Falsefun_nodes.append(n7)n8 = (5, 6)G.nodes[n8][WALKABLE] = Falsefun_nodes.append(n8)n9 = (5, 5)G.nodes[n9][WALKABLE] = Falsefun_nodes.append(n9)n10 = (5, 4)G.nodes[n10][WALKABLE] = Falsefun_nodes.append(n10)n11 = (5, 3)G.nodes[n11][WALKABLE] = Falsefun_nodes.append(n11)return fun_nodes# A*寻路
def a_star(G, START, GOAL):open_list = []close_list = []vertex = STARTloop_flag = Truewhile loop_flag:print('-----')if vertex == GOAL:print('到达', vertex)close_list.append(vertex)# loop_flag = Falsebreakprint('选中', vertex)close_list.append(vertex)for node in nx.neighbors(G, vertex):# 如果n在close_list或者不可行，忽略try:walkable = G.nodes[node][WALKABLE]except:walkable = Trueprint('walkable', walkable)if (not walkable) or (node in close_list):continueprint('遍历', node)if node in open_list:print(node, '在open_list')node_g_dis = G.nodes[node][G_DIS]vertex_g_dis = G.nodes[vertex][G_DIS]sum_g_dis = manhattan(vertex, node) + vertex_g_dis# 更新权值if sum_g_dis < node_g_dis:G.nodes[node][PARENT] = vertexG.nodes[node][G_DIS] = sum_g_disG.nodes[node][F] = sum_g_dis + manhattan(GOAL, node)else:G.nodes[node][G_DIS] = manhattan(node, START)h_dis = manhattan(node, GOAL)G.nodes[node][H_DIS] = h_dissum_f_dis = G.nodes[node][G_DIS] + h_disG.nodes[node][F] = sum_f_disG.nodes[node][PARENT] = vertexopen_list.append(node)# print('G.nodes(data=True)', G.nodes(data=True))print('open_list', open_list)f_list = []for n in open_list:f_list.insert(0, (n, G.nodes[n]))print('f_list', f_list)min_f = min(f_list, key=lambda x: x[1][F])print('min_f', min_f)point = min_f[0]print('F最小点', point)open_list.remove(min_f[0])print('close_list', close_list)print('open_list', open_list)vertex = pointt = GOALpath = [t]is_find = Falsewhile not is_find:for n in G.nodes(data=True):if n[0] == t:parent = n[1][PARENT]path.append(parent)if parent == START:is_find = Truebreakt = parentlist.reverse(path)return path# 计算曼哈顿距离
def manhattan(u, v):dis = abs(u[0] - v[0]) + abs(u[1] - v[1])return disif __name__ == '__main__':my_graph()

运行代码，跑几轮，看看程序选的路线如何。出发点是START，目的地是GOAL。图中标记红色叉（X）的节点是故意随机生成的断点、障碍物、陷阱，特意用来挑战A-Star算法智商 :-)，图中红‘X’表明这个节点不可通行，不能用于选路。障碍物点数量越多，选路难度越大，本例是20个（obstacle = 20）障碍物点。注意本例的随机障碍物点生成规则，程序生成的随机障碍物点如果刚好是起点或终点，则忽略；如果生成的随机障碍物点刚好已经在之前生成过，则同意忽略。这意味着，可能每次生成的随机障碍物点zong's不等于20，而是<=20。

最终的红色圆点即为出发点到终点的路线节点，把节点用淡红色粗线连起来，即为A*算法选出来的路线。

在本例出发点是(1,1)，终点是(5,7)。出发点和终点和程序代码开始的M，N值相关。

下面是运行了几轮程序，A*选择的路线（ 起点(1,1) -> 终点(5,7) ，红色点连成的淡红色（red，alpha=0.5）粗线为形成的路线）截图：

程序当前存在一些问题，对障碍物点没做特殊处理，只是不让障碍物刚好是起点和终点。如果随机生成的障碍物点把出发点和终点隔绝死，或者中间某处路隔绝断，程序就就选不到路运行错误。后续还需要对这个程序改进和优化。

下面来些有趣的内容：给A-Star算法挖坑，看它会不会跳进去

现在，针对A*算法的特点，我造一堵特殊的墙，一个凹形的墙。看看A星算法是否会跳进这堵墙形成的坑。实验的做法是修改起点和终点，把起点修改为(3,1)，终点修改为(3,7)。同时，不再随机生成障碍点，而是在(3,1)和(3,7)之间特意挑选一些位置、写死一批（9个点）不可通行的节点（仍然用X标记），这批不可通行的节点形成一个连续的凹形阻挡面，正面对(3,1)节点，程序运行几轮的截图：

 A-Star聪明的绕过了这个大坑（凹形墙），顺利达到(3,7)点。

（未完待续...）

图论BFS(Breath First Search)Algorithm广度优先搜索遍历空间平面网格图路径选择，networkx，Python_zhangphil的博客-CSDN博客import randomimport networkx as nximport matplotlib.pyplot as pltWALKABLE = 'walkable'PARENT = 'parent'VISITED = 'visited'def my_graph(): M = 7 N = 9 G = nx.grid_2d_graph(m=M, n=N) pos = nx.spring_layout(G, iterations=100) ...https://blog.csdn.net/zhangphil/article/details/121267357

图论DFS(Depth First Search)Algorithm深度优先搜索遍历空间平面图选择路径，networkx，Python_图论 dfs_zhangphil的博客-CSDN博客import randomimport networkx as nximport matplotlib.pyplot as pltWALKABLE = 'walkable'PARENT = 'parent'VISITED = 'visited'def my_graph(): M = 7 N = 9 G = nx.grid_2d_graph(m=M, n=N) pos = nx.spring_layout(G, iterations=100) ...https://blog.csdn.net/zhangphil/article/details/121269870

https://zhangphil.blog.csdn.net/article/details/121171499https://zhangphil.blog.csdn.net/article/details/121171499

https://zhangphil.blog.csdn.net/article/details/121208538https://zhangphil.blog.csdn.net/article/details/121208538