내가 공부하기 위한 공간 - [알고리즘] 17 - 근사해(외판원, 정점커버, 통채우기)

[근사 알고리즘]

정의 : 최적해 대신 근사해를 구하는 것

• 최적해 찾는 시간이 불가능에 가까울 때 사용
• 근사비율이 1에 가까울수록 최적해에 가까움(근사비율 = 근사해/최적해)
• 보통 근사비율의 최적해는 간접최적해로 대신함

 

 

[외판원]

• 무방향, 경유하는 것보다 직유가 짧음을 전제

MST를 이용하여 근사해를 구함

1. MST에서 모든 정점을 방문하여 돌아오는 순서를 구함
2. 순서를 적은 숫자에서 중복되는 숫자들을 제거
3. 남은 숫자들이 외판원의 근사해

 

MST가중치의 합을 간접 최적해

근사비율은 2이하(삼각 부등식 조건에 의해)

 

<유사코드>

Input: 그래프 G(V, E), 각 간선의 비용(cost)

1. MST = MinimumSpanningTree(G)  # 최소 신장 트리 구하기

2. 경로 = []
3. 방문한 = set()

4. function DFS(u):
     방문한.add(u)
     경로.append(u)
     for each vertex v adjacent to u in MST:
         if v not in 방문한:
             DFS(v)

5. DFS(임의의 시작 정점)

6. 경로.append(시작 정점)  # 사이클 완성

7. return 경로

 

 

[정점커버]

• 무방향 전제

모든 간선을 덮는 정점들의 집합

ex)

정점 : {A, B, C}

간선 : {(A, B), (B, C)}

답은 {B}, {A, C}

 

알고리즘(2가지)

1. 차수가 높은 정점 우선
2. 에지를 기준으로 선택

• 매칭 : 정점들이 중복되지 않는 에지들의 집합
• 극대매칭 : 매칭을 더이상 추가할 수 없는 집합
• 최대매칭 : 극대매칭 중 매칭이 가장 많은 집합
• 극대 매칭을 근사 최적해로 사용
• 최대매칭으로 근사해를 구함

 

<유사코드>

Input: 그래프 G = (V, E)

1. C = empty set  # 정점커버 집합
2. M = empty set  # 매칭 집합
3. E' = E.copy()  # 간선 집합 복사

4. while E' is not empty:
     pick any edge (u, v) from E'
     M.add((u, v))
     C.add(u)
     C.add(v)
     
     # E'에서 u 또는 v와 연결된 모든 간선 제거
     for each edge e in E':
         if u in e or v in e:
             E'.remove(e)

5. return C

 

[통채우기]

용량이 C인 통에 N개의 물건을 최소 통의 개수로 물건을 모두 담는 문제

 

알고리즘(4가지)

1. 최초적합 : 첫 통부터 채우기
2. 최선적합 : 가장 좁은 통부터 채우기
3. 최악적합 : 가장 넓은 통부터 채우기
4. 다음적합 : 직전통만 고려하여 채우기

 

최적해는 전체물건합/C,

1,2,3에서 근사해 : 2*최적해>=근사해

4에서 근사해 : 2*최적해>근사해

즉 비율은 2이하

 

<유사코드>

// 최초
Input: 아이템 리스트 items, 통 용량 C
Bins = empty list

for item in items:
    placed = False
    for bin in Bins:
        if bin.remaining_capacity >= item:
            bin.add(item)
            placed = True
            break
    if not placed:
        new_bin = create_bin(C)
        new_bin.add(item)
        Bins.append(new_bin)

return number_of_bins_used = len(Bins)

// 최선
Input: items, C
Bins = empty list

for item in items:
    # 가장 적은 남은 공간을 갖는 통 찾기 (item이 들어갈 수 있는)
    best_bin = None
    min_space_left = C + 1

    for bin in Bins:
        if bin.remaining_capacity >= item and bin.remaining_capacity - item < min_space_left:
            best_bin = bin
            min_space_left = bin.remaining_capacity - item

    if best_bin is not None:
        best_bin.add(item)
    else:
        new_bin = create_bin(C)
        new_bin.add(item)
        Bins.append(new_bin)

return len(Bins)

// 최악
Input: items, C
Bins = empty list

for item in items:
    # 가장 많은 남은 공간을 갖는 통 찾기 (item이 들어갈 수 있는)
    worst_bin = None
    max_space_left = -1

    for bin in Bins:
        if bin.remaining_capacity >= item and bin.remaining_capacity > max_space_left:
            worst_bin = bin
            max_space_left = bin.remaining_capacity

    if worst_bin is not None:
        worst_bin.add(item)
    else:
        new_bin = create_bin(C)
        new_bin.add(item)
        Bins.append(new_bin)

return len(Bins)

// 다음
Input: items, C
Bins = empty list
current_bin = create_bin(C)
Bins.append(current_bin)

for item in items:
    if current_bin.remaining_capacity >= item:
        current_bin.add(item)
    else:
        current_bin = create_bin(C)
        current_bin.add(item)
        Bins.append(current_bin)

return len(Bins)