인공지능 강의 2화 :: (깊이우선, 너비우선, 균일비용) 탐색

인공지능 강의 2화를 보며 배운내용

 

들어가기전 용어 탐구

• 상태묘사: 풀고자 하는 문제의 상태를 컴퓨터로 처리하기 위한 자료구조로 표현
• 연산자: 어떤 상태 => 다른 상태로 변환하는 도구. 변환 테이블, 변환 함수로 구현
• 상태공간: 정의된 연산자의 집합으로 초기상태로부터 얻을 수 있는 목표상태의 집합으로, 그래프로 표현 가능
• 맹목적 탐색: 목표 노드에 대한 정보를 사용 X, 정해진 순선에 따라 탐색
• 경험적 탐색: 목표 노드의 위치와 경험적 정보를 사용하는 탐색
• 깊이우선 탐색: 탐색 진행방향/깊이방향을 목표로 탐색
• 너비우선 탐색: 트리 레벨 순서에 따라 노드를 확장하여 탐색
• 균일비용 탐색: 출발 노드로부터 경로 비용이 가장 작은 노드를 먼저 선택하여 검사하고 확장하는 탐색

 

문제풀이에 사용될 수 있는 전략

=> 알고리즘을 잘 만들어 사용한다.

하지만 알고리즘이 만들어지기 어려울 땐?

• 시행착오
• 경험적 방법
• 통찰

 

문제 상태를 컴퓨터로 표현

상태

초기상태 => 목표상태

 

연산자

변환 테이블

입력 상태묘사에 대한 출력 상태묘사를 리스트 작성

 

일반화된 변환 규칙(변환 함수)

상태묘사를 변화시키는 함수를 작성

 

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

• 상태묘사/초기상태 정의
• 연산자 정의
• 목표상태 정의

 

상태공간에서의 문제풀이

초기상태 => 목표상태에 도달할 수 있는 연산자 찾는 것

 

탐색 과정

정해진 기준에 따라 노드를 선택

선택된 노드(상태)에 적용할 수 있는 모든 연산자로 모든 후계노드(후계상태)를 생성

=> 노드의 확장

후계노드에 부모노드를 가리키는 포인터를 첨부

=> 탐색 성공 후 풀이 경로를 알 수 있게 해준다.

 

목표노드가 있는지 검사

원하는 목표를 찾지 못했으면 정해진 기준에 따라 다음 노드 선택해서 탐색 과정 반복

 

OPEN: 확장할 수 있는 노드

CLOSED: 이미 확장한 노드

노드 확장했다면

OPEN => CLOSED로 노드를 옮겨서 저장

 

탐색 방법

맹목적 탐색(bliind search)

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

엄청 소모적인 탐색을 할 가능성이 높다

 

경험적 탐색(heuristic search)

목표노드의 위치와 관련된 경험적 정보 사용

경험적 정보: 항상 옳은 것은 아니지만, 개연성이 많은 경우 잘 맞는 정보

 

맹목적탐색 종류

깊이우선, 너비우선, 균일비용

 

깊이우선 탐색

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

OPEN은 스택 구조

목표에 갈 수 없는 경로를 계속 탐색하게 될 수 있다.

=> 깊이제한(depth bound)을 정할 수 있다.

깊이제한에 도달하거나, 진행할 경로가 없을 경우 이전 상태 중 다른 경로를 탐색

 

너비우선 탐색

트리의 레벨 순서에 따라 노드 확장

=> 너무 많은 노드를 확장하기도 한다.

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

OPEN은 큐 구조

해가 존재한다면 출발노드에서 목표노드까지 최단 길이 경로를 찾는 것을 보장

 

균일비용 탐색이란?

노드 사이의 경로비용

한 상태 => 다른 상태로 이동할 때 필요한 비용

OPEN의 노드들 중 출발노드로부터 경로비용이 최소인 노드를 선택해서 확장

최소비용을 탐색할 수 있는 탐색방법

 

비용이 적은 노드를 찾을 때 정렬대신 사용할 수 있는 방법?

heap과 같은 자료구조 사용