我有一个非常困难的问题要解决，我只是想知道可以使用什么算法来找到最快的路线。无向图由正向和负向调整组成，这些调整会影响在迷宫中导航的机器人或事物。我遇到的问题是迷宫，其中包含可以是 + 或 - 的循环。一个例子可能会有所帮助:-
节点A给对象10分
节点B从对象中取15
节点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
最佳答案
这是一个简单的动态规划问题。
假设对于给定长度的路径，对于每个节点，您想知道终止于该节点的最佳成本，以及该路线的来源。 (该长度的数据可以存储在散列中，即链表中的路由。)
假设我们有 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，并且没有办法离开它。在这种情况下，我们将永远循环。添加检查将需要工作对于这种情况。)
关于algorithm - 遍历具有负节点和循环节点的图的最佳算法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10319085/