인공지능 3강 (탐색에 의한 문제풀이)

학습개요

1. 경험적 탐색은 경험적 지식을 활용하여 문제의 해를 보다 효과적으로 탐색하기 위한 기법이다. 이번 시간에는 경험적 지식을 탐색에 적용하는 방법 및 주요 경험적 탐색 방법에 대하여 학습한다. 또한 탐색을 통해 성공적으로 목표를 달성하는데 장애가 되는 요소와 이 문제를 개선하기 위한 탐색 기법을 모색해 볼 것이다.

 학습목표

1. 경험적 탐색의 기본적 아이디어를 설명할 수 있다.
2. 각각의 경험적 탐색 방법에서 사용하는 평가함수의 형태를 설명할 수 있다.
3. 언덕오르기 탐색 알고리즘을 설명할 수 있다.
4. 계수최적화 문제에서 발생할 수 있는 문제점들을 이해한다.
5. 모의담금질 알고리즘을 설명할 수 있다.
6. A* 알고리즘으로 최적해를 구하는 방법을 설명할 수 있다.

 주요용어

1. 언덕오르기 탐색 : 임의의 상태에서 시작하여 가장 목표에 근접한 후계상태로 이동하는 탐색 알고리즘
2. 지역최대치 문제 : 시스템의 최대치에 해당되는 계수를 찾는 문제에서 실제 최대치가 아니라 주변의 극대치에 해당되는 계수를 찾게 되는 문제
3. 모의 담금질 : 탐색공간에서 평가함수의 전역최대치(최소치)에 해당되는 해를 구하기 위한 확률적인 경험적 접근 방법으로, 현재 상태를 개선하지 않는 후계상태로도 시간에 따라 감소하는 확률에 따라 이동할 수 있도록 함으로써 지역최대치(최소치)에서 빠져나올 수 있게 하는 방법
4. A* 알고리즘 : 다음 확장할 노드를 결정할 때 그 노드까지 도달하는 경로비용과 그 노드로부터 목표노드에 도달하기 위한 경로비용 예측치의 합이 최소인 노드를 선택하여 탐색하는 방법

정리하기

1. 경험적 탐색은 목표상태를 보다 효과적으로 탐색하기 위해 경험적 지식을 평가함수에 반영한다.
2. 언덕오르기 탐색은 현재상태를 확장하여 생성된 후계노드들 중에서 평가함수로 계산한 비용이 가장 적은 노드를 다음 확장할 노드로 선택한다. 이때 노드의 비용은 그 노드로부터 목표노드에 도달하는 비용을 예측한 값이다.
3. 언덕오르기 탐색과 같은 계수 최적화 방법에서는 지역최대치 문제, 고원문제, 능선문제 등으로 인해 최적의 해에 해당되는 목표상태에 도달하지 못할 가능성이 있다.
4. 모의담금질(simulated annealing)은 시간에 따라 감소하는 확률에 따라 평가함수의 값이 개선되지 않는 후계상태로도 이동할 수 있게 하는 확률적 접근방법이다.
5. A* 알고리즘에서 노드의 평가함수는 출발노드로부터 그 노드에 도달하기 위한 비용과 그 노드로부터 목표노드에 도달하는데 필요한 예측비용의 합으로 정의된다.
6. A* 알고리즘에서는 평가함수가 최소인 노드를 선택하여 확장한다. 예측비용이 항상 실제 비용 이하로 예측되도록 정의한다면 탐색된 경로는 최소비용 경로이다.