algorithm - Maximize the score of circular arrangement of numbers -

algorithm - Maximize the score of circular arrangement of numbers -

i looking efficient algorithm solve problem of arranging circular set of numbers between 1-12 highest score.

the score of arrangement given sum of score of adjacent pairs

to score of adjacent pair (a,b), next steps calculated:

1. find x such (a+x) mod 12 = b 2. x in score table 3. value in score table @ index 'x' score of pair (a,b).

this repeated every adjacent pair , sum score of arrangement.

here example: suppose score table [5,4,6,7,2,7,-2,-6,-8,-2,6,12,13] consider these numbers: 5, 12, 8, 9 each adjacent pairs, values x are: 5 -> 12: 7 12 -> 8: 8 8 -> 9: 1 9 -> 5: 8 values score[x] are: score[7] = -6 score[8] = -8 score[1] = 4 score[8] = -6 sum of score[x] values is: (-6) + (-8) + (4) + (-6) = -18

the goal come algorithm efficiently arrange numbers maximize score, given numbers - 20 of them between 1 , 12 - , score table.

many thanks,

you can solve problem exact tsp solver.

imagine there's set of cities, each has "value". we'll value of city x v(x). imagine travel city x y costs s(v(y) - v(x) (mod 12)). note s score table , v(y) - v(x) (mod 12) value looked in score table.

the goal of tsp find order should visit cities 1 time optimize cost -- in case, want maximize cost. (alternatively, create scoring function negative , minimize cost.)

that is, tsp give permutation of set of cities optimize score. since cities values you're interesting in permuting, give permutation of values produces optimal score.

so.. find programme or library allows specify how much costs fly city x city y , allow run , it'll give optimal permutation of cities -- can replace city ids value (v(id)) optimal solution looking for.

you write own tsp solver -- branch & bound techniques popular.

algorithm search tree permutation maximize