[인공지능 시스템 2강]

1. 문제풀이의 개념

1) 문제풀이란 무엇인가?

2) 문제의 표현

3) 문제 표현의 예

 

2. 탐색에 의한 문제풀이

1) 상태공간 탐색에 의한 문제풀이

2) 탐색 방법의 종류

 

3. 깊이우선 탐색 및 너비우선 탐색

1) 깊이우선 탐색

2) 너비우선 탐색

 

4. 균일비용 탐색

1) 균일비용 탐색이란?

2) 균일비용 탐색 알고리즘

3) 균일비용 탐색 예제

 

주요 용어

문제풀이란 ?

인공지능에서 문제풀이란 직관적으로 단순하게 해결할 수 없는 문제에 대해 문제를 파악 하고 문제의 해에 이르는 방법을 찾아내는 일련의 과정을 의미한다.

 

 

1) 깊이우선 탐색

깊이우선 탐색(depth-first search)은 탐색 진행방향으로 계속 전진하여 목표를 탐색하는 방법이다. 이렇게 탐색하기 위해서는 가장 최근에 생성된 노드를 가장 먼저 확장하며, 따라 서 OPEN은 스택 구조를 사용한다. 이와 같은 탐색 방법은 목표에 도달할 수 없는 경로를 계속 탐색하는 문제가 발생할 수 있다. 이를 방지하기 위해 깊이제한(depth bound)을 정하여 무한정 진행하지 않도록 제한할 수 있다. 만일 깊이제한에 도달하거나 더 이상 진행할 경로가 없다면 이전 상태 중 다른 경 로를 선택할 수 있는 위치로 복귀하여 탐색을 계속한다.

 

2) 너비우선 탐색

너비우선 탐색(breadth-first search)은 트리의 레벨 순서에 따라 노드를 확장하는데, 이것 은 생성된 순서에 따라 노드를 확장하는 것이며, 이를 위해 OPEN의 구조는 큐를 사용한다. 너비우선 탐색은 만일 해가 존재한다면 출발노드에서 목표노드까지 도달하는 최단길이 경로 를 찾는 것을 보장한다.

 

3) 균일비용 탐색이란?

깊이우선 탐색이나 너비우선 탐색에서는 한 상태에서 다른 상태로 이동하기 위해 필요한 ‘비용’은 고려하지 않았다. 그러나 문제에 따라서는 상태의 이동에 따른 비용이 다를 수 있다.

 

 

탐색트리

 

정리 및 의문

- 맹목적 탐색과 경험적 탐색의 차이?

- 각 탐색 방법별 차이점?