헝가리 반지 퍼즐

Question

나는 헝가리 반지 퍼즐에 대한 인정 가능한 발견법을 찾는 데 어려움을 겪고있다. IDA * 알고리즘을 사용하여 Visual Basic에서 프로그램을 작성하고 작성하려고합니다. 내가 부족한 것은 실제 퍼즐을 푸는 방법입니다. 왼쪽 및 오른쪽 링을 자체 배열에 구현했으며 각 링을 시계 방향 및 반 시계 방향으로 회전시키는 기능을 가지고 있습니다. 나는 코드를 요구하지 않고 시작하기위한 어딘가에있다. 레드 값 = 1 노란색 = 2 블루 = 3 블랙 = 4

이 : 나는 각 색상의 값으로 다음을 저장, 배열에서

Dim leftRing(19) As Integer 
' leftRing(16) is bottom intersection and leftRing(19) is top intersection 
Dim rightRing(19) As Integer 
' rightRing(4) is top intersection and rightRing(19) is bottom intersection 

: 여기

은 2 링 배열입니다

Answer 1

나는 반지를 풀기 위해 몇 개의 볼을 교체해야하는지 (1 9- 컬러, 10 10- 컬러, 9- 컬러에서 1 개의 고독 볼)를 각 링에서 따로 따로 세는 것을 제안합니다. 회전을 사용하여 최대 두 개의 볼을 고정 할 수 있으며 다른 두 개의 고정을 위해 다른 회전이 필요합니다. 각 반지의 거리를 개별적으로 계산 = 2n-1 여기서 n은 불량 위치의 절반입니다. 오류가 가장 적은 위치를 찾을 때 20 개의 위치를 ​​모두 반복 할 수 있지만 단순한 정리는 제외하고이 측정 기준을 계산하는 더 좋은 방법이 있다고 가정합니다.

업데이트 : 가레스 리드에 대한 논의는 다음 휴리스틱을 가리키는 : 별도로 각 링에 대한

, 수 : 색상 변경의

1. 수. 목표 금액은 링당 세 가지 색상 변경이며 한 번에 최대 네 가지 색상 변경 사항을 삭제할 수 있습니다. 크레딧은이 측정 항목에 대해 Gareth로 이동합니다.
2. 다른 색상의 수를 무시하고 위치를 무시합니다. 10 개의 공 10 개, 9 개의 공 9 개, 다른 9 개의 공 1 개. 한 번에 최대 2 가지 색상을 변경할 수 있습니다.
   가
   1. 10 10 공, 10 공 9가 같아야

   제 휴리스틱

은 세 부분으로 분할 할 수있다. 10 개 이상의 공을 교체해야합니다.
3. 10 볼 중 단 하나의 색만 있어야합니다. 부 색상의 공을 교체해야합니다.
4. 9 색 중 하나의 볼 만 있어야합니다. 다른 색상의 볼을 교체해야합니다. 모두가 같은 색이고 9 색이 부족하지 않으면 추가로 1 개의 공을 교체해야합니다.

큰 추정치를 사용하십시오. 반지를 번갈아 할 필요가 있으므로 2n-1의 움직임이 실제로 n 개의 교체에 필요합니다. 두 견적이 동일하거나 더 큰 견적이 최근에 이동 한 반지 인 경우 추가 견적을 추가하십시오. 반지 중 하나는 첫 번째 이동으로 향상되지 않습니다.

동일한 링을 두 번 돌리는 모든 이동을 삭제합니다 (큰 회전을 허용하는 이동 메트릭 가정). 이것들은 이미 탐구되었다.

이렇게하면 모든 지역 최소값을 피해야합니다.