python 實現A_算法的示例代碼

來源：中文源碼網????瀏覽： 次????日期：2018年9月2日

【下載文檔:??python 實現A_算法的示例代碼.txt?】

(友情提示:右鍵點上行txt文檔名->目標另存為)

python 實現A*算法的示例代碼 A*作為最常用的路徑搜索算法，值得我們去深刻的研究。路徑規劃項目。先看一下維基百科給的算法解釋：http://en.wikipedia.org/wiki/A*_search_algorithm

A *是最佳優先搜索它通過在解決方案的所有可能路徑(目標)中搜索導致成本最小(行進距離最短，時間最短等)的問題來解決問題。 )，并且在這些路徑中，它首先考慮那些似乎最快速地引導到解決方案的路徑。它是根據加權圖制定的：從圖的特定節點開始，它構造從該節點開始的路徑樹，一次一步地擴展路徑，直到其一個路徑在預定目標節點處結束。

在其主循環的每次迭代中，A *需要確定將其部分路徑中的哪些擴展為一個或多個更長的路徑。它是基于成本(總重量)的估計仍然到達目標節點。具體而言，A *選擇最小化的路徑

F(N)= G(N)+ H(n)

其中n是路徑上的最后一個節點，g(n)是從起始節點到n的路徑的開銷，h(n)是一個啟發式，用于估計從n到目標的最便宜路徑的開銷。啟發式是特定于問題的。為了找到實際最短路徑的算法，啟發函數必須是可接受的，這意味著它永遠不會高估實際成本到達最近的目標節點。

維基百科給出的偽代碼：function A*(start, goal)

// The set of nodes already evaluated

closedSet := {} // The set of currently discovered nodes that are not evaluated yet.

// Initially, only the start node is known.

openSet := {start} // For each node, which node it can most efficiently be reached from.

// If a node can be reached from many nodes, cameFrom will eventually contain the

// most efficient previous step.

cameFrom := an empty map // For each node, the cost of getting from the start node to that node.

gScore := map with default value of Infinity // The cost of going from start to start is zero.

gScore[start] := 0 // For each node, the total cost of getting from the start node to the goal

// by passing by that node. That value is partly known, partly heuristic.

fScore := map with default value of Infinity // For the first node, that value is completely heuristic.

fScore[start] := heuristic_cost_estimate(start, goal) while openSet is not empty

current := the node in openSet having the lowest fScore[] value

if current = goal

return reconstruct_path(cameFrom, current) openSet.Remove(current)

closedSet.Add(current) for each neighbor of current

if neighbor in closedSet

continue // Ignore the neighbor which is already evaluated. if neighbor not in openSet // Discover a new node

openSet.Add(neighbor)

// The distance from start to a neighbor

//the "dist_between" function may vary as per the solution requirements.

tentative_gScore := gScore[current] + dist_between(current, neighbor)

if tentative_gScore >= gScore[neighbor]

continue // This is not a better path. // This path is the best until now. Record it!

cameFrom[neighbor] := current

gScore[neighbor] := tentative_gScore

fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) return failurefunction reconstruct_path(cameFrom, current)

total_path := {current}

while current in cameFrom.Keys:

current := cameFrom[current]

total_path.append(current)

return total_path下面是UDACITY課程中路徑規劃項目，結合上面的偽代碼，用python 實現A* import math

def shortest_path(M,start,goal):

sx=M.intersections[start][0]

sy=M.intersections[start][1]

gx=M.intersections[goal][0]

gy=M.intersections[goal][1]

h=math.sqrt((sx-gx)*(sx-gx)+(sy-gy)*(sy-gy))

closedSet=set()

openSet=set()

openSet.add(start)

gScore={}

gScore[start]=0

fScore={}

fScore[start]=h

cameFrom={}

sumg=0

NEW=0

BOOL=False

while len(openSet)!=0:

MAX=1000

for new in openSet:

print("new",new)

if fScore[new]MAX=fScore[new]

#print("MAX=",MAX)

NEW=new

current=NEW

print("current=",current)

if current==goal:

return reconstruct_path(cameFrom,current)

openSet.remove(current)

closedSet.add(current)

#dafult=M.roads(current)

for neighbor in M.roads[current]:

BOOL=False

print("key=",neighbor)

a={neighbor}

if len(a&closedSet)>0:

continue

print("key is not in closeSet")

if len(a&openSet)==0:

openSet.add(neighbor)

else:

BOOL=True

x= M.intersections[current][0]

y= M.intersections[current][1]

x1=M.intersections[neighbor][0]

y1=M.intersections[neighbor][1]

g=math.sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1))

h=math.sqrt((x1-gx)*(x1-gx)+(y1-gy)*(y1-gy))

new_gScore=gScore[current]+g

if BOOL==True:

if new_gScore>=gScore[neighbor]:

continue

print("new_gScore",new_gScore)

cameFrom[neighbor]=current

gScore[neighbor]=new_gScore

fScore[neighbor] = new_gScore+h

print("fScore",neighbor,"is",new_gScore+h)

print("fScore=",new_gScore+h)

print("__________++--------------++_________")

def reconstruct_path(cameFrom,current):

print("已到達lllll")

total_path=[]

total_path.append(current)

for key,value in cameFrom.items():

print("key",key,":","value",value)

while current in cameFrom.keys():

current=cameFrom[current]

total_path.append(current)

total_path=list(reversed(total_path))

return total_path

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持中文源碼網。

親,試試微信掃碼分享本頁!?*^_^*

總結

以上是生活随笔為你收集整理的python算法实现源码_python 实现A_算法的示例代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。