所以，假设我有一些代码在dijkstras.py给定图形 G 的情况下执行 dijkstras。
def shortest_path(G, start, end):
def flatten(L): # Flatten linked list of form [0,[1,[2,[]]]]
while len(L) > 0:
yield L[0]
L = L[1]
q = [(0, start, ())] # Heap of (cost, path_head, path_rest).
visited = set() # Visited vertices.
while True:
(cost, v1, path) = heapq.heappop(q)
if v1 not in visited:
visited.add(v1)
if v1 == end:
return [('cost', cost)] + [('path', list(flatten(path))[::-1] + [v1])]
path = (v1, path)
for (v2, cost2) in G[v1].iteritems():
if v2 not in visited:
heapq.heappush(q, (cost + cost2, v2, path))
G 是这样的：
G = {
's': {'u':10, 'x':5},
'u':{'v':1, 'x':2},
'v':{'y':4},
'x':{'u':3, 'v':9, 'y':2},
'y': {'s':7, 'v':6}
}
我们将如何转换现有的算法，shortest_path(G, start, end)以最少的修改来利用 a*。
我在想的是：
def shortest_path(G, start, end, h): #where h is the heuristic function
def flatten(L): # Flatten linked list of form [0,[1,[2,[]]]]
while len(L) > 0:
yield L[0]
L = L[1]
q = [(0, start, ())] # Heap of (cost, path_head, path_rest).
visited = set() # Visited vertices.
while True:
(cost, v1, path) = heapq.heappop(q)
if v1 not in visited:
visited.add(v1)
if v1 == end:
return [('cost', cost)] + [('path', list(flatten(path))[::-1] + [v1])]
path = (v1, path)
for (v2, cost2) in G[v1].iteritems():
if v2 not in visited:
heapq.heappush(q, (cost + cost2 + h(v2), v2, path)) #modification here
但我什至还没有运行它，所以我不知道它会如何运行。在我开始编写更多代码之前，我只是想从某人那里得到这个。