This is a straightforward dynamic programming problem.

假设,就一定长的路程而言,就每一航道而言,你想要知道在这条路上结束的最佳成本,以及这条路从哪里走。 (该长度的数据可以储存在连接清单上的斜线上。)

为我们提供这一数据,以便采取零步骤。 然后,我们先用一个干净的圆板,然后对底部进行每一次回答,把它推向前进,如果我们没有数据,或者说我们比最佳数据更重,那么,我们就会更新有关这一节点的数据,并增加路线(将这一节点与先前的相关清单联系起来)。

一旦达到你所希望的步骤的数量,就找到了最好的现有路线,然后,你们的分量和路线就成了一个联系的清单。

================================================================================================================================================================================================================================================================

此处是实施算法的实际代码:

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 ))

Note that I explicitly connected each node to itself. Depending on your problem you might want to make that automatic.

(注,有一条可能的fin。) 假设起始点的分数为0分,而且没有办法。 在这种情况下,我们永远不休。 它将努力为这一案件增加检查。

I m a little confused by your description, it seems like you are just looking for shortest path algorithms. In which case google is your friend.

比如,你已经做了一些调整,这些调整实际上应当为平常的图表的加价。 I.e. 你们想找到一条成本最低的道路,以便你们需要多加调整。

If your graph has loops that are beneficial to traverse (i.e. decrease cost or increase points through adjustments) then the best path is undefined because going through the loop one more time will improve your score.

这里有一些皮条码

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;