on
2주차 문제 해결 및 탐색 전략(2-1 이론)
2주차 문제 해결 및 탐색 전략(2-1 이론)
2주차 문제 해결 및 탐색 전략(2-1 이론)
오늘은 인공지능에서 문제를 어떻게 정의하고, 어떻게 풀어내는지에 대해 알아봅시다.
1. 인공지능에서 문제를 정의하기 위해 필요한 4가지 구성요소
1) 초기상태(state)
2) 가능한 행동들(action)
3) 목표를 도달했는가(Goal Test)
4) 경로 비용(path cost)
2. 추상화(Abstraction)
추상화는 모델링을 통해 현실의 실제 문제보다 이해하기 쉽도록 문제를 변환하는 과정입니다.
현실에는 수 많은 경우와 복잡한 상황이 있지만 추상화를 통해 문제를 정의하고 해결하는 것입니다.
3. 예제
1) 루마니아 예제
루마니아 예제는 루마니아의 Arad라는 도시부터 Burcharest까지 가는 경로를 짜는 문제
경로 자체는 매우 많이 있겠지만, 그 중에서 가장 최고의 경로를 찾는 것이 목적이죠.
최고의 경로는 정의마다 다를 수 있지만, 보통 최단 거리를 말합니다.
2) 8-퍼즐
가운데가 비어있는 3x3 표에서 숫자들을 움직여 정해진 순서대로 만드는 문제
4. Tree Search 알고리즘
뿌리(root)를 점점 펼쳐나가면서 해결책을 찾아나가는 과정
뿌리는 데이터 구조에서 제일 꼭대기에 있는 초기 상태를 말합니다.
루마니아 예제에서는 Arad가 뿌리가 되겠죠.
각각의 다른 도시들은 state가 되는 노드입니다.
각각의 액션은 나무의 가지를 생성하게 됩니다.
state를 펼치는 것은 탐색이라고 부를 수 있고, 탐색을 반복하면 goal state를 찾을 수 있게 됩니다.
아직 펼쳐지지 않은 노드는 Fringe라고 얘기합니다.
이렇게 State 공간을 펼치고 펼치다 보면, 결국 하나의 나무 구조가 되겠죠.
이 알고리즘이 Tree search라고 불리는 이유입니다.
자 그런데 탐색을 하려면 전략이 필요합니다.
전략이란 어떤 순서로 노드를 펼칠 것인지 정의하는 것입니다.
그럼 그 순서는 어떻게 결정될까요?
일반적으로 좋은 전략인지 판단할 때에는 4가지 구성요소가 필요합니다.
5. 전략을 판단하는 4가지 기준(구성요소)
1) 완전성(Completeness) : 이 전략을 사용하면 반드시 해를 구할 수 있는가
2) 시간 복잡도(Time complexity) : 얼만큼의 시간이 걸리는지 (시간 복잡도가 낮을 수록 좋은 전략)
3) 공간 복잡도(Space complextiy) : 얼만큼의 메모리 공간이 필요한지 (공간 복잡도가 낮을 수록 좋은 전략)
4) 최적성(Optimality) : 내가 항상 최적의 해를 구할 수 있는가
문제에 따라서 적절한 전략을 선택하는 것이 중요
6. 탐색전략 1 : Uninformed search (주어진 정보만을 활용해서 탐색을 하는 전략)
* 강의에서는 대표적인 BFS와 DFS만 자세히 설명해 주지만, 저는 궁금해서 나머지 전략들도 찾아봤어요!
1) 너비 우선 탐색(Breadth-first search, BFS)
FIFO(first in first out) 구조
앞에 있는 것을 먼저 큐에 넣고, 그것이 답인지 아닌지 판단 후, 판단이 된 노드는 버려짐
각 줄에 있는 노드들을 큐에 넣고, 그 아래 노드는 그 다음 큐로 들어감
즉, 가로로 한 줄씩 탐색
A랑 B는 벌써 버려진 상태입니다
2) 균일 비용 탐색(Uniform-cost search)
너비 우선 탐색을 변형한 전략입니다.
아래에 있는 노드로 가는데 드는 총 비용을 검사해서 비교한 후, 가장 적은 비용이 드는 노드를 먼저 탐색합니다.
장점은 출발 노드에서 목표 노드까지 최단 길이 경로를 보장할 수 있고, 무한한 루프에 빠지지 않게 해줍니다.
단점은 깊이가 커질수록 필요한 메모리 공간이 기하급수적으로 늘어납니다.
3) 깊이 우선 탐색(Depth-first search, DFS)
LIFO(last in first out) 구조
큐에 들어온 마지막 노드를 먼저 확인 후, 답이 아니면 그 아래 줄의 노드들이 들어감
더 이상 아래에 있는 노드가 없으면, 마지막에 추가되는 것이 없기 때문에 다음 노드로 넘어감
즉, 세로로 한 줄씩 탐색
4) 깊이 제한 탐색(Depth-limited search)
DFS와 같은 전략이지만, 깊이에 제한을 둡니다.
깊이가 매우 깊다면 DFS 전략을 사용했을 때 드는 시간과 비용이 엄청나겠죠.
이런 점을 개선한 전략이 깊이 제한 탐색입니다.
하지만 설정한 깊이 아래에 목표가 있다면, 답을 찾을 수 없겠죠.
5) 반복적 깊이심화 탐색(Iterative deepening search)
깊이 제한 탐색에서 제한을 조금씩 늘려가는 방식입니다.
2번의 균일 비용 탐색과 유사하다고 볼 수도 있습니다.
전략 판단 기준을 바탕으로 비교해 본 BFS와 DFS
O는 복잡도를 나타내는 notation 중 하나
b는 한 노드에서 펼쳐질 수 있는 최대의 숫자
d는 목표가 있는 깊이, m은 탐색을 하게 될 깊이
다음 시간에는 Heuristic search에 대해 배운다고 하네요.
여러 가지 다른 정보를 활용하여 Uninformed search보다 훨씬 쉽게 답을 찾을 수 있다고 합니다.
from http://data-learning-jjoshu.tistory.com/5 by ccl(A) rewrite - 2021-12-01 18:00:38