最大化数字循环排列的得分(Maximize the score of circular arrangement of numbers)

最大化数字循环排列的得分(Maximize the score of circular arrangement of numbers)

我正在寻找一种有效的算法来解决在1-12之间安排一组循环数来获得最高分的问题。

排列的得分由其所有相邻对的得分之和给出

要获得相邻对（a，b）的分数，请计算以下步骤：

1. Find x such that (a+x) mod 12 = b 2. Look up x in a score table 3. The value in the score table at index 'x' is the score of the pair (a,b).

对于每个相邻对重复这一过程，并且总和是该排列的分数。

Here is an example: Suppose the score table is [5,4,6,7,2,7,-2,-6,-8,-2,6,12,13] Consider these numbers: 5, 12, 8, 9 For each adjacent pairs, the values for x are: 5 -> 12: 7 12 -> 8: 8 8 -> 9: 1 9 -> 5: 8 The values for score[x] are: score[7] = -6 score[8] = -8 score[1] = 4 score[8] = -6 The sum of the score[x] values is: (-6) + (-8) + (4) + (-6) = -18

我们的目标是提出一种算法来有效地安排数字以最大化分数，给定数字本身 - 最多20个在1到12之间 - 和分数表。

非常感谢，

I am looking for an efficient algorithm to solve a problem of arranging a circular set of numbers between 1-12 to get the highest score.

The score of an arrangement is given by the sum of the score of all its adjacent pairs

To get the score of an adjacent pair (a,b), the following steps are calculated:

1. Find x such that (a+x) mod 12 = b 2. Look up x in a score table 3. The value in the score table at index 'x' is the score of the pair (a,b).

This is repeated for every adjacent pair and the sum is the score of the arrangement.

Here is an example: Suppose the score table is [5,4,6,7,2,7,-2,-6,-8,-2,6,12,13] Consider these numbers: 5, 12, 8, 9 For each adjacent pairs, the values for x are: 5 -> 12: 7 12 -> 8: 8 8 -> 9: 1 9 -> 5: 8 The values for score[x] are: score[7] = -6 score[8] = -8 score[1] = 4 score[8] = -6 The sum of the score[x] values is: (-6) + (-8) + (4) + (-6) = -18

The goal is to come up with an algorithm to efficiently arrange the numbers to maximize the score, given the numbers themselves - up to twenty of them between 1 and 12 - and the score table.

Many thanks,

最满意答案

您可以使用精确的TSP求解器解决此问题。

想象一下，有一组城市，每个都有“价值”。 我们会说城市x的值是V(x) 。 现在想象一下，从城市x到y旅行它需要花费S(V(y) - v(X) (mod 12)) 。 请注意， S是您的分数表， V(y) - V(x) (mod 12)是要在分数表中查找的值。

TSP的目标是找到您应该访问所有城市的订单，以优化您的成本 - 在这种情况下，您希望最大化您的成本。 （或者，你可以让你的得分功能为负，并最大限度地降低你的成本。）

也就是说，TSP将为您提供优化您的分数的城市集合的排列。 由于您的城市实际上是您在置换时感兴趣的值，因此它会为您提供值，从而产生最佳分数。

那么..找一个程序或图书馆，你可以指定从城市x飞到城市y成本，然后让它运行，它会给你城市的最佳排列 - 然后你可以取代城市具有值（ V(id) ）的V(id)可以获得您正在寻找的最佳解决方案。

您也可以编写自己的TSP求解器 - 分支和绑定技术看起来很受欢迎。

You can solve this problem with an exact TSP solver.

Imagine there's a set of cities, each which has a "value". We'll say that the value of a city x is V(x). Now imagine that to travel from city x to y it costs S(V(y) - v(X) (mod 12)). Note that S is your score table and V(y) - V(x) (mod 12) is the value to be looked up in the score table.

The goal of TSP is to find what order you should visit all the cities exactly once to optimize your cost -- in this case, you want to maximize your cost. (Alternatively, you could just make your scoring function negative and minimize your cost.)

That is, TSP will give you a permutation of the set of cities that optimize your score. Since your cities are actually the values you're interesting in permuting, it will give you a permutation of your values that produces an optimal score.

So.. Find a program or library that allows you to specify how much it costs to fly from city x to city y and then let it run and it'll give you the optimal permutation of your cities -- then you can replace the city IDs with the value (V(id)) to get the optimal solution you were looking for.

You could write your own TSP solver as well -- branch & bound techniques look popular.