경로 탐색 알고리즘

너비 우선 탐색

너비 우선 탐색은 그래프를 탐색하는 알고리즘이다. 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드를 광범위하게 탐색한다.

우선 두 노드 사이에 경로가 있는지 확인하고, 그 사이의 최단 경로를 결정한다.

너비 우선 탐색은 기본적으로 그래프를 층 별로 탐색하는데, 0층에서 시작하며 다음 층으로 이동하기 전에 해당 층의 모든 노드를 방문할 때까지 수평으로 이동한다.

즉, 한번 거친 노드를 저장한 후 다시 꺼내는 선입 선출 원칙으로 탐색한다. 주로 큐 데이터 구조로 구현하는 편이다.

깊이 우선 탐색

깊이 우선 탐색도 그래프를 탐색하는 알고리즘이다. 이는 시작 노드와 집접 연관된 하위 노드의 끝까지 탐색한 후 다음 하위 노드를 탐색하는 방법이다.

0층에서 시작하여 하위 노드가 없을 때까지 하위노드를 차례로 탐색한다. 탐색이 끝나도 원하는 노드에 도달하지 못했으면 1층으로 되돌아가 다음 노드에서 반복한다.

너비 우선 탐색이 같은 층의 모든 노드를 탐색한 후 다음 층을 탐색한다면, 깊이 우선 탐색은 경로 하나의 모든 층을 탐색한 후 다음 경로의 모든 층을 탐색한다.

깊이 우선 탐색을 구현할 때는 보통 재귀 호출이나 스택을 명시하는 방법을 사용한다.

백트래킹

백트래킹은 모든 경우를 다 탐색해 해답을 찾는 제어 알고리즘이다. 어떤 규칙으로 정해진 해답을 찾지 못하면 처음으로 돌아와 다른 규칙으로 문제의 해답을 찾는다.
보통 트리 데이터 구조에서는 깊이 우선 탐색과 너비 우선 탐색을 이용해 백트래킹을 실행한다.

데이스크라 알고리즘

데이스크라 알고리즘은 가중 그래프에서 동작하고 그래프의 노드 하나에서 다른 노드까지의 최단 경로를 찾는다. 그래프의 가중치를 비용(cost)라고 하며, 이 비용이 음수가 아니여야 한다.

시작점인 노드에 비용을 0으로 설정하고 다른 노드에는 무한대의 비용을 할당한다. 시작점에서 이동할 수 있는 인접한 노드들의 비용을 계산하고, 비용이 최소인 노드를 경로의 일부로 선택한다.

선택한 노드를 기준으로 다시 인접한 노드의 비용을 계산한다. 즉, 목표에 도달할 때까지 한 번에 하나의 경로씩 계속 반복해 계산하며 각 노드까지의 최단 경로를 찾는 것이다.

데이스크라 알고리즘은 강력하지만, 알고리즘이 탐색하는 공간에 대한 정보가 없어서 블라인드 탐색 또는 무정보 탐색이라 알려진 동작을 수행하는 데는 많은 시간과 자원을 소비하는 한계점이 있다.

하지만 장점이 뚜렷해 네비게이션 서비스에서 많이 사용하는 알고리즘이기도 하다.

데이스크라 알고리즘을 개선한 알고리즘도 여럿 있는데, 그중 벨먼-포드(bellman-ford) 알고리즘은 그래프에서 최단 경로를 찾는데 이용된다.

다른점으로는 벨먼-포드 알고리즘은 가중치가 음수인 에지를 갖는 그래프에서도 동작한다.

A*(A star) 알고리즘

로봇 공학과 인공지능에 대해 관심이 증가하며 주목받는 알고리즘이다. 노드 사이의 최단 경로를 찾는다.

A* 알고리즘은 휴리스틱 알고리즘의 범주에 속한다. 휴리스틱 알고리즘은 확률론을 토대로 문제의 대략적인 해결책을 제공한다. 최적의 해결책을 제공하지는 않지만, 휴리스틱은 완벽한 논리가 아니라 사람의 직감으로 판단하는 영역을 구현하는 방법이다.

