一种快速的Python算法，用于寻找最大的每次移动的变化之和的路径

Question

假设我有一个无向图(可以是循环图，也可以是无环图)，其中每个节点都带有整数状态。我想找到这样一条路：

1. 遍历每个节点，但只有一次
2. 不需要遍历每个边缘
3. ，使每个移动

的状态变化之和最大化

作为一个例子，我有一个循环图-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

我想这就是你要找的：

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]

Answer 2

• 将每个无定向链接替换为两个有向、有成本的链接。例如，状态5和状态7的节点之间的链路将被两个成本为+2和-2的链路所取代。
• 为每条链路的成本增加了价值，这将使所有链路成本变为正
• ，并从每个链路成本中减去
• 乘以-1
• 乘以-1
• 应用旅行推销员算法

f 211

所以，举你的例子：

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