숫자 순환 배열의 점수 최대화

Question

높은 점수를 얻으려면 1-12 사이의 원형 숫자 집합을 정렬하는 문제를 해결하는 효율적인 알고리즘을 찾고 있습니다.

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). 

:

구성의 스코어 인접한 쌍 점수 (a가, b)는 다음과 같이 계산된다을 얻기 위해 모든 인접 쌍

을들의 점수의 합으로 주어진다

인접한 모든 쌍에 대해 반복되며 합계는 배열의 점수입니다. 및 점수 표 - 1과 12 사이의 그 스무까지 -

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 

목표는 숫자 자체를 주어, 효율적으로 점수를 극대화하기 위해 숫자를 배열하는 알고리즘을 마련하는 것입니다.

많은 감사합니다.

Answer 1

정확한 TSP 해결사로이 문제를 해결할 수 있습니다.

"가치"가있는 일련의 도시가 있다고 상상해보십시오. 우리는 도시의 가치가 x 인 것을 V(x)이라고 말할 것입니다. 이제 도시 x에서 y으로 여행하는 경우에는 S(V(y) - v(X) (mod 12))이 걸린다 고 상상해보십시오. S은 점수 표이고 V(y) - V(x) (mod 12)은 점수 표에서 조회 할 값입니다.

TSP의 목표는 비용을 최대화하기 위해 모든 도시를 정확히 한 번 방문해야하는 순서를 찾는 것입니다.이 경우 비용을 최대화해야합니다. (또는 점수 산정 기능을 음수로 설정하고 비용을 최소화 할 수 있습니다.)

즉, TSP는 점수를 최적화하는 도시 세트의 순열을 제공합니다. 도시가 실제로 당신이 퍼뮤팅에 흥미있는 가치이기 때문에, 그것은 당신에게 최적의 점수를 산출하는 가치의 순열을 줄 것입니다.

그래서 .. x 도시에서 y 도시로 비행하는데 드는 비용을 지정한 다음 그것을 실행하게하면 도시의 최적 순열을 줄 수있는 프로그램이나 라이브러리를 찾으십시오. 찾고자하는 최적의 솔루션을 얻으려면 도시 ID를 값 (V(id))으로 바꿀 수 있습니다.

여러분은 TSP 솔버도 작성할 수 있습니다 - & 바운드 기법이 인기가 있습니다.