지도 서비스로 길을 알아보자

• 지도 서비스 역시 경로 검색 알고리즘을 사용한다
• 지도 서비스를 이용하면 출발지에서 목적지까지의 경로를 바로 알아볼 수 있지만 서비스의 따라서 같은 조건으로 검색해도 경로가 다른 것을 알려주는데 이는 서비스 마다 경로 검색 알고리즘이 다르기 때문이다.

1. 사람에겐 쉽고 기계는 어려운 '경로 알고리즘'

경로 검색이란

• 출발 지점에서 도착 지점에 도달하기 까지의 경로(루트나 길)를 발견하는 처리를 의미
• 경로 여러개 있을 땐 조건에 맞는 경로를 찾아야 하며 다양한 상황에서 활용 된다
• 가장 비용이 적은 경로를 최단 경로라 하며 이때 비용은 시간, 거리, 횟수, 에너지 등의 물리량 의미
• 여러개 비용이 관련되거나 비용이 시간에 따라 변할 때 최단 거리 경로 구하는 알고리즘 복잡해짐
• 뿐만 아니라 비용이 두 번째, 세 번째인 경로를 검색하는 것도 매우 수준 높은 알고리즘 필요

경로 검색 돕는 그래프 이론

• 그래프는 노드 집합과 엣지 집합을 말하며 결합 구조를 표현하는 모델이므로 노드를 두는 장소 또는 엣지가 직선이지 곡선인지는 고려하지 않음
• 엣지에서 방향성이 있는 그래프를 유향 그래프, 없는 그래프를 무향 그래프라 부르며 방향성 그래프에서 방향을 나타내는 엣지를 화살표로 표현
• 이웃한 노드를 연결한 선은 경로로 경로 검색에서 그래프로 해결한다는 건 출발 지점에서 도착 지점까지 가장 비용이 적은 경로 발견하겠다는 뜻

경로 검색 방법

• 경로 검색 시 시작 노드에서 도착 노드까지 가는 경로의 경우의 수를 다 구하는 방법이 있지만 여기에 엣지 자체에 할당된 비용을 고려해서 가장 적게되는 경로를 골라야한다.

노드나 엣지의 갯수 증가

• 노드나 엣지 개수 증가 시 경로 개수 함께 증가

최단 경로 구하는 데이크스트라 알고리즘

• 가까운 문제부터 해결하고 해결된 결과를 바탕으로 다음 문제를 해결한ㄴ다는 생각으로 최단 거리(최소 비용)와 경로를 찾아 나감

데이크스트라 사고 방식

1> 시작 노드에서 시작 노드로 가는 최단 경로 조사로 시작
2> 시작 노드와 인접한 노드를 조사하는데 최소 비용이 할당된 노드까지로 향하는 최소 비용을 확정 지음
3> 마찬 가지로 같은 작업이 반복

=> 정리하면 데이크스트라 알고리즘은 다음과 같은 작업을 반복해 최단 경로를 구함

1. 시작 노드 0으로 정의
2. 정의 하지 않은 노드 중 비용이 가장 적게 드는 노드를 찾아 비용을 확정
3. 비용 확정한 노드의 경로 체크, 확정 노드까지 비용 엣지 비용을 합친 결곽가 현재 노드 값보다 작으면 갱신

2. 알고리즘의 난적 '조합적 확산'

조합적 확산이란

-경로 검색 같은 알고리즘 설계 시 주의해야할 점이 조합적 확산

• 노드의 수가 많은 경우 단순하게 해결하려다 입력 조합 개수 뿐만 아니라 출력 조합의 개수도 커지는 문제가 발생하여 현실적인 시간 내 끝내기 어려워질 수 있다.
• 효율적인 알고리즘을 찾아낼 수 만 이다면 모든 문제를 열거 했을 때 조합적 확산이 일어날 가능성이 있는 문제도 바로 해결 가능한데 그 예로 도널드 커누스가 개발한 Simple Path 알고리즘이 있다.