algo_lec14

Today's Topics

• Approximation algorithms for NP-hard problems
• Approximation algorithm example 1: Traveling Salesman Problem (TSP)
• Approximation algorithm example 2: Bin Packing

---

Handling NP-Hard Problems

NP-Hard 문제는 일반적으로 다항 시간 안에 정답을 찾는 알고리즘이 존재하지 않습니다.

따라서 완벽한 해답 대신, 현실적으로 쓸 수 있는 두 가지 전략이 자주 사용:

 

• Backtracking and branch-and-bound:
  - Explore all solutions, prune unpromising paths.
  - Worst-case time is exponential, but often efficient with good heuristics.

 

• 가능한 모든 해를 탐색하지만,
• 조건을 만족하지 않을 가능성이 높은 경우는 미리 잘라내고(prune) 더 이상 진행하지 않음

• Approximation algorithms: 
  - Do not guarantee optimal solutions.
  - Provide solutions close to optimal within a proven bound.

정답(최적해)을 보장하지 않지만, 최적해에 가까운 결과를 빠르게 구하는 알고리즘

---

 

Approximation Algorithms for NP-hard

NP-Hard 문제는 정답(최적해)을 빠르게 구하기 어렵기 때문에, 최적해에 근접한 결과를 빠르게 구할 수 있는 알고리즘을 사용.

이것이 바로 근사 알고리즘.

 

• An approximation algorithm finds near-optimal solutions efficiently.
• ρ-approximation algorithm:
  - If ρ > 1: opt ≤ appr ≤ ρ × opt
  - If ρ < 1: ρ × opt ≤ appr ≤ opt

---

Approximation Algorithm Example 1: TSP

가능한 한 비용이 적은 경로를 찾는 문제

 

• Traveling Salesman Problem

• known as NP-complete/NP-hard problem
• No polynomial algorithm exists

---

• Euclidean TSP
  • w(u,w) <= w(u,v) + w(v,w)
  • The path from u to w is shorter than the path from u to w through v.
  • For G = (V,E) and arbitrary path (v1,v2,...,vk), w(v1,vk) <= w(v1,v2,...,vk)
• Similarity in spanning tree and Hamiltonian Circuit(HC)
  • Spanning tree has no cycle 스패닝 트리는 트리이므로, 사이클이 없으면서 모든 정점이 연결
  • HC는 모든 정점을 연결하는 사이클이므로, HC에서 어느 하나의 엣지만을 제거하면 스패닝 트리가 됨.
  • MST has polynomial time algorithm such as Prim and Kruskal algorithms while TSP doesn't have it.
  • Thus, let's use MST to find the lower-bound weight sum of HC
• spanning tree 와 Hamiltonian Circuit(HC) 의 유사성

1. Spanning tree 

• 주어진 그래프의 모든 정점을 연결하되, 사이클이 없는 구조
• 간선 수 = 정점 수 - 1
• 대표 알고리즘: Prim, Kruskal
• 다항 시간 내에 최적 해(MST)를 구할 수 있음

---

2. HC, Hamiltonian Circuit

• 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 순환 경로
• 즉, 모든 정점을 포함하고, 간선 수 = 정점 수 (사이클을 구성)
• 이 문제는 NP-complete → 최적해를 다항 시간에 구할 수 없음.

---

중요한 관찰: HC와 Spanning Tree의 구조적 유사성

• 해밀토니안 사이클에서 간선 하나를 제거하면,
  → 사이클이 제거되면서 모든 정점을 연결하는 스패닝 트리가 됨.
• 반대로, MST에 적절한 간선 하나를 더하면 HC 후보가 될 수 있음.

---

결론: MST를 HC 또는 TSP의 하한선으로 사용 가능

• MST는 정점을 최소한으로 연결하는 구조이므로,
  → MST의 총 가중치는 TSP 또는 HC의 최소 경로 비용보다 작거나 같다.

MST weight ≤ TSP or HC weight → mst ≤ opt.

• 따라서 TSP의 최적 해를 추정할 때, MST를 하한선(lower bound) 으로 사용할 수 있다.

---

TSP는 모든 도시(정점)를 정확히 한 번씩 방문하고 다시 출발지로 돌아오는 경로 중에서 총 비용이 최소가 되는 경로를 찾는 문제.
이 문제는 NP-Hard로 분류되어, 최적해를 구하기 위한 계산 시간이 매우 오래 걸릴 수 있다.

Input: G
Output: Approximate solution F

[ 알고리즘 단계 ]

1. MST 구성
   주어진 그래프에서 MST를 만든다.
   Prim 또는 Kruskal 알고리즘을 사용하여 최소 비용으로 모든 정점을 연결.
2. MST를 전위 순회(DFS)
   트리 형태의 MST를 DFS(깊이 우선 탐색) 순서로 탐색한다.
   이 순서를 따라 정점을 방문하면 하나의 경로가 만들어진다.
3. 중복 정점 제거 및 순회 경로 완성
   DFS로 탐색하면서 중복 방문된 정점을 생략하고, 각 정점을 한 번씩만 포함하여 경로를 구성한다.
   마지막에 시작점으로 돌아와 순회 경로를 만든다.

MST 기반 2-approximation algorithm

