Artificial Intelligence (2) 썸네일형 리스트형 [인공지능] Informed Search 알고리즘 비교 [이 글은 고려대학교 윤수식 교수님 COSE361 강의 중간고사 내용 정리를 위해 작성한 글입니다.] Informed Search란 heuristic한 정보를 바탕으로 하며, goal state에서 얼마나 가까운지를 고려하는 방식이다.1. Greedy Search그리디 알고리즘과 유사하게 그리디 탐색은 goal state에 가장 가깝다고 판단되는 노드를 가장 먼저 방문을 한다.허나 거리가 가깝다고 해서 최적의 해는 아니기 때문에 최악의 경우 DFS와 같이 작동할 수 있다는 문제점이 있다. CompleteDFS와 같이 무한 경로에 빠질 수 있으므로 Complete 하지 않다. Optimal최소의 값을 탐색하지 않으므로 optimal 하지 않다. 1. A* SearchA* search는 실제 path.. [인공지능] Uninformed Search 알고리즘 비교 [이 글은 고려대학교 윤수식 교수님 COSE361 강의 중간고사 내용 정리를 위해 작성한 글입니다.] Uninformed Search란 Heuristic하지 않은, 즉 goal로부터 현재 state가 얼마나 가까운지를 고려하지 않은 모든 Search 알고리즘을 의미한다. 1. Depth-First Search 흔히 알려진 DFS는 깊이를 우선적으로 탐색하며, 스택 구조를 통해 구현된다.Time complexityDFS에서 최악의 경우는 가장 오른쪽 아래의 leaf node에 Goal State가 있는 경우이다.이때는 모든 노드를 탐색해야 하므로 시간 복잡도는 $O\left ( b^{m} \right ) $가 된다. Space complexity반면 Space Complexity의 경우 현재 탐색중인 .. 이전 1 다음
