python 实现A*算法的示例代码
A*作为最常用的路径搜索算法，值得我们去深刻的研究。路径规划项目。先看一下维基百科给的算法解释：https://en.wikipedia.org/wiki/A*_search_algorithm
A*是最佳优先搜索它通过在解决方案的所有可能路径（目标）中搜索导致成本最小（行进距离最短，时间最短等）的问题来解决问题。），并且在这些路径中，它首先考虑那些似乎最快速地引导到解决方案的路径。它是根据加权图制定的：从图的特定节点开始，它构造从该节点开始的路径树，一次一步地扩展路径，直到其一个路径在预定目标节点处结束。
在其主循环的每次迭代中，A*需要确定将其部分路径中的哪些扩展为一个或多个更长的路径。它是基于成本（总重量）的估计仍然到达目标节点。具体而言，A*选择最小化的路径
F（N）=G（N）+H（n）
其中n是路径上的最后一个节点，g（n）是从起始节点到n的路径的开销，h（n）是一个启发式，用于估计从n到目标的最便宜路径的开销。启发式是特定于问题的。为了找到实际最短路径的算法，启发函数必须是可接受的，这意味着它永远不会高估实际成本到达最近的目标节点。
维基百科给出的伪代码：
functionA*(start,goal)
//Thesetofnodesalreadyevaluated
closedSet:={}
//Thesetofcurrentlydiscoverednodesthatarenotevaluatedyet.
//Initially,onlythestartnodeisknown.
openSet:={start}
//Foreachnode,whichnodeitcanmostefficientlybereachedfrom.
//Ifanodecanbereachedfrommanynodes,cameFromwilleventuallycontainthe
//mostefficientpreviousstep.
cameFrom:=anemptymap
//Foreachnode,thecostofgettingfromthestartnodetothatnode.
gScore:=mapwithdefaultvalueofInfinity
//Thecostofgoingfromstarttostartiszero.
gScore[start]:=0
//Foreachnode,thetotalcostofgettingfromthestartnodetothegoal
//bypassingbythatnode.Thatvalueispartlyknown,partlyheuristic.
fScore:=mapwithdefaultvalueofInfinity
//Forthefirstnode,thatvalueiscompletelyheuristic.
fScore[start]:=heuristic_cost_estimate(start,goal)
whileopenSetisnotempty
current:=thenodeinopenSethavingthelowestfScore[]value
ifcurrent=goal
returnreconstruct_path(cameFrom,current)
openSet.Remove(current)
closedSet.Add(current)
foreachneighborofcurrent
ifneighborinclosedSet
continue//Ignoretheneighborwhichisalreadyevaluated.
ifneighbornotinopenSet//Discoveranewnode
openSet.Add(neighbor)
//Thedistancefromstarttoaneighbor
//the"dist_between"functionmayvaryasperthesolutionrequirements.
tentative_gScore:=gScore[current]+dist_between(current,neighbor)
iftentative_gScore>=gScore[neighbor]
continue//Thisisnotabetterpath.
//Thispathisthebestuntilnow.Recordit!
cameFrom[neighbor]:=current
gScore[neighbor]:=tentative_gScore
fScore[neighbor]:=gScore[neighbor]+heuristic_cost_estimate(neighbor,goal)
returnfailure
functionreconstruct_path(cameFrom,current)
total_path:={current}
whilecurrentincameFrom.Keys:
current:=cameFrom[current]
total_path.append(current)
returntotal_path
下面是UDACITY课程中路径规划项目，结合上面的伪代码，用python实现A*
importmath
defshortest_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
whilelen(openSet)!=0:
MAX=1000
fornewinopenSet:
print("new",new)
iffScore[new]=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("__________++--------------++_________")
defreconstruct_path(cameFrom,current):
print("已到达lllll")
total_path=[]
total_path.append(current)
forkey,valueincameFrom.items():
print("key",key,":","value",value)
whilecurrentincameFrom.keys():
current=cameFrom[current]
total_path.append(current)
total_path=list(reversed(total_path))
returntotal_path
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。