最大化數字循環排列得分

我正在尋找一種有效的算法來解決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之間 - 和評分表。

非常感謝，

來源

2014-10-30 Dr C

問題是..這看起來很像旅行商問題（TSP）。解決這些問題並不總是很快。然而，你並沒有大尺寸的設計，這可能是一個可取的因素。 – Kaganar 2014-10-30 15:00:45

我想我應該問。你在尋找一種能夠找到最高分或者相當不錯的分數的算法嗎？ – Kaganar 2014-10-30 15:05:24

我寧願最高分。非常感謝。 – 2014-10-30 16:06:05

您可以用一個精確的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)）替換城市ID以獲得您正在尋找的最佳解決方案。

你也可以編寫自己的TSP解算器 - 分支&綁定技術看起來很流行。

來源

2014-10-30 18:35:22 Kaganar

因爲得分還取決於訪問的第一個和最後一個城市之間的得分，我是否需要更改算法？ – 2014-10-31 14:23:40

不應該 - 規範的定義是找到一個循環。這意味着最後一個城市需要連接到第一個城市。 – Kaganar 2014-10-31 14:25:12

最大化數字循環排列得分

回答

相關問題