저는 8 퍼즐의 작은 버전 인 3- 퍼즐 (3 블록과 공백)을 해결하는 프로그램을 만들고 있습니다. 블랭크에 인접한 블록을 빈 공간으로 이동하여 나무를 만들려고합니다. 따라서 모든 상태는 2 개의 상태를 제공 할 수 있습니다 (분기 인수 = 2). 나는 나무를 풀기 위해 폭 넓은 우선 탐색을 사용하고 있지만, 나무를 가로 지르기 위해서는 우선 만들어야합니다. 난 그냥 나무를 영원히 계속 확장 할 수 없기 때문에 나무를 일정한 깊이로 확장 한 다음 그것을 가로 지르는 수단이 있어야합니다. 따라서 탐색이 마지막 단계에 도달하면 expand() 함수를 호출하여 더 확장 할 수 있습니다. 누군가이 아이디어를 전달할 수있는 명확한 방법이나 알고리즘을 제공 할 수 있습니까? 아니면 내 문제를 해결할 다른 방법이 있습니까?나무를 횡단하면서 나무를 어떻게 확장합니까?
모든 보드 상태가 모두 set 인 채로 유지하십시오. 두 보드 상태는 다른 위치 (조각처럼 공백이 있음)가 다른 위치에 있으면 다릅니다. 일관된 순서를 사용하여 모든 자릿수를 연결하여 상태를 설명하는 문자열을 작성할 수 있습니다. 대부분의 언어/라이브러리는 문자열 세트를 직접 지원합니다.
방문하지 않은 보드 상태 만 확장해야합니다(). 처음으로 주를 방문 할 때마다 "방문 주"set에 추가해야합니다. 상태를 확장하기 전에 이미 존재하는지 확인하십시오.
전체 알고리즘 (일반에 대한 폭 우선, 어떤 중복 검색)입니다 :
place initial state into "pending" (a queue)
place initial state into "visited" (a set)
while "pending" is not empty,
extract its first state, called "next"
if it is not present in "visited",
if it is the goal, report success, ending the algorithm
otherwise, add all its children at the end of "pending"
if you reach this point, there is no way to reach a goal state from a start state
어떻게 나무를 확장하겠습니까? 어떤 상태가 트리에 자식을 가지고 있지 않다면, 확장 (state t) 함수에 현재 상태't'를 전달하여 그 노드에 2 개의 새로운 자식을 생성해야합니까? 마지막 레벨에서 모든 노드를 한 번에 확장하는 것이 더 좋은 아이디어일까요? – Ghost
각 상태에 "상위"필드를 제공하십시오 (국가 평등의 비교에 사용되지 않음). 대기열에 하위 상태를 추가 할 때마다 현재 상태를 상위로 지정하십시오. 당신이 원했던 것처럼 당신이 그것을 탐험하면서 당신은 나무를 건축 할 것입니다. 목표에 대한 최적 경로를 찾으려면 목표 상태의 부모 체인을 따르십시오 (부모가없는 시작 노드에 도달 할 때까지). – tucuxi
많이 고마워요 :) – Ghost
난 당신이 유용하게 찾을 수있는 구현이있다. 그것은 C++로 작성되었으며 내 github에 잘 설명되어 있습니다.
당신은 때때로, 실제 코드보고에서 높은 수준의 설명을 혜택을 누릴 수 있으며, 심지어 의사는 아쉬움을 남길 수 있습니다.
의견이 명확하지 않은 경우 모든 코드에 대해 명확한 이해 가능한 문서를 작성하려고합니다.
@ tucuxi 아니, 나는 3 개의 퍼즐이라고했는데, 그 이유는 공간이 단지 옆에있을 수 있기 때문이다 (단지 4 개의 사각형이 있기 때문에). 따라서 공간에 인접한 블록이 2 개만있을 수 있습니다. – Ghost
(내 이전 댓글 삭제 - 당신 말이 맞아요) – tucuxi