Search
쉽게 얘기하면 컴퓨터과학에서의 탐색 (search) 알고리즘은 문제를 입력해서 그 문제에 대한 해 (solution)를 얻는 알고리즘이다. 문제를 풀기위해 컴퓨터과학자가 연구하는 대부분의 알고리즘들은 일종의 탐색 알고리즘들이다 (문제해결 (Problem Solving)). 문제를 푸는 가능한 해를 모두 모아둔 집합을 탐색공간 (search space, 상태공간 (State Space)) 라고 부른다. 무정보 탐색 (Uninformed Search) 알고리즘은 탐색공간을 탐색하는 가장 단순하고 직관적인 (intuitive) 방법을 사용한다. 반면에 정보탐색 (informed search, 휴리스틱 탐색 (Heuristic Search)) 알고리즘은 탐색시간을 줄이기 위해 탐색공간의 구조에 대한 지식을 응용하는 휴리스틱을 사용한다.
무정보 탐색 (Uninformed Search) 은 문제의 독특한 성질을 고려하지 않는 알고리즘이다. 따라서 쉽게 구현가능하고, 똑같은 구현방식을 추상화 (abstraction) 해서 넓은 범위의 문제들에 사용가능하다. 문제는 대부분의 상태공간이 매우 크다는 것이며, 무정보탐색 (특히 트리의 경우) 은 작은 크기의 경우에만 합리적인 시간이 소요된다는 것이다. 따라서 탐색시간을 빠르게 하기위해, 때로는 정보탐색 (informed search) 만을 사용한다.
리스트 탐색 (list search) 알고리즘은 탐색 알고리즘중에서 가장 기본적인 것이다. 목적은 어떤 키 (key) 에 의해 집합의 한 요소를 찾는 것이다 (키와 관련된 다른 정보를 포함하는). 이것이 컴퓨터과학에서 일반적인 문제이기 때문에, 이 알고리즘의 계산복잡도는 잘 연구되었다. 가장 쉬운 알고리즘은 선형탐색 (linear search) 으로서 리스트의 각 요소를 순서대로 검사한다. ........ 대부분의 list search 알고리즘, 즉 linear search, binary search, self-balancing binary search trees 와 같은 것들은 주어진 키보다 더 크거나 작은 모든 값을 찾기위해 부가적인 비용이 거의 들지 않도록 확장될 수 있는데, 그것은 range search 라고 불리운다. 그러나 예외적으로 hash tables 은 그러한 탐색을 효율적으로 수행할수 없다.
트리탐색 (Tree search) 알고리즘은 탐색기술의 핵심이다. 트리 (Tree) 가 명시적 (explicit) 이든 암시적 (implicit) 이든 (예를들면 바둑 (Baduk) 에서 처럼) 트리의 노드를 탐색한다. 기본원리는 하나의 노드가 자료구조에서 얻어지고 그 자식들이 검사되어 자료구조에 더해진다는 것이다. 자료구조를 조작하여, 트리는 level 별로 탐색하거나 (너비우선 탐색 (Breadth First Search)) 먼저 leaf node 에 도달하고나서 backtracking (깊이우선 탐색 (Depth First Search)) 하는 등의 다른 순서로 탐색한다. 트리탐색의 다른 예들은 반복적 깊이증가 탐색 (Iterative Deepening Depth-first Search), Depth-limited search, 양방향 탐색 (Bidirectional Search), Uniform-cost search 등이 있다.
정보탐색 (informed search, 휴리스틱 탐색 (Heuristic Search)) 에서는 그 문제에만 독특한 어떤 휴리스틱이 하나의 가이드로서 사용된다. 좋은 휴리스틱 (Heuristic) 은 정보탐색을 드라마틱하게 만들며 어떤 무정보탐색보다도 능가하는 성능을 낸다. 리스트에서는 탁월한 informed list-search 알고리즘은 거의 없다. 가까이에 그 문제에 바탕한 휴리스틱이 있는 hashing function을 가진 hash table 은 가능한 영역이다. 대부분의 정보탐색 알고리즘은 트리에서 사용되며 최상우선 탐색 (Best-first Search), A* 알고리즘 와 같은 것이다. 무정보탐색 알고리즘에서 처럼 정보탐색도 확장되어 그래프 (Graph) 에서 작동할 수 있다.
게임 (Game) 프로그램과 machine planning 과 같은 인공지능 (Artificial Intelligence) 의 다른 유형들은 최소최대 (Mini-max) 알고리즘, search tree pruning, 알파베타 가지치기 (Alpha-Beta Pruning) 과 같은 탐색 알고리즘을 사용하는데 그러한 것을 적대탐색 (adversarial search) 라고 한다.
제약 만족 (constriant satisfaction) 은 제약조건 만족 문제 (Constraint Satisfaction Problem) 를 푸는 탐색의 유형으로서, 하나의 경로를 찾기보다는 단순히 변수에 할당된 값을 찾는 것이다. 그 변수들은 어떤 순서로도 처리될 수 있기 때문에 보통의 트리탐색 알고리즘은 너무 비효율적이다. 제약 문제를 푸는 방법들은 combinatorial search 와 backtracking 를 들 수 있는데, 둘다 제약문제들과 관련된 자유도 (freedom) 을 이용한다.
string search algorithm 는 strings 내에 있는 패턴들을 탐색한다. 이것을 더 효율적으로 만드는 유명한 자료구조는 suffix tree 이다. 유전알고리즘 (Genetic Algorithm) 은 상태공간 (State Space) 을 감소시키기 위한 휴리스틱으로서 진화 (Evolution) 에서 얻어진 아이디어를 사용한다. 모의 담금질 (Simulated Annealing) 은 일종의 확률 (probabilistic) 탐색 알고리즘이다
공짜점심 정리 (No-Free-Lunch theorems) 는 "공짜점심 같은 것은 없다 (there ain't no such thing as a free lunch)"에서 나온 명칭으로서, 모든 수학적으로 가능한 문제에 대해, 각각의 탐색알고리즘이 평균적으로 수행하는 (do on average as well as any other) 이유를 설명한다. 이것은 각 탐색알고리즘에 존재하는 편차 (bias) 때문이며, 알고르즘이 만드는 가정들이 때때로 정확하지 않기 때문이다. 공짜점심 정리는 해당 영역에 사용가능한 지식이 많지 않은 가운데서 사용되는 유전알고리즘 (Genetic Algorithm) 과 모의 담금질 (Simulated Annealing) 과 같은 통상적인 탐색알고리즘에 대한 반박 논리로서 사용된다. (No-Free-Lunch theorems for search) ....... (Wikipedia : Search algorithm)
site :
AI Topics : Web Search AI Topics : Search
Wikipedia : Search algorithm Wikipedia : Web search engine
AI on the Web : Search and Game Playing : Stuart Russell
video :
Innovations in AI and Search : CITRIS : Peter Norbig, 2009/09/02