인공지능) 2. 탐색에 의한 문제풀이(1)

문제풀이의 개념

직관적으로 단순하게 해결할 수 없는 문제에 대해 문제를 파악하고 문제의 해에 이르는 방법을 찾아내는 일련의 과정

• 문제풀이에 사용될 수 있는 전략
  -> 알고리즘, 시행착오, 경험적 방법, 통찰

문제의 상태를 컴퓨터로 표현

• 상태
  • 초기상태: 최초에 주어진 문제의 상태
  • 목표상태: 풀이된 결과에 해당하는 문제의 상태
• 상태 묘사
  적절한 자료구조를 이용하여 컴퓨터를 통해 상태를 표현한 것
  문제에 따라 적절한 자료구조 선택 -> 기호 열, 벡터, 다차원 배열, 트리, 리스트 등
• 연산자
  상태를 변화시키기 위한 도구의 표현

연산자의 정의

1. 변환 테이블을 정의하는 방법
   • 모든 입력 상태묘사에 대해 각각의 상태로부터 변화할 수 있는 모든 출력 상태묘사를 저장하는 목록 생성
2. 일반화된 변환 규칙으로 정의하는 방법
   • 하나의 상태묘사를 다른 상태묘사로 변환시키는 일종의 연산능력을 지닌 함수로 정의

상태 사이의 관계 표현

방향성 그래프를 이용하여 부모상태와 후계상태의 관계 표현

• 상태 공간
  정의된 연산자 집합을 이용하여 초기상태로부터 얻을 수 있는 모든 상태의 집합

상태공간에서 문제풀이를 위한 문제의 표현

1. 상태 묘사 및 초기 상태 정의
2. 연산자 정의
3. 목표 상태 정의

탐색에 의한 문제풀이

• 그래프에서 경로 탐색 문제
  시행 착오를 거치면서 목표상태에 도달하는 탐색 과정
• 탐색에 유용한 지식을 사용함으로 방대한 상태공간에서 탐색의 범위를 줄인다

탐색 과정

1. 정해진 기준에 따라 노드 선택
2. 선택된 노드에 적용할 수 있는 모든 연산자를 가하여 모든 후계노드를 생성
3. 노드의 확장
   후계노드에 부모노드를 가리키는 포인터를 첨부
   -> 탐색에 성공 후 풀이 경로를 알 수 있게 함
4. 목표 노드가 있는지 검사
5. 원하는 목표를 찾지 못했을 경우, 정해진 기준에 따라 다음 노드를 선택, 탐색 과정 반복

OEPN: 합으로 확장할 노드를 저장하는 리스트
CLOSED: 이미 확장한 노드를 저장하는 리스트

탐색 알고리즘에 따라 정해진 순서로 OPEN에서 확장할 노드를 꺼내 CLOSED로 옮김
확장 결과 생성된 노드를 OPEN의 적절한 위치에 저장

맹목적 탐색

목표노드의 위치와 무관한 순서로 노드 확장 - 소모적

경험적 탐색

문제영역에서 사용할 수 있는 목표노드의 위치와 관련된 겅험적 정보를 사용

탐색의 목적 및 경험적 정보 사용에 따른 탐색방법 분류

맹목적 탐색

깊이우선탐색

• 탐색 방법
  탐색 진행방향인 깊이 방향으로 계속 전진하여 목표를 탐색

• 가장 최근 생성된 노드를 가장 먼저 확장

• OPEN은 스택 구조

• 목표에 도달할 수 없는 경로를 계속 탐색하게 될 수 있음
  -> 깊이 제한을 정할 수 있음

너비우선탐색

• 탐색 방법
  트리의 레벨 순서에 따라 노드를 확장함

• 생성된 순서에 따라 노드를 확장

• OPEN은 큐 구조

해가 존재한다면 출발 노드에서 목표 노드까지 도달하는 최단 길이의 경로를 찾게 됨

균일비용탐색

• 노드 사이의 경로 비용
  • 한 상태에서 다른 상태로 이동하기 위해 필요한 비용

-> OPEN의 노드 중 출발 노드로부터의 경로 비용이 최소인 노드를 선택하여 확장함
-> 최소비용 경로 탐색 가능

힙 자료구조를 사용하면 정렬하는 시간을 줄일 수 있다

CLOSED에 들어있는 노드라면 최단거리이기 때문에 다음 경로에서 제외
OPEN에 존재한다면 비용을 비교해야함