겹치는 카드로 게임을 해결하기위한 구조/알고리즘

Question

Tower Solitaire, Tripeaks 또는 Fairway Solitaire 라인을 따라 카드 게임을 고려하십시오. 테이블은 즉시 사용할 수있는 일부 카드로 구성되며 각 카드는 그 아래에 다른 카드를 덮을 수 있습니다 (재생되는 것을 막는 데 차단). 하나의 "기초"카드가 있으며, 파운데이션 카드의 정확히 1 위 또는 아래에있는 경우 테이블에서 카드를 제거 할 수 있습니다.이 시점에서 새 파운데이션 카드가됩니다. 테이블에서 카드를 재생할 수 없을 때 가져야 할 교체 카드 수가 제한되어 있으므로 일반적으로 가능한 가장 긴 카드를 재생하고 싶습니다.

먼저, 솔루션 찾기를 용이하게하기 위해 이사회를 어떻게 대표 하시겠습니까? 둘째, 가장 긴 재생 가능한 시퀀스를 찾기 위해 어떤 알고리즘을 사용 하시겠습니까?

예시:

  -4a- -5-
-3-  -2- -4b-

하단 블록 카드의 카드는 제거되지 않습니다. 3과 2가 모두 사라질 때까지 4A를 제거 할 수 없습니다. 시작 카드가 에이스라고 가정하면 여기서 최적의 플레이는 2, 3, 4b, 5, 4a입니다. (대신 2, 3, 4a를 플레이 할 수는 있지만 그다지 좋지는 않습니다.)

나는 이것이 일종의 지시 된 그래프로 표현되어야한다고 생각합니다. 3과 2 내지 4A, 2 및 4B에서 5 사이의 가장자리가 있지만, 3과 2 사이, 4A에서 5 사이의 가장자리가 있습니까? 그렇다면 순서 (3 번 또는 2 또는 2) 중 어느 쪽이든 재생 될 수 있다는 사실이 그래프에서주기를 형성하여 효율적인 "가장 긴 경로"알고리즘을 사용하지 못하게합니까? (그래프에주기가 포함 된 경우 그래프에서 가장 긴 경로를 찾는 것이 NP가 완료되었다고 생각합니다.)

Answer 1

이것을 게임 상태의 그래프로 표현한다면 (즉, 잠재적으로 다음 상태가 계산 된) - 루프가 없을 것입니다. 시작점.

Answer 2

요점은 가능한 가장 적은 노드가있는 지시 된 acyclic 그래프를 구성하는 것입니다.이 노드는 문제의 상태 공간을 완전히 캡처 할 것입니다. 그런 다음 일반적인 알고리즘을 실행할 수 있습니다.

테이블에 나머지 카드의 구조의 모양을 기반으로 인코딩을 제안합니다.

상태의 첫 번째 데이터는 가장 왼쪽 최상단 카드의 고유 한 ID 일 수 있습니다. (예를 들어, 4A와 같이, 그것은 단 하나의 카드 4A 만 있다는 의미에서 독특합니다). 나머지 모양은 왼쪽의 다음 카드가 동일한 '레벨'에 있는지 또는 한 레벨인지를 설명하는 각 카드에 대해 -1,0,1 중 하나로 표시 될 수 있습니다. 더 깊거나 더 높습니다. (이것은 카드가 다른 카드 2 개만 겹치고 구조가 예제에서 제공 한 구조처럼 보인다는 가정을 악용하고 있습니다).