경험적 탐색(휴리스틱 탐색, 최고 우선 탐색, A-star)으로 8-puzzle 해결법, 길 찾기 원리 | 유찬맨 |

경험적 탐색(휴리스틱 탐색)으로 8-puzzle 해결법

8-puzzle 문제 트리(깊이 우선 탐색, 너비 우선 탐색)으로 해결법

 

전에 진행한 방법이 아닌 휴리스틱 탐색으로 8퍼즐을 해결해보겠습니다.

위 평가함수를 이용하여 최고 우선탐색을 진행한다.

최고 우선 탐색은 평가함수를 활용하여 이동한다 위 이미지는 왼쪽(평가함수가 높은쪽)으로 이동한다.

이쯤에서 생각해 봐야 하는게 과연 평가함수가 높은것만 따라 가는것이 좋은껄까?

평가 함수가 높은것 만을 따라 가면 답이 나오긴한다. 하지만 최고 우선 탐색은 오직 높은 점수만 보기 때문에 시야가 좁아서 최고의 해를 구하지 못할 수도 있다.

 

최고 우선 탐색의 문제를 보안한 것이 

A*(A-star) 알고리즘이다.

A* 알고리즘은 휴리스틱 추정값을 통해 알고리즘을 개선할 수 있는데요. 이러한 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있느냐가 결정됩니다.

 

A-star 알고리즘은 게임에서 길찾기 알고리즘으로 많이 사용한다. 

 

A-star는 이동횟수, 오답 수가 제일 적은 곳으로 이동한다.

 

위 이미지 처럼 초록색값(오답 수가 없는 곳)이 최종 도착지이다.

깊이 우선 탐색, 너비 우선 탐색을 사용할때 시간이 무제한 존재하면 무조건 답을 찾을 수 있는 반면

A*방식을 사용한다면 매우 빠르게 답을 찾을 수 있지만 찾지 못할 수도 있다.

 

8퍼즐을 해결하는 탐색법들을 정리한 영상 첨부하며 마치겠습니다.

 

아무리 코딩을 잘해도 평가함수를 모른다면 인공지능으로 그 어떠한 게임도 만들지 못한다.