V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):4.5,('D','F'):8,('D','H'):4,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})
INFINITY=10000000
def find_neighbours(node):
neighbours=[]
for item in E:
if node==item[0][0]:
neighbours.append(item[1][0])
return neighbours
def reconstruct_path(cameFrom, current):
total_path = [current]
while current in cameFrom:
current = cameFrom[current]
total_path.append(current)
return total_path
#
def Astar(start, goal):
current = start
fScore={}
gScore={}
# The set of currently discovered nodes still to be evaluated.
openSet = set()
# The set of nodes already evaluated.
closedSet = set()
# Initially, only the start node is known.
openSet.add(current)
# 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 ={}#the empty map
# For each node, the cost of getting from the start node to that node.
for node in V:
gScore[node] = INFINITY #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.
for node in V:
fScore[node] = INFINITY #map with default value of Infinity
# For the first node, that value is completely heuristic.
fScore[start] = V[start]#heuristic_cost_estimate(start, goal)
def heuristic_cost_estimate(node, goal):
return E[cameFrom[node],node]+V[node]
count=0
while openSet:
count+=1
if count>10:
break
print openSet
minn=INFINITY
for node in openSet:
if fScore[node]<minn:
current=node
if current==None:
current=start
#current = node in openSet having the lowest fScore[] value)
if current == goal:
return reconstruct_path(cameFrom, goal)
openSet.remove(current)
#Add it to the closed set
closedSet.add(current)
for neighbor in find_neighbours(current):
if neighbor in closedSet:
continue # Ignore the neighbor which is already evaluated.
# The distance from start to goal passing through current and the neighbor.
tentative_gScore = gScore[current] + E[(current, neighbor)]
if neighbor not in openSet: # Discover a new node
openSet.add(neighbor)
elif 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 "failure"
print Astar('A','K')