TSP 문제를 완전히 해결하는 대신, 최적해에 가까운 근사해를 다항 시간 안에 구하는 방법이 사용.
이 알고리즘은 최소 신장 트리(MST)를 기반으로 구성.

• 근사 해의 총 비용은 최적해의 두 배 이내.
• 즉, 최적 TSP 경로의 비용이 opt일 때, 근사 알고리즘이 구한 경로의 비용은 최대 2 × opt를 넘지 않는다.

---

Approximation Algorithm Example 2: Bin Packing

• Problem: Given items with sizes 0 < si ≤ 1, pack them into minimum number of bins (capacity 1).

크기가 0 < s_i ≤ 1인 n개의 물건이 주어졌을 때, 각 상자의 용량이 1일 때,
이 물건들을 가능한 최소 개수의 상자에 나누어 담는 문제.

• NP-Hard 문제로, 최적해를 구하는 것이 어렵다.
• 그래서 근사 알고리즘을 사용하여 빠르게 "좋은 해"를 구한다.

• Next-fit Algorithm:
  - Place each item in the current bin if it fits; otherwise, start a new bin.

 

• 현재 사용 중인 상자에 넣을 수 있으면 그대로 넣고,
• 넣을 수 없으면 새로운 상자를 하나 꺼내서 그 안에 넣는다.

  - Worst-case: uses ≤ 2 × OPT bins.

• 최악의 경우, 사용되는 상자 수는 최적해의 2배 이내

• First-fit Algorithm:
  - Place each item in the first bin where it fits.

 

• 물건을 순서대로 하나씩 보면서,
• 지금까지 사용한 상자 중 가장 먼저 들어갈 수 있는 상자에 넣는다.
• 빈 상자 중에서 앞에서부터 검사하므로 "First-fit"

  - Known to use ≤ 1.7 × OPT + 0.7 bins.
  - Worst-case time complexity = O(n²)

 

• 최악의 경우, 사용 상자 수 (# of bins used) ≤ 1.7×OPT + 0.7
• OPT: optimal solution (min number of bins)

첫 번째 증명 아이디어
First-Fit이 m개의 상자를 사용했다면, 그 중 최소 m-1개는 절반 이상 채워져 있어야 한다.
이유: 만약 절반 이하로 채워진 상자가 2개 이상 있다면? → 두 상자의 물건을 하나로 합쳐서 쓸 수 있으므로, First-Fit 알고리즘은 그 중 하나에 담았어야 함 → 따라서 대부분의 상자들은 절반 초과로 채워져야 한다는 성질이 생김.
시각 예시: 물건 a, b가 각각 용량의 ½ 이하이면 → 같은 상자에 들어갈 수 있음 First-Fit은 이걸 활용하지 못하는 경우가 거의 없음

두 번째 수학적 증명
전제: 모든 물건의 크기 합을 ∑s_i (i=1 to n)이라 하자.
상자의 용량은 1이므로, 최적 해는 이보다 작을 수 없음 → opt ≥ ∑s_i
반면, First-Fit이 m개의 상자를 사용했는데, 그 중 m-1개는 절반 이상 채워져 있다고 가정하면, ∑s_i > (m-1) / 2
정리: m ≤ 2×opt

First-Fit 알고리즘이 어떻게 동작하든, 그가 사용하는 상자 수 m은 항상 m≤2×opt 를 만족한다는 것을 수학적으로 증명.

 

• First-fit Decreasing Algorithm:
  - Sort items in non-increasing order and apply first-fit.
  - Uses ≤ 11/9 × OPT + 0.7 bins.

 

알고리즘 개요

First-Fit Decreasing(FFD)는 Bin Packing 문제에서 널리 쓰이는 근사 알고리즘 중 하나.

 

*FFD는 다음과 같은 순서로 동작:

1. 정렬(Sort)
   모든 물건을 크기(무게) 기준으로 내림차순(non-increasing order) 으로 정렬.
   예: [0.5, 0.4, 0.3, 0.2, 0.2, 0.2]
2. First-Fit 적용
   정렬된 물건들을 순서대로 보면서, 가장 먼저 들어갈 수 있는 상자(bin)에 넣습니다.
   빈 상자가 없으면 새 상자를 시작.

---

알고리즘 특징

• 최적해를 항상 주지는 않음. → BUT. 굉장히 우수한 품질의 해를 빠르게 제공.
• 최악의 경우, Time complexity = O(n^2)
  • 왜냐하면 각 아이템에 대해 이미 존재하는 모든 상자를 확인할 수 있기 때문.

---

근사 품질 보장

• 이 알고리즘은 이론적으로 다음과 같은 근사 보장을 가짐:
  • 사용한 상자 수 ≤ (11/9×OPT)+0.7
  • 여기서 OPT는 최적해(즉, 가장 적은 상자 수)를 의미.

---

 

• 그림은 FFD가 어떻게 동작하는지 시각적으로 보여줌.
  • 객체 리스트: [0.5, 0.4, 0.3, 0.2, 0.2, 0.2, 0.2]
  • 먼저 0.5와 0.4는 한 상자에 들어갈 수 있으므로 첫 상자에 배치.
  • 다음 0.3은 두 번째 상자에 혼자 들어감.
  • 그다음 0.2들 네 개는 남은 공간에 채워지며, 새로운 상자는 필요한 만큼 추가.
  • 마지막 0.2 하나는 따로 남아서 새 상자를 차지.