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

8-puzzle를 풀때 사용할것은 "트리"이다.

동그라미들이 노드 이다.

 

 

초기상태에서 목표상태로 한번에 가면 좋지만 한번에 가지 못한다.

• 상태공간(state space): 상태들이 모여 있는 공간​
• 연산자(operator): 다음 상태로 이동할 때 필요한 행동​

 

깊이 우선 탐색

막다른 길을 만나면 부모노드로 올라간다.

더 이상 갈곳이 없으면 루트로 올라간다.

그렇게 루트에서 H까지 간다.

H까지 도착하면 끝이 아니라 루트까지 올라가야 끝이다.

F에서 시작하여 F에서 끝난다.

선입선출이라 생각하면 쉽다.

※ 깊이 우선 탐색(DFS)의 특징

 

- 자기 자신을 호출하는 순환 알고리즘의 형태를 지님

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

 

 

※ 너비 우선 탐색(BFS)의 특징

 

- BFS 는 재귀적으로 동작하지 않는다.

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

- BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함 

- 즉 선입선출(FIFO) 원칙으로 탐색

위 2가지 탐색 방법을 8퍼즐 해결에 사용한다.

 

먼저 상태를 정의해준다.

 

연산자를 정의해준다.

위 문제를 해결하기 위해 시뮬레이션 사이트에 접속해준다.

https://deniz.co/8-puzzle-solver/

 

깊이 우선으로 진행한다.

1번 진행

2번 진헹해준다.

3번 진행한다.

---

10번째 진행

10번째 진행을 하면 파란색 노드는 거의 버림(??)받은걸 알 수 있다.

이 방법으로 8퍼즐을 풀면 한숨 자고와도 다 못풀것 같다.

 

너비 우선 탐색으로 진행해준다.

1번 진행

2번 진행

3번 진행

---

10번 진행

너비 우선 탐색은 넓게~넓게 진행한다.

 

위 두가지 탐색처럼 무식한 방법이 아닌 휴리스틱 탐색을 진행해보겠습니다.

 

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