Route Planner , Graph Search Algorithm, BFS 등 경로계획 총 정리

1. Route Planner 체계 및 문제정의

1) Route Planner란?

• Route Planner는 “출발지에서 목적지까지 이동할 때, 가장 적합한 경로(예: 최단거리, 최소 시간, 최소 비용 등)를 찾는 문제”를 해결해주는 시스템입니다.
• 예를 들어, 네이버 지도나 구글 지도처럼 “현재 위치에서 원하는 목적지까지 어떻게 가야 하는지”를 안내해주는 기능이 바로 Route Planner의 대표적인 예시입니다.

2) Route Planner가 다루는 문제의 특징

1. 목적지(Goal)와 시작점(Initial state)이 존재합니다.
   - 예: 집(시작점) → 회사(목적지)
2. 이동할 수 있는 경로가 여러 개 존재합니다.
   - 예: 도로망, 지하철 노선, 버스 노선 등
3. 각 경로(도로, 지하철, 버스 등)는 연결 정보와 이동 비용(거리, 시간, 요금 등)을 가지고 있습니다.
4. 목표: 정해진 목적지에 도달할 수 있는 최적/가장 좋은 경로를 찾는 것
   - "최적"이라고 하면 보통 최소 비용(최소 거리, 최소 시간)이지만, 상황이나 목적에 따라 다른 기준을 쓸 수 있습니다. 예를 들어, 통행료가 가장 적은 경로나, 막히지 않는 길을 찾는 경로 등을 고려할 수 있습니다.

3) 문제정의 방법

• 그래프(Graph) 형태로 정의:
  • 노드(Node): 교차로, 지하철역, 버스정류장 등
  • 엣지(Edge): 노드 간을 연결하는 도로, 지하철 선로 등
  • 엣지 가중치(Weight): 두 노드 사이를 이동하는 비용(거리, 시간, 요금 등)

결국 Route Planner 문제는 “그래프 상에서 시작 노드에서 목표 노드까지 최적 경로를 찾는 문제”로 정의할 수 있습니다.

---

2. Graph Search Algorithm

1) Graph Search Algorithm이란?

그래프(노드와 엣지로 이루어진 구조)에서 특정 노드를 찾거나, 노드 간의 최적 경로를 찾기 위해 사용하는 알고리즘을 통칭합니다.

• Graph Search Algorithm은 크게 두 가지 범주로 나눌 수 있습니다
  1) Uninformed Search (Blind Search):
  문제 공간에 대한 추가 정보(예: 휴리스틱) 없이, 주어진 구조만으로 탐색
  2) Informed Search (Heuristic Search):
  문제 공간에 대한 추가 정보, 즉 휴리스틱(heuristic)을 이용하여 좀 더 효율적으로 탐색

---

2-1. Uninformed Search (Blind Search)

1) 정의

• Uninformed Search는 문제 공간에 대한 사전 정보가 없거나, 거의 없는 상태에서 가능한 모든 경로를 탐색하거나, 혹은 특정 순서대로 탐색하는 방법입니다.
• “blind search”라고도 불리는데, 그 이유는 ‘다음에 어떤 노드를 탐색해야 하는지’에 대해 사전에 주어진 가이드(추가 지식)가 없어서, 비교적 단순한 규칙에 따라 탐색하기 때문입니다.

2) 대표적인 알고리즘

1. Breadth-First Search (너비 우선 탐색, BFS)

   • 

     
     특징: 시작 노드에서 가까운 노드부터 차례대로(계층적으로) 탐색합니다.
   • 장점: 최단 경로(간선 수가 기준이 될 때)를 가장 먼저 찾을 수 있음.
   • 단점: 탐색 공간이 급격히 커질 수 있음(예: 트리 구조에서 노드가 매우 많을 때).
2. Depth-First Search (깊이 우선 탐색, DFS)

   • 

     
     특징: 한 경로를 끝까지 파고든 뒤(목적지나 막다른 길에 도달할 때까지), 다시 돌아와 다른 경로를 탐색합니다.
   • 장점: 구현이 쉽고, 메모리 사용량이 비교적 적을 수 있음.
   • 단점: 무작정 깊이 들어가버려서 최단 경로를 쉽게 놓칠 수 있음.
