필자는 인공 지능이나 게임에서 경로 찾기를위한 인기있는 알고리즘 (A-Star, Dijkstra)이 잘 알려진 "15- 퍼즐"을 해결하는 데 사용된다는 것을 AI 서적에서 읽었습니다.A-Star 또는 Dijkstra의 알고리즘으로 15 퍼즐을 어떻게 풀습니까?
아무도 나에게 이러한 알고리즘 중 하나를 적용 할 수 있도록 노드와 에지의 그래프로 15- 퍼즐을 줄이는 방법에 대한 몇 가지 조언을 제공 할 수 있습니까?
그래프의 각 노드를 게임 상태로 처리한다면 그 트리가 꽤 커지지 않을까요? 아니면 그렇게 할 수있는 방법일까요?
그냥 게임 트리를 사용하십시오. 나무는 특별한 형태의 그래프라는 것을 기억하십시오.
현재 노드에서 사용할 수있는 동작 중 하나를 만든 후에는 각 노드의 잎이 게임 위치가됩니다. 이 알고리즘 문제에 관해서 Parallel Combinatorial Search에 하나, 그리고 엄지 손가락의 External-Memory Graph Search
일반 규칙에 하나 :
빠른 구글 검색은 몇 몇 자세하게 다루 논문을 전환 사람은 가능성이 전에 일을하고있다 너 결과를에 게시했다.
링크 중 절반이 사망했습니다. – Jonny
다음은 첫 번째 링크입니다. http://www.cse.psu.edu/~pxr3/optslides.pdf –
또한. A-Star 알고리즘을 사용하면 가능한 한 다음 단계가 다른 단계보다 완성 된 경로에 더 가까운 지 여부를 판단하기 위해 허용 가능한 휴리스틱을 파악해야합니다.
아닙니다. 허용 가능한 휴리스틱은 단지 필요한 단계의 수를 과대 평가하지 않아도됩니다. 두 단계 중 어느 단계가 더 가까웠는지 알 수 있다면 일반적인 의미에서 검색을 수행하지 않고 단계가 더 가까워 질수록 반복 할 수 있습니다. –
15 개의 퍼즐이있는 A-Star에 대한 훌륭한 경험적 발견 방법은 잘못된 위치에있는 사각형의 수입니다. 당신은 제자리에서 벗어난 제곱 당 적어도 1 개의 움직임이 필요하기 때문에, 제자리의 제곱수는 퍼즐을 풀기 위해 필요한 움직임의 수보다 작거나 같음을 보증하므로 A-Star의 적절한 발견법이됩니다 . 여기
제안 된 메트릭이 문제에 잘 맞다고 생각하지 않습니다. 직관적으로 그것은 보드의 잘못된쪽에 몇 개의 조각이있는 상황에 상당히 취약합니다. 최종 위치에서 거리를 합한 것이 더 좋을 것입니다. – wowest
네 말이 맞아, 그게 좋겠지 만 내 것도 효과가있을거야. – RossFabricant
고마워, 내 페이지 야! 8Puzzle을 해결하기위한 코드가 있으며 Ivan Bratko의 Prolog Programming의 치료법을 기반으로합니다. – justinhj
이 약간 상세하게 A * 알고리즘을 사용하여 이야기 8 퍼즐 문제에 대한 과제입니다 갈뿐만 아니라, 매우 간단합니다 :
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
이있는 기억 * 귀하의 영웅에 의해 정의 된대로 목표 경로로 진행하는 문제 공간을 탐색합니다.
최악의 경우에만 전체 문제 공간을 가득 채워야 만합니다. 문제의 실제 해결책이 없을 때 이런 경향이 발생합니다.
이 문제를 해결하는 이론적 방법은 보드의 모든 구성을 그래프의 정점으로 상상해 놓은 다음 보드의 Manhatten Distance와 같은 것을 기반으로 한 브리닝 첫 번째 검색을 사용하여 가장 짧은 시작 구성에서 솔루션으로의 경로
n x n 보드의 경우 게임 공간이 너무 커져서 방문한 정점을 효율적으로 표시하는 방법이 명확하지 않은 경우가 있습니다. 즉, 보드의 현재 구성이 다른 경로를 통과하여 이전에 발견 된 것과 동일한 지 평가하는 분명한 방법은 없습니다. 또 다른 문제점은 n (약 (n^2)!)으로 그래프 크기가 너무 빨리 커지므로 경로 수가 계산적으로 트래버스 할 수 없으므로 Brue-Force 공격에 적합하지 않다는 것입니다.
이 논문의 저자 Ian Parberry A Real-Time Algorithm for the (n^2 − 1) - Puzzle은 첫 번째 행, 첫 번째 열, 두 번째 행을 완료함으로써 반복적으로 솔루션에 도달하는 간단한 욕심 많은 알고리즘을 설명합니다. 그러나 솔루션에 즉시 도착하지만 솔루션 최적에서 멀다. 본질적으로 그것은 컴퓨터 근육을 이용하지 않고 인간이하는 것처럼 문제를 해결합니다.
이 문제는 루빅 큐브를 해결할 때와 밀접한 관련이 있습니다. 모든 게임의 그래프는 너무 커서 brue force로 풀지는 못하지만, 매우 단순한 7 단계 방법이 있습니다.이 방법을 사용하면 딱딱한 인간이 약 1 ~ 2 분 안에 큐브를 풀 수 있습니다. 물론이 경로는 최적이 아닙니다. 이동 순서를 정의하는 패턴을 인식하여 속도를 17 seconds으로 낮출 수 있습니다. 그러나 Jiri의 이런 위업은 다소 초인적입니다!
Parberry 메서드는 한 번에 하나의 타일 만 이동하는 것으로 설명합니다. 하나는 Jiri의 손재주를 사용하고 한 번에 여러 타일을 움직여 알고리즘을 개선 할 수 있다고 상상해보십시오. 이것은 Parberry가 증명했듯이 경로 길이를 n^3에서 줄이지는 않지만 선행 항의 계수를 줄입니다.
이것은 compsci 숙제와 같은 냄새를 풍깁니다! –
꽤 일반적인 CompSci 숙제 문제 – monksy