Simulated Annealing and Yahtzee!

Question

나는 Programming Challenges을 집어 들고 얏쯔를 발견했습니다! 내가 단순화 문제 :

• 13 개 득점 범주가 있습니다
• 각 롤
• 목표는에있는 별개의 범주에 맞아야합니다 (연극을 포함) 플레이어가 13 롤이 있습니다 연극 (범주에서 롤의 최적 배치)에 대한 최대 점수를 찾습니다; 점수 (놀이)는 놀이를위한 점수를 돌려 보낸다

최대 놀이 점수를 찾아내는 것은 13를 요구한다! (= 6,227,020,800) score() 호출.

시뮬레이션 어닐링을 선택하면 가장 높은 점수에 가까운 것을 더 빨리 찾을 수 있습니다. 결정적이지는 않지만 충분합니다.

((1,2,3,4,5) #1 
(1,2,6,3,4),#2 
    ... 
(1,4,3,2,2) #13 
) 

그리고 점수에 전달 연극 (1,5,6,7,2,3,4,8,9,10,13,12,11)()이 놀이의 순열에 대한 점수를 반환 내가 좋아하는, 5 다이 (13) 롤의 목록을 가지고있다.

"인접 상태"를 어떻게 선택합니까? 랜덤 재시동의 경우, 임의로 순열을 선택할 수 있습니다. 1-13, 그들을 벡터에 넣고 점수를 매기십시오. 여행하는 세일즈맨 문제에서, 여기에 good neighboring state의 예 : ". 어떤 특별한 순열의 이웃 인접한 도시 한 쌍의 상호 교환 에 의해, 예를 들어 생산하는 순열이다"

가

는 단순히과 같이, 임의의 두 벡터의 위치를 ​​교환에 대한 나쁜 감정이 있습니다

(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13 
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one 

을하지만 증거가없는 좋은 이웃 상태를 선택하는 방법을 모르겠어요. 누구든지 좋은 이웃 국가를 고르는 방법에 대한 아이디어가 있습니까?

Answer 1

페어 스왑 전략은 나에게 좋지 않습니다. 그것은 확실히 이론 - 모든 순열을 방문합니다. 가장 중요한 점은 귀하의 사례에서 '이웃'이 실제로 '유사'한지 확인하는 것입니다. 즉, 한 쌍만 바꾸는 경우에만 서로 다른 두 개의 게재 위치가 점수면에서 유사합니다. 나는 당신의 "게임"의 규칙이 나에게 명확하지 않기 때문에 이것을 결정할 수 없습니다.

Answer 2

트릭은 여러 유형의 이동을하는 것입니다. SA는 작고 통일 된 움직임과 크고 다양한 동작을 제공합니다. 그러나 첫 번째 제안 기회가 높아집니다. 작은 움직임은 쉽습니다. 1을 변경하거나 2를 바꿉니다.

drools planner의 내 간호사 숙청 예제를보십시오. java의 오픈 소스.