3. Uniform Cost Search (균일 비용 탐색)

   • 

     특징: “방문하게 되는 누적 비용(가중치)”이 가장 작은 노드를 우선으로 탐색합니다.
   • 장점: 간선마다 거나 시간 등의 서로 다른 “비용”이 있을 때, 최적 해를 찾을 수 있음.
   • 단점: 여전히 비용을 고려하긴 하지만, 다음 노드로의 이동을 선택할 때 추가적인 휴리스틱은 사용하지 않으므로, 최적경로를 찾지만 탐색 범위가 커질 수 있음.
4. Dijkstra's Algorithm
   • 특징: 주어진 시작 노드에서 다른 모든 노드까지의 최단 경로를 계산합니다.
   • 장점: 모든 노드에 대해 최단 경로를 정확히 계산하며, 결과의 신뢰성이 높음.
   • 단점: 음수 가중치를 가진 그래프에서는 작동하지 않으며, 이를 해결하려면 Bellman-Ford 알고리즘과 같은 다른 방법을 사용해야함. 높은 메모리사용량

3) 요약

• Uninformed Search는 추가 정보를 사용하지 않고, “어떻게 순서대로 검색하느냐”에 따라 탐색 방식을 달리합니다.
• 따라서, 최단 경로를 찾을 수는 있지만, 많은 경우 불필요하게 많은 노드를 방문하게 되는 비효율적인 면이 있습니다.

---

2-2. Informed Search (Heuristic Search)

1) 정의

• Informed Search는 말 그대로 문제 공간에 대한 추가적인 정보(추정치, 가이드라인)를 활용하여 탐색 효율을 높이는 기법입니다.
• 여기서 사용하는 ‘추정치’ 혹은 ‘가이드라인’을 휴리스틱(Heuristic)이라고 부릅니다.
  - 예: 출발 지점에서 목표 지점까지 대략적인 거리, 예상 비용 등

2) 휴리스틱(Heuristic)이란?

• 정확한 비용이 아니라, “대충 이 정도 거리가 남았겠다”라는 식의 추정값입니다.
• 예를 들어, 지도상에서 A라는 도시와 B라는 도시 사이의 직선 거리(Euclidean distance)가 대표적인 휴리스틱이 됩니다.

3) 대표적인 알고리즘

1. Greedy Best-First Search (탐욕적 최적 우선 탐색)

   • 

     특징: “현재 상태에서 목표 노드까지의 추정 거리(휴리스틱)가 가장 작은 노드”를 우선적으로 탐색합니다.
   • 장점: 휴리스틱에 따라 빠르게 목표 지점에 가까운 노드를 확인할 수 있음.
   • 단점: 휴리스틱이 부정확하거나, 탐색 과정에서 최단 경로를 보장하지 못할 수 있음.
2. A* Search
   • 특징: 현재까지의 누적 비용(g값) + 휴리스틱(h값) = f(n)을 최소화하는 방향으로 탐색합니다.
   • 공식: f(n) = g(n) + h(n)
     • g(n): 시작 노드에서 n번 노드까지의 실제 누적 비용
     • h(n): n번 노드에서 목표 노드까지의 추정 비용(휴리스틱)
   • 장점: 휴리스틱을 잘 설계하면 최단 경로를 가장 빠르게 찾을 수 있는 강력한 알고리즘입니다.
   • 단점: 휴리스틱이 부정확하거나 너무 크게 잡히면, 비효율적인 탐색이 될 수 있음(최적해 보장을 위해서는 휴리스틱이 낙관적이어야 한다는 조건이 필요).

4) 요약

• Informed Search는 휴리스틱(문제 공간에 대한 추가 정보)를 이용하여 불필요한 경로를 덜 탐색하고 효율적으로 최적 경로를 찾습니다.
• 잘 설계된 휴리스틱이 있으면 매우 빠르게 최적해를 탐색할 수 있으나, 휴리스틱 설계가 어렵거나 부정확하면 탐색 효율이 크게 떨어질 수 있습니다.

---

실생활 예시로 마무리하기

• 네비게이션:
  • “네비게이션이 목적지까지 경로를 계산할 때, 교통 상황이나 평소 도로 속도, 거리 등의 정보를 참고”하는 것이 Informed Search의 예시입니다.
  • 단순히 지도의 도로만 보고(추가 정보 없이) 가능한 모든 경로를 찾아보는 것은 Uninformed Search와 유사하겠지만, 실제로는 교통량(휴리스틱), 과거 데이터 등을 이용해 더 빠르게 최적 경로를 찾아냅니다