如何遍历带有负权节点和环的图的最佳算法

Question

我有一个非常困难的问题需要解决，我想知道有什么算法可以用来找到最快的路线。这个无向图由正面和负面调整组成，这些调整会影响一个机器人或物品在迷宫中的导航。我的问题是包含循环的迷宫，它们可以是+或-。下面是一个例子：

1. 节点A给对象10点

2. 节点B从对象中取走15点

3. 节点C给对象20点

route=""

起始节点为A，结束节点为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-Ford和Dijkstra，但这些算法只给出了简单的路径而不是循环路径。

它可能以某种方式是递归的或某种启发式形式吗？

---

关于您的类比：

我想我明白您的意思了，加上一些伪代码会更清晰，到目前为止route()

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

- David Ryan

---

从这个例子中我推断出： "机器人有一个资源编号，它是一个整数，不能允许其低于零。每个节点都有一个值；当访问该节点时，机器人的资源会因该值而改变。" 这样对吗？ - gcbenison

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，而且没有离开它的方法。在这种情况下，我们将永远循环。添加一个检查此情况的检查将需要一些工作。）

- btilly

---

我会补充一下，如果没有正权重环路的情况下，在 #nodes 步后终止。 - dfb

抱歉，请查看主要文本，我已编辑以显示伪代码，我走对了吗？ - David Ryan

@DavidRyan - 我的意思是，如果一个图中没有正权重环（不是说它们无效，在这个图中它们不存在），可能就没有答案。 - dfb

你的解决方案是否可以运行？因为我无法使其工作，似乎有一个无限循环导致 CPU 占用率飙升。 - David Ryan

@DavidRyan 我的代码在 Python 2.6.3 上运行良好。我的第一份代码会在图中没有解决方案时进入无限循环，但我已经为我所知道的所有问题提供了修复方法，很快我会更新我的帖子。 - btilly

Answer 2

这里是一些伪代码

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;

- dfb

---

谢谢，我会尝试编程并查看是否可行。顺便说一下，我的图表包含1-23个节点，所给的示例过于简单仅用于演示。 - David Ryan

我假设Max()函数是一个区间函数，用于查找a和b之间的区间Max(a,b)，那么None*graph是什么？这是实际上未访问的节点等吗？ - David Ryan

这是Python风格的伪代码。None*graph.#numnodes只是一个长度为（节点数）的数组。Max仅仅是如果a>b则为a，否则为b。 - dfb

Answer 3

我有点困惑你的描述，似乎你只是在寻找最短路径算法。如果是这样，那么谷歌就是你的好朋友。

在你给出的例子中，你有负调整，实际上在图遍历的通常用语中应该是正成本。也就是说，您希望找到具有最低成本的路径，因此您需要更多的正调整。

如果您的图具有对遍历有利的循环（即通过调整降低成本或增加分数），则最佳路径未定义，因为再经过一次循环将改善您的得分。

- brain

---

我正在寻找一种有效的方法来遍历上述图形，其代价>0。抱歉，也许使用“调整”一词使其不太清楚，基本上每个节点都有一个资源级别，当机器人移动到该节点时，机器人的资源或生命级别将根据节点的权重增加或减少。 抱歉，我对图形术语并不完全熟悉。因此，我正在寻找一种算法来决定要采取哪条路径。顺便说一句，这是一个无向图。 - David Ryan

机器人只能拥有100个点，因此超过100的任何成本都是无效的，因此具有120个点或％的节点仅为机器人提供100％。也许点数不是最好使用的东西。 - David Ryan

遍历过程中，机器人可以得到小于0分的分数吗？ - brain