ホームページ > バックエンド開発 > Python チュートリアル > Python で A* アルゴリズムを実装する詳細な手順を学習します。

Python で A* アルゴリズムを実装する詳細な手順を学習します。

PHPz
リリース: 2024-01-23 22:51:05
転載
715 人が閲覧しました

以此加权图为例,用Python实现A*算法。加权图中的节点用粉红色圆圈表示,并且给出了沿节点的路径的权重。节点上方的数字代表节点的启发式值。

Python で A* アルゴリズムを実装する詳細な手順を学習します。

首先为算法创建类。一个用于存储与起始节点的距离,另一个用于存储父节点。并将它们初始化为0,以及起始节点。

def aStarAlgo(start_node,stop_node):
open_set=set(start_node)
closed_set=set()
g={}
parents={}
g[start_node]=0
parents[start_node]=start_node
ログイン後にコピー

找到具有最低f(n)值的相邻节点,针对到达目标节点的条件进行编码。如果不是这种情况,则将当前节点放入打开列表中,并设置其父节点。

While len(open_set)>0:
n=None
for v in open_set:
if n==None or g[v]+heuristic(v)<g[n]+heuristic(n):
n=v
if n==stop_node or Graph_nodes[n]==None:
pass
else:
for(m,weight)in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m]=n
g[m]=g[n]+weight
ログイン後にコピー

如果相邻的g值低于当前节点并且在封闭列表中,则将其替换为这个新节点作为父节点。

else:
if g[m]>g[n]+weight:
g[m]=g[n]+weight
parents[m]=n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
ログイン後にコピー

如果当前g低于前一个g,并且其相邻在open list中,则将其替换为较低的g值,并将相邻的parent更改为当前节点。

如果不在两个列表中,则将其添加到打开列表并设置其g值。

if n==None:
print(&#x27;Path does not exist!&#x27;)
return None
if n==stop_node:
path=[]
while parents[n]!=n:
path.append(n)
n=parents[n]
path.append(start_node)
path.reverse()
print(&#x27;Path found:{}&#x27;.format(path))
return path
open_set.remove(n)
closed_set.add(n)
print(&#x27;Path does not exist!&#x27;)
return None
ログイン後にコピー

现在,定义一个函数来返回相邻节点及其距离。

def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
ログイン後にコピー

此外,创建一个函数来检查启发式值。

def heuristic(n):
H_dist={
&#x27;A&#x27;:11,
&#x27;B&#x27;:6,
&#x27;C&#x27;:99,
&#x27;D&#x27;:1,
&#x27;E&#x27;:7,
&#x27;G&#x27;:0,
}
return H_dist[n]
ログイン後にコピー

描述一下图表并调用A*函数。

Graph_nodes={
&#x27;A&#x27;:[(&#x27;B&#x27;,2),(&#x27;E&#x27;,3)],
&#x27;B&#x27;:[(&#x27;C&#x27;,1),(&#x27;G&#x27;,9)],
&#x27;C&#x27;:Node,
&#x27;E&#x27;:[(&#x27;D&#x27;,6)],
&#x27;D&#x27;:[(&#x27;G&#x27;,1)],
}
aStarAlgo(&#x27;A&#x27;,&#x27;G&#x27;)
ログイン後にコピー

算法遍历图,找到代价最小的路径。

这是通过E => D => G。

以上がPython で A* アルゴリズムを実装する詳細な手順を学習します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:163.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート