- 현 단계에서 바로 앞 문제만 해결하면, 원하지 않은 결과 값이 나올 수 있기 때문에
n단계 까지 미리 알아본 후 최소 경로를 선택한다.(Look Ahead)
- 인공지능으로 도출된 답은 100% 좋은 값은 아니다. 단지, 쓸만한 값이다.
ex) 세일즈맨의 여행 경로(TSP Problem)
- 이 문제의 목표는 A노드에서 시작하여 각 노드를 모두 방문하여 A노드로 돌아오는 최단 경로를 찾는 것이다.
i) Not Look Ahead. 현재 위치에서 가지 않은 도시로 향하는 최단 거리를 찾을 경우
경로 : A > D > E > B > C > A / 값 : 25
ii) Look Ahead. 현재 위치에서 3단계를 앞서서 본 경우
1단계 경로 :
A > B > E (5) / A > B > C (9) / A > C > B (12) / A > C > E (9) / A > C > D (15) / A > D > C (11) / A > D > E (10)
~ 값이 제일 작은 A > B > E 선택하여 A에서 B로 이동
2단계 경로 :
B > E > C (7) / B > E > D (12) / B > C > E (11) > B > C > D(17)
~ 값이 제일 작은 B > E > D 선택하여 B에서 E로 이동
3단계 경로 :
E > C > D(14) / E > D > C(19)
~ 값이 제일 작은 E > C > D 선택하여 E에서 C로 이동
4단계 경로 :
C > D > A(11)
~ 더 이상의 경로가 나오지 않기 때문에 선택
결론 : A > B > E > C > D > A 길을 선택 값 : 20
- 앞의 문제를 어느정도 살펴 보느냐에 따라서 자신이 원하는 답을 얻을 수 있는지 없는지 여부를 알 수 있다.
* 인공지능 문제의 표현
- 인공 지능 문제를 해결하기 위해서 해결에 앞서 아래의 사항을 표현할 수 있어야 한다.
ⓐ 초기상태(Initial state) : 문제의 초기 상태
ⓑ 목표 상태(Goal state) : 문제의 최종 상태
ⓒ 상태 공간(State space) : 문제를 해결하는데 나오는 상태들의 집합
ⓓ 연산자(Operators) : 초기 상태에서 목표 상태로 변화시키는 규칙
ⓔ 제약 조건(Constraints) : 주어진 문제를 해결하는 데 지켜야 할 제약
ⓕ 목적 함수(Object Function) : 초기상태에서 목표상태에 도달하기 위한 효과 적인 탐색 방법
> 목적함수 도출이 AI 문제 해결의 핵심이며, 해결해야할 문제 자체가 될 수 있음
- 인공 지능 문제 해결의 목적 : 제약 조건을 만족하면서 초기 상태에서 목표상태로 상태를 옮기는 연산자의 계열 중에서,
목표 함수를 최대 또는 최소로 하는 상태를 발견 하는 것
* 상태 공간의 표현
- 문제의 해 : 초기 상태에서 목표 상태를 얻을 때까지 연산자를 반벅하여 실행(탐색)하여 얻어진다.
- 초기상태, 목표상태, 연산자, 제약조건이 명백하게 정해지면 탐색해야할 공간은 확실해진다.
- 표현 방식 : 그래프, 트리, AND-OR 그래프
* 문제 풀이 모형
- 문제를 컴퓨터가 형식적으로 취급하여, 마치 이해한 것처럼 만든다.
- 문제의 적잘한 해결법을 선택한다.
- 해결법을 적용하여 결과 값을 도출한다.
- 일반적인 문제 풀이 방법
ⓐ 절차에 기분을 둔 방법(Algorithm)
> 알고리즘이 존재하여, 이를 이용해 쉽게 답을 구할 수 있는 문제
> N이 커질 수록 느려져 사람이 쓰기 부적합한 것이 많다.
ⓑ 탐색에 기반을 둔 방법
> 시행착오적 방법으로 해결하는 문제
> 시행착오에서 알고리즘이 발견되면 절차 중심 방법 문제풀이로 옮겨진다.
ⓒ 사례에 기반을 둔 방법(AI)
> 경험을 이용하여 새로운 문제를 해결
> 탐색에 기반을 둔 방법보다 효율적으로 문제를 해결 가능
> 답을 구하는 Process가 정해져 있지 않아 일상생활의 대부분 문제에 사용 가능