快速 Python 算法，用于找到使每个移动的变化总和最大化的路径

Question

假设我有一个无向图（可以是循环的或非循环的），其中每个节点都分配有一个整数状态。我想找到这样的路径：

遍历每个节点但只遍历一次
不需要遍历每条边
最大化每步状态变化的总和

例如，我有一个循环图-5-4-5-7-2-（前5个和后2个相连）。如果我们从前5个开始，到后2个结束，那么每一步的变化总和就是-1 + 1 + 2 + (-5) = -3。该图可以用邻接矩阵描述如下：

import numpy as np
node_states = [5, 4, 5, 7, 2]
# Adjacency matrix
               #5 4 5 7 2
am = np.array([[0,1,0,0,1], # 5
               [1,0,1,0,0], # 4
               [0,1,0,1,0], # 5
               [0,0,1,0,1], # 7
               [1,0,0,1,0]])# 2

预期输出为

max_delta_sum_path = [2, 5, 4, 5, 7]

路径总和最大的地方3 + (-1) + 1 + 2 = 5

谁知道有没有比较快的算法可以自动找到这条路径？

Answer 1

将每个未定向的 link 替换为两个定向的、成本较高的 link。例如，状态 5 和 7 的节点之间的 link 将被两个 link 替换，成本为 +2 和 -2。
为每个 link 的成本增加价值，这将使所有 link 成本为正值
找到最昂贵的 link 的成本并从每个 link 成本中减去
将每个 link 成本乘以 -1
应用旅行商算法

因此，对于您的示例：

0 -> 1 cost -1 converts to 6

0 -> 4 cost -3 converts to 8

1 -> 0 cost 1 converts to 4

1 -> 2 cost 1 converts to 4

2 -> 1 cost -1 converts to 6

2 -> 3 cost 2 converts to 3

3 -> 2 cost -2 converts to 7

3 -> 4 cost -5 converts to 10

4 -> 0 cost 3 converts to 2

4 -> 3 cost 5 converts to 0

Answer 2

我想这就是您要找的：

import numpy as np
node_states = [5, 4, 5, 7, 2]
# Adjacency matrix
               #5 4 5 7 2
am = np.array([[0,1,0,0,1], # 5
               [1,0,1,0,0], # 4
               [0,1,0,1,0], # 5
               [0,0,1,0,1], # 7
               [1,0,0,1,0]])# 2

for i in range(len(node_states)):
    for j in range(len(node_states)):
        if am[i][j] == 1:
            am[i][j] = node_states[i] - node_states[j] # go through ever entry in every list, and if it is 1 replace it with the traversal cost
"""
am =    [[ 0  1  0  0  3]
         [-1  0 -1  0  0]
         [ 0  1  0 -2  0]
         [ 0  0  2  0  5]
         [-3  0  0 -5  0]]
"""

from itertools import permutations
def largest_sum(node_states, am):
    largest = None
    largest_journey = None
    traversal_list = list(permutations(range(len(node_states)), len(node_states))) # store all possible permutations of node_states indexes
    for trav in traversal_list: # go through each permuatation
        costs = [] # track the cost of each traversal
        for i in range(len(trav)):
            if i == 0: # there are one less traversals than nodes so we are ignoring the first node
                continue
            if am[trav[i]][trav[i-1]] == 0: # traversal cannot happen if the traversal has no adjacency
                continue
            costs.append(am[trav[i]][trav[i-1]]) # use the updated am matrix to get our costs, and store them here
        if len(costs) == len(node_states) - 1: # if one less traversal was made than we have nodes, we know all nodes were visited
            costs_sum = sum(costs) # sum the costs for our total of travel
            if largest is None or largest < costs_sum: # only keep this total if it was bigger than our old total
                largest = costs_sum # track the new total
                largest_trav = list(map(lambda x: node_states[x], trav)) # change our array of indexes (trav) into an array of node values
    return largest_trav # when the looping is done, return our total

out = largest_sum(node_states, am)
print(out)

输出：

[2, 5, 4, 5, 7]

快速 Python 算法，用于找到使每个移动的变化总和最大化的路径

Fast Python algorithm for finding the path that maximize the sum of the changes of each move

python

algorithm

graph

undirected-graph