如何根据成对元素分值生成多个元素的最优顺序

Question

我有很多元素，比方说 [a, b, c, d]，对于每个成对组合，我有一个分数：

[['d-a', 0], ['a-b', 0], ['b-a', 0],
 ['a-c', 2], ['c-a', 0], ['a-d', 2],
 ['d-b', 1], ['b-c', 2], ['c-b', 0],
 ['b-d', 2], ['d-c', 2], ['c-d', 2]]

我正在 Python 中寻找一种方法，将这些元素按连续顺序排列，从而使这些分数的总和最小。每个单元必须出现一次且仅出现一次。请注意，两个元素的连续性也很重要，即 'd-a' = 0 而 'a-d' = 2.

非常感谢您的回答。

谢谢

西蒙

Answer 1

elements = ['a', 'b', 'c', 'd']
scores = [['d-a', 0], ['a-b', 0], ['b-a', 0], ['a-c', 2], ['c-a', 0], ['a-d', 2],
          ['d-b', 1], ['b-c', 2], ['c-b', 0], ['b-d', 2], ['d-c', 2], ['c-d', 2]]

s = dict(scores)
print(min(itertools.permutations(elements),
          key=lambda p: sum(s[a+'-'+b] for a, b in zip(p, p[1:]))))

打印 ('c', 'a', 'b', 'd').

如何根据成对元素分值生成多个元素的最优顺序

How to generate an optimal order of multiple elements based on pairwise element score values

python

optimization

mathematical-optimization