데이스크라 알고리즘의 접근법과 탐색할 때마다 최선의 휴리스틱을 찾아 그에 따라 노드를 탐색하는 최선 우선 탐색이라는 알고리즘의 요소를 결합하여, 전체 순회 비용이 가장 낮은 경로를 선택한다.

A 알고리즘을 사용하려면 우선 문제를 그래프로 나타내야 한다. A 알고리즘은 시작 노드에서 인접 노드로 이동하는 비용을 계산하고 목표 노드까지의 예상 비용을 계산한다.

계산이 끝나면 인접 노드 중 비용이 가장 낮은 노드를 선택하고, 선택된 노드를 탐색이 완료된 것으로 간주한다. 이 과저을 목표노드에 도달할 때까지 반복한다.

데이스크라 알고리즘이 그래프에서 가능한 모든 경로를 탐색하는데 비해 A* 알고리즘은 어림짐작한 최단 경로의 비용이 실제 최단 경로의 비용에 가까울 수 있어 효율적이다. 비용계산에 실패할 수 있지만 최단 경로를 찾는 것이 보장 된다.

군집화 알고리즘

군집화 알고리즘은 분류 시스템과 머신러닝 시스템에서 널리 사용딘다.

K-평균 알고리즘

데이터 구조의 특성 속성, 예를 들어 이질성등을 사용하여 데이터를 분류하는 그래프 군집화에 사용된다.데이터를 분류하여 관련된 요소끼리 묶는 동작을 군집화라고 하는데 데이터를 군집화하려면 군집 분석을 수행하는 알고리즘을 데이터 요소에 적용해야 한다.

데이터 군집화에는 계층형 군집화와 분할형 군집화가 있다. K-평균 알고리즘은 분할형 군집화에 해당하는데, n차원 좌표계에서 유클리드 거리를 기반으로 'K'개의 평균을 찾는 알고리즘이다.

K-평균 알고리즘은 분류 시스템뿐 아니라 머신러닝의 비지도 학습 시스템에서도 사용된다.

머신러닝

기본적으로 컴퓨터를 도구로 활용하여 데이터를 통계적으로 분석한 후 의사 결정이나 예측을 도출한다. 머신러닝 시스템은 이를 위해 먼저 대량의 정보를 수집하여 원하는 정보로 변환한다.
변환한 데이터로 머신러닝 알고리즘을 학습시키는데 사용하고, 최종적으로는 학습을 통해 만든 머신러닝 알고리즘을 바탕으로 문제를 해결한다.

머신러닝 시스템이 분류한 데이터 세트를 통해 학습하는 것을 지도 학습이라고 하고, 분류되지 않은 데이터 집단을 갖고 결과를 특정할 수 없는 분류를 수행하는 것을 비지도 학습이라고 한다.
또 이전에 수행한 동작의 피드백을 통해 학습을 지속함으로써 시간이 지남에 따라 성능이 향상되는 강화 학습도 있다.

신경망

신경망은 생명체에 존재하는 신경 세포망을 뜻한다. 인공 시경망은 생명체의 뇌를 모방하여 고안되었다. 신경망에서 각 신경 세포는 앞 뒤 계층의 모든 신경세포와 연결되어 있다.
인공 신경망에서는 이러한 신경 세포를 노드 또는 유닛이라 부르고, 일반적으로 입력층, 은닉층, 출력층으로 구성된다.

입력층은 정보를 받아 네트워크에 전달하며, 은닉층을 연산이 이루어진다. 출력층에서도 연산을 수행할 수 있고 신경망의 외부로 데이터를 전달한다.

네트워크 내의 데이터 흐름을 기반으로 하는 피드포워드 신경망이 있는데, 은닉층이 없는 단층 퍼셉트론과 여러개의 은닉층을 갖는 다층 퍼셉트론으로 구분할 수 있다.

딥러닝

딥러닝 시스템은 머신러닝 시스템의 하나로 인공 신경망을 활용해 머신러닝을 수행한다. 인공 신경망이 계층형 구조이므로 딥러닝 시스템은 비선형 학습을 허용한다는 특징이 있다.
딥러닝 이론에는 합성곱 신경망, 생성적 적대 신경망, 순환 신경망 등이 있다.