用負節點和循環節點遍歷一個圖的最佳算法是什麼

Question

我有一個真正難以解決的問題，我只是想知道什麼算法可以用來找到最快的路線。無向圖包含正面和負面調整，這些調整會影響導航迷宮的機器人或事物。我遇到的問題是包含可以是+或 - 的循環的迷宮。一個示例可能有助於： -

1. 節點A給出10點到對象

2. 節點B，從所述對象

3. 節點C給出20點到對象

需要15

route =「」

起始節點是A，endin克節點是C

給出的圖形的結構： -

a(+10)-----b(-15)-----c+20 

node() means the node loops to itself - and + are the adjustments 

節點沒有環是C + 20，所以節點c具有20的積極的調整，但是沒有循環

如果機器人或物體具有在它的資源10分，則最佳路徑將是： -

a > b > c the object would have 25 points when it arrives at c 

路線= 「A，b，C」

這很容易實現，接下來的挑戰是知道如何回溯到一個好的節點，讓我們假設在每個節點，你可以找到它的任何鄰居的節點和他們的調整水平。這裏是下面的例子： -

如果機器人開始只有5分的話，最好的路徑是

a > a > b > c the bot would have 25 points when arriving at c 

路徑= 「A，A，B，C」

這是一個非常簡單的圖形，但是當你有更多的節點時，機器人很難知道是在一個好節點上循環還是從一個好節點跳到另一個好節點，同時跟蹤可能的路由。

這樣的路線將是回溯隊列。

較硬的示例將導致大量的來回

機器人具有10個點

a(+10)-----b(-5)-----c-30 

A> B> A> B> A> B> A> B> A> B > c剩下5分。

另一種方式的機器人可以做到這一點是： -

A> A> A> B> C

這是一種更有效的方式，但如何赫克你可以設定這部分是我的問題。

沒有人知道解決這個問題的好算法，我已經看過Bellman-fords和Dijkstra，但是這些只是給出了一個簡單的路徑，而不是一個循環的路徑。

它可以以某種方式或某種形式的啓發式遞歸？

---

指你的比喻： -

我覺得我得到你的意思，有點假的會更清楚，到目前爲止路線（）

q.add(v) 
best=v 
hash visited(v,true) 

while(q is not empty) 
    q.remove(v) 
    for each u of v in G 

     if u not visited before 
      visited(u,true) 
      best=u=>v.dist 
     else 
      best=v=>u.dist 

Answer 1

這是一個直截了當的動態規劃問題。

假設對於給定長度的路徑，對於每個節點，您想要知道在該節點處結束的最佳成本以及該路由來自哪裏。 （該長度的數據可以存儲在散列中，路由在鏈表中）。

假設我們有n個步驟的數據。然後，對於n + 1，我們從一個乾淨的石板開始，然後將每個回答都拿到第n個，將它向前移動一個節點，如果我們落在節點上，我們沒有數據，否則，比找到的最好，然後我們用改進的分數更新該節點的數據，然後添加路由（只是將該節點鏈接回上一個鏈接列表）。

一旦我們獲得了所需的步數，就可以找到具有最佳現有路線的節點，然後將您的得分和路線作爲鏈接列表。

========

這是實現該算法實際代碼：

class Graph: 
    def __init__(self, nodes=[]): 
     self.nodes = {} 
     for node in nodes: 
      self.insert(node) 

    def insert(self, node): 
     self.nodes[ node.name ] = node 

    def connect(self, name1, name2): 
     node1 = self.nodes[ name1 ] 
     node2 = self.nodes[ name2 ] 
     node1.neighbors.add(node2) 
     node2.neighbors.add(node1) 

    def node(self, name): 
     return self.nodes[ name ] 

class GraphNode: 
    def __init__(self, name, score, neighbors=[]): 
     self.name = name 
     self.score = score 
     self.neighbors = set(neighbors) 

    def __repr__(self): 
     return self.name 

def find_path (start_node, start_score, end_node): 
    prev_solution = {start_node: [start_score + start_node.score, None]} 
    room_to_grow = True 
    while end_node not in prev_solution: 
     if not room_to_grow: 
      # No point looping endlessly... 
      return None 
     room_to_grow = False 
     solution = {} 
     for node, info in prev_solution.iteritems(): 
      score, prev_path = info 
      for neighbor in node.neighbors: 
       new_score = score + neighbor.score 
       if neighbor not in prev_solution: 
        room_to_grow = True 
       if 0 < new_score and (neighbor not in solution or solution[neighbor][0] < new_score): 
        solution[neighbor] = [new_score, [node, prev_path]] 
     prev_solution = solution 
    path = prev_solution[end_node][1] 
    answer = [end_node] 
    while path is not None: 
     answer.append(path[0]) 
     path = path[1] 
    answer.reverse() 
    return answer 

這裏是如何使用它的示例：

graph = Graph([GraphNode('A', 10), GraphNode('B', -5), GraphNode('C', -30)]) 
graph.connect('A', 'A') 
graph.connect('A', 'B') 
graph.connect('B', 'B') 
graph.connect('B', 'B') 
graph.connect('B', 'C') 
graph.connect('C', 'C') 

print find_path(graph.node('A'), 10, graph.node('C')) 

注我明確地將每個節點連接到它自己。根據您的問題，您可能需要自動完成。 （注意，左邊有一個可能的無限循環，假設起始節點的分數爲0，並且沒有辦法解決它，那麼我們將永遠循環，這將需要添加一個檢查這種情況）

Answer 2

我有點你的描述困惑，似乎你只是在尋找最短路徑算法。在這種情況下，谷歌是你的朋友。

在這個例子中，你已經給出了-ve調整，它應該是圖形遍歷的通常說法中的+ ve成本。即你想找到一個成本最低的路徑，所以你想要更多的+ ve調整。

如果您的圖形有循環有利於遍歷（即通過調整降低成本或增加點數），那麼最好的路徑是不確定的，因爲再次通過循環會提高您的分數。

Answer 3

下面是一些僞代碼

steps = [] 
steps[0] = [None*graph.#nodes] 
step = 1 
while True: 
    steps[step] = [None*graph.#nodes] 
    for node in graph: 
     for node2 in graph: 
      steps[step][node2.index] = max(steps[step-1][node.index]+node2.cost, steps[step][node2.index]) 

    if steps[step][lastnode] >= 0: 
     break;