1. 문제풀이의 개념
1) 문제풀이란?
-
직관적으로 단순하게 해결할 수 없는 문제에 대해 문제를 파악하고 문제에 해에 이르는 방법을 찾아내는 일련의 과정
-
문제풀이에 사용될 수 있는 전략: 알고리즘, 시행착오, 경험적 방법, 통찰,
-
시행착오, 경험적 방법을 통해서 찾는다.
2) 퍼즐 문제
-
목표한 퍼즐을 만들어지도록
-
알고리즘으로 해결하기 어렵다.
-
퍼즐 조각의 배치나 이동방식을, 컴퓨터로 정의한다.
-
여러 가지 방법으로 계속 시도한다.
-
여러가지 시행착오를 거치면서 해결한다
3) 상태
-
퍼즐판에 나열된 퍼즐 조각 배치 형태
-
초기 상태: 최초에 주어진 상태
-
목표 상태: 결과에 해당되는 상태
-
상태묘사: 컴퓨터 내부에서의 표현 방식
-
연산자: 상태를 변화시키는 도구
-
상태묘사 언어: 기호 열, 다차원 배열, 벡터, 등등
4) 연산자
- 어느 한 상태로부터 변화할 수 있는 다른 상태로 변화함
ex) 연산자
퍼즐 문제 : 빈 칸의 상, 하, 좌, 우 이동
-
부모 상태: 바뀌기 전 상태
-
후계 상태: 바뀌고 난 후 상태
5) 상태 공간
- 정의된 연산자 집합을 이용하여 초기 상태로부터 얻을 수 있는 후계 상태를 나타낸 모든 상태의 집합
- 우리가 찾아야 하는 목표
- 상태 묘사 => 초기 상태 => 연산자의 집합 => 목표 상태
2. 상태 공간 탐색에 의한 문제 풀이
-
초기 상태에서 목표 상태에 도달하기 위해, 일련의 연산자를 찾는다.
-
초기 상태에서 목표 상태에 도달 하기 위한 탐색을 한다.
-
상태 공간이 너무 크면 찾기가 힘들어서 여러가지 시행 착오를 거치는 탐색 과정을 거친다.
-
가능한 탐색에 유용한 방법을 찾아서 탐색을 해야하는 범위를 좁혀야 한다.
1) 탐색 과정
-
선택된 노드에 적용할 모든 연산자를 가한다.
-
노드의 확장: 가능한 모든 노드를 찾는 과정
-
탐색이 성공하고 난 후 풀이 경로를 알 수 있도록, 부모 노드의 흔적을 남겨 둔다.
-
Open: 아직 확장 하지 않은 노드
-
closed: 이미 확장한 노드
3. 탐색 방법의 종류
1) 맹목적 탐색 (깊이 우선 탐색, 너비우선 탐색, 균일 비용 탐색)
-
목표 노드의 위치와 무관하게 순서로 노드 확장
-
시간과 자원을 많이 소비할 경우가 생김
2) 경험적 탐색 (언덕오르기 탐색, 최적 우선 탐색, 모의 담금질, A* 알고리즘)
-
경험적 정보 를 이용하여 탐색을 한다.
-
목표 위치와 관련된 경험적 정보를 사용.
4. 깊이우선 탐색, 너비우선 탐색
1) 깊이우선 탐색
-
탐색 진행 방향(깊이 방향) 계속 한쪽 노드로 진행
-
가장 최근에 생성된 노드를 가장 먼저 확장함
-
open은 스택 구조 (Last In First Out)
-
목표와 무관한 경로를 계속 탐색
-
depth bound!!! 깊이를 제한한다. 너무 오랫동안 한 우물만 파지 말라!!
-
깊이 제한에 도달하거나, 더이상 경로가 없으면 되돌아 온다.
2) 너비우선 탐색 방법
-
트리의 레벨 순서에 따라 노드를 확장함
-
생성된 순서에 따라 노드를 확장함 (first in first out)
-
천천히 같이 내려간다고 생각하면 됨.
5) 균일 비용 탐색
-
한 노드에서 다른 노드로 이동하는 비용
-
시작 노드 S 에서 n 까지 비용 g(n)
-
open 노드중에서 출발 노드로 부터의 경로 비용이 최소인 노드를 선택하여 확장함
-
open 에 확장한 노드를 넣는데 이때 겹치는 노드가 있을때는 경로가 짧은 놈으로 저장한다.
-
open을 경로비용 g의 오름차순으로 정렬
