N 퍼즐을 풀기위한 A * 경험적 방법의 비교

Question

나는 3 가지 다른 경험적 함수를 가진 A * 알고리즘을 사용하여 N-puzzle을 풀려고합니다. 시간 복잡성의 관점에서 각각의 경험적 방법을 비교하는 방법을 알고 싶습니다. 내가 사용하고있는 경험적 방법은 맨하탄 거리, 맨하탄 거리 + 선형 충돌, N- 맥스 스왑입니다. 특히 8 개의 퍼즐과 15 개의 퍼즐이 필요합니다.

Answer 1

N-Puzzle은 일반적으로 가장 짧은 솔루션을 찾기가 쉽지 않으므로 어떤 휴리스틱 스를 사용하든 관계없이 복잡하지 않은 차이점을 찾을 수는 없습니다. 어떤 경계의 견고 함을 증명하십시오.

8- 퍼즐이나 15- 퍼즐로만 제한하는 경우 허용 가능한 휴리스틱이있는 A * 알고리즘은 보드 위치가 유한하지만 큰 수이기 때문에 O (1) 시간에 실행됩니다.

Answer 2

@Harold가 언급 한 바에 따르면, 휴리스틱 함수의 시간 복잡도를 비교하는 접근법은 실험적 테스트에 의한 것입니다. 귀하의 경우, 8- 퍼즐과 15- 퍼즐에 대해 n 임의의 문제 집합을 생성하고 다른 휴리스틱 함수를 사용하여 문제를 해결하십시오. 상황이 인식 할 수는 있습니다

1. 이 비교는 항상 하드웨어 expecs, 프로그래밍 언어, 기술 알고리즘을 구현 같은 여러 가지 요인에 따라 달라집니다 ...

2. 이 일반적으로 더를 정보가있는 경험적 방법은 정보가 부족한 것보다 적은 노드를 늘릴 것이고 아마도 더 빠를 것입니다.
   1. 문제점 :

   그리고 마지막으로, 각 문제에 세트에 대한 세 가지 추론을 비교하기 위해, 나는 평균 실행 시간과 그래픽을 건의 할 것 (예를 들어 5 회 문제를 반복) 난이도에 따라 정렬 된 x 축에 있습니다.

3. 실행 시간은 각 경험칙 함수 (대개 대안의 차이를 쉽게 볼 수없는 경우 로그 눈금)로 y 축에 있습니다.

및 탐구 된 상태의 수와 유사한 그래픽.