1

dijkstras.pyでは、グラフ G を指定してダイクストラを実行するコードがいくつかあるとします。

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

でも、まだ走ったことがないので、どうなるかわかりません。もっとコーディングを始める前に、これを誰かに跳ね返したかっただけです。

4

1 に答える 1

0

アルファが示唆したように、正しい解決策は を使用することcost + cost2 + h(v2)です。

于 2013-02-22T19:14:20.750 に答える