탐색(Search)에 관해

목차

1.탐색 (Search)이란?

2.문제해결

3.탐색에 의한 문제해결

4.상태공간(state space)

5.상태공간(state space)-계속

6.탐색기법

7.휴리스틱 기법

8.게임트리 탐색

본문내용

탐색 (Search)이란?
컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정
인공지능적 문제해결에서 주요한 수단
해를 찾는 과정의 효율성과 찾은 해의 적합성까지 포함
학습(Learning)이나 계획(Planning)도 탐색의 일종으로 보는 견해도 있음
문제해결
인간의 지적 문제해결
‘1+2’ : 인공지능적 문제 해결로 볼 수 없음
하노이 탑 문제 : 인공지능적 탐색이 필요
직접적 기법
문제 해를 위한 순차적 수행을 위한 프로그래밍
초기상태가 다르면 프로그램 수정 필요
인공지능적 방법이 아님(거의 모든 기존의 프로그램에 의한 문제 해결방식)
인공지능적 해법
문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제 해결
예제: 하노이 타워
탐색에 의한 문제해결
최적의 해를 구할 수 없을 수도 있으나, 문제의 해에 도달하기 위한 보다 포괄적이며 자동화된 해결방안 제시
직접적 해결이 가능한 분야보다는 불확실한 상황에 의해 모호하게 표현되거나, 다양한 가변성을 가지는 문제에 대하여 문제해결 과정 중에 지적 판단이 요구되는 경우 탐색기법이 유용
문제해결의 최적의 방법보다 적당한 방법을 찾는 것이 쉽고, 인간과 상통하는 바가 있다는데에 또한 의미가 있음
완벽한 의미의 지능적 기계보다는 인간의 지능이 어느 정도 개입하는 시스템 개발이 보다 현실적임은 인정해야함. 탐색이 모든 문제를 자동으로 해결하지는 못함.
상태공간(state space)
상태: 문제의 풀이과정 중의 고유한 요소(상황)
상태의 집합을 상태공간 또는 문제공간이라 함
상태공간의 도입은 문제의 형식화에 유리
초기상태(Initial State) := ((d1,d2)()())
목표상태(Goal State) := (()()(d1,d2))
초기상태에 연산자(operator, 규칙) 적용  상태 변이  목표상태
상태공간을 트리구조로 표현: 상태 트리
문제의 해결이란 뿌리노드(즉, 초기 상태)에서 목표노드(목표상태)까지 도달하는 과정을 찾는 것
상태 트리 예(부분적 모습)
상태공간(state space)-계속
문제해결 과정
임의 노드에 연산자를 적용하여 1개 이상의 자녀노드를 확장
확장될 때까지 노드는 열려있다(Open)이라 하며, 이미 확장된 노드는 닫혀있다(Closed)라고 함
확장하려는 순간에 있는 노드를 활성노드(Active Node)라 함
문제 해결을 위하여 뿌리노드로부터 확장을 시작하여 목표상태 노드가 생성되면 성장을 멈추게 되고 한가지 해결을 찾게됨
트리의 전체 모양을 완성할 필요는 없음
일부의 트리만으로도 목표노드를 발견할 수 있다면 족함
트리의 크기가 문제해결의 효율성과 관련
어느 가지로 확장해 나갈 것인가가 탐색 알고리즘의 역할
트리에서의 노드의 재생성은 문제 야기
탐색의 효율을 저하, 무한루프에 빠질 가능성 존재
노드 상호간의 관계를 표현해 줄 수 있는 상태그래프를 이용

키워드

Search,   인공지능,   AI,   Artificial Inteligence,   A.I.,   search