3

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

  1. 节点 A 给对象 10 分

  2. 节点 B 从对象中取 15

  3. 节点 C 给对象 20 分

路线=""

起始节点是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-fords 和 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
4

3 回答 3

2

这是一个简单的动态规划问题。

假设对于给定长度的路径，对于每个节点，您想知道在该节点处结束的最佳成本，以及该路径的来源。（该长度的数据可以存储在散列中，即链表中的路由。）

假设我们有 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 并且没有办法离开它。在这种情况下，我们将永远循环。为这种情况添加检查需要工作.)

于 2012-04-25T16:09:17.893 回答
0

我对您的描述感到有些困惑，您似乎只是在寻找最短路径算法。在这种情况下，谷歌是你的朋友。

在您给出的示例中，您有 -ve 调整，在图遍历的通常用语中，这实际上应该是 +ve 成本。即你想找到一条成本最低的路径，所以你需要更多的+ve调整。

如果您的图表有利于遍历的循环（即通过调整降低成本或增加点数），那么最佳路径是未定义的，因为再通过一次循环将提高您的分数。

于 2012-04-25T16:02:31.750 回答
0

这是一些伪代码

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;
于 2012-04-25T16:30:08.577 回答