Whatever floats your boat

이전까지는 탐색공간을 체계적으로 탐색했다. 따라서 문제의 solution까지 도달하는 경로까지도 구할 수 있었다. 하지만 경로가 필요없는 문제도 존재한다. 이럴 때는 다른 알고리즘을 사용할 수 있는데 여기선 Local Search의 Hill-climbing 방식을 알아보도록 하겠다. Local Search and Optimization Local Search는 다음과 같은 특성을 가진다. 다른 state를 기억하지 않고 오직 현재 state만 알고있다. 따라서 stack, queue와 같은 다른 자료구조를 사용하지 않는다. 그리고 위와 같은 특성때문에 Memoryless Search라고 불린다. 인접 state로만 움직인다. 경로를 무시한다. Local Search의 장점 메모리 사용량이 적다. 탐색공간..

지난시간에 Uninform Search을 배웠다. 현재 상태와 목적지의 정보를 갖지않고 상태공간을 탐색을 탐색하였다. Informed Search는 목적지와 현재 상태 정보를 가지고 Goal에 다가가기 좋은 방향으로 탐색한다. (Heuristic 함수 사용) 참고로 Informed Search는 Heuristic Search라고도 불린다. Informed Search 개요 Informed Search는 Uninformed Search의 한계를 보안하기 위해 나왔다. Informed search는 효율성을 향상시키기위해 문제마다 heuristic 함수를 사용하고 다음과 같은 방법들이 있다. Best-first A* 또한 이번글의 마지막 부분에서 heuristic을 만드는 기술도 알아볼 것이다. worst ..

Uninformed Search란 여러가지 문제를 해결하기 위한 탐색 기법 중 하나로 사전정보를 갖지 않고 탐색하는 알고리즘 기법이다. Uninformed Search는 Blind search라고 불리며 Informed Search랑 비교된다. Blind Search라고 불리는 이유는 현재 node에서 Goal node까지의 거리(heuristic value)를 알지 못하기 때문에 Blind Search라고 불린다. 만약 현재 위치에서 Goal node까지의 거리 혹은 heuristic value를 안다면 Informed search라고 한다. Uninformed Search에는 다음과 같은 알고리즘이 있다. Breadth-first Search Depth-first Search Iterative dee..