그리디 알고리즘 - 최단 경로, 배낭문제

*본문은 <컴퓨팅 사고력 향상을 위한 문제해결과 알고리즘>(성균관대학교 출판부, 2017)을 참고하여 작성되었습니다.

 

그디리 알고리즘이란 단어 뜻 그대로 '탐욕적' 문제해결 방법에 해당한다. 즉, 주어진 문제 상황에서 최선의 답을 선택하는 방식으로, 선택할 때마다 가장 좋은 방법을 선택하여 답을 찾아가는 것이다. 그러나 이 알고리즘은 데이터 간의 관계를 고려하지 않고 매 순간마다 최선의 선택을 적용하기 때문에 근시안적으로 의사 결정을 내리는 문제 해결 방안이다.

그리디 알고리즘은 전체 문제에 대한 완벽한 최적의 해결책을 보장하지 못하는 특성 때문에 다음과 같은 특정 문제 해결에 적용하는 것이 가능하다. 현재 단계의 선택이 다음 선택에 전혀 무관하며, 매 단계 선택된 최적의 해결 방안이 전체 문제해결의 최적화로 이어지는 경우에 적합한 알고리즘이다.

이 알고리즘은 문제를 풀 방법이 떠오르지 않아 단순하게 문제풀기(brute force)를 적용하려 했으나 이 방법이 너무 오래걸릴 경우 차선으로 적용할 수 있는 방법이다.

장점은 빠른 계산 속도다. 단점은 모든 경우에 최적해를 보장하지 못한다는 점이다.

1. 최단 경로 문제

이 문제는 그리디 알고리즘이 적용되는 대표적인 문제 중 하나로 다익스트라 알고리즘이라고 한다. 가중치가 있는 그래프에서 한 특정 정점에서 다른 모든 정점으로까지의 최단 경로를 구하는 문제이다.

조건: 그래프가 주어지고 시작점이 정해져야 함. 가중치가 양수인 경우에만 적용 가능.

이해할 때 참고한 자료: https://hsp1116.tistory.com/42

코드:

from collections import defaultdict

class Graph:
    def __init__(self):
        self.vertexs = set()
        self.edges = defaultdict(list)
        self.distances = {}

    def add_vertex(self, value):
        self.vertexs.add(value)

    def add_edge(self, start, destination, distance):
        self.edges[start].append(destination)
        self.edges[destination].append(start)
        self.distances[(start, destination)] = distance
        self.distances[(destination, start)] = distance

    
    def dijsktra(graph, start):
        visited = {start:0}
        path = {}

        nodes = set(graph.vertexs)

        while nodes:
            shortest_node = None
            for node in nodes:
                if node in visited:
                    if shortest_node is None or visited[node] < visited[shortest_node]:
                        shortest_node = node

            if shortest_node is None:
                break

            nodes.remove(shortest_node)
            present_weight = visited[shortest_node]

            for edge in graph.edges[shortest_node]:
                weight = present_weight + graph.distances[(shortest_node, edge)]
                if edge not in visited or weight<visited[edge]:
                    visited[edge] = weight
                    path[edge] = shortest_node

        return visited, path

2. 배낭 문제

 최적화가 요구되는 문제에 해당하며, 정해진 무게만 담을 수 있는 배낭에 물건 가치의 합이 최대가 되도록 하는 문제다. 물건을 쪼갤 수 있는 분할 가능 배낭 문제와 물건을 쪼갤 수 없는 0-1 배낭 문제가 있다. 전자는 그리디 알고리즘에 해당하며, 후자는 그리디 알고리즘으로 최적해를 찾지 못할 수도 있다.

def select_item(capacity, weights, values):
    value = 0.

    # zip은 같은 index의 원소끼리 튜플 형태로 반환. ex: (values[0], weights[0])
    valuePerWeight = sorted([[v/w, w] for v,w in zip(values, weights)], reverse=True)
    while capacity>0 and valuePerWeight:
        maxitem = 0
        idx = None
        # enumerate는 (arr's idx, arr's value)형 튜플 반환
        for i, item in enumerate(valuePerWeight):
            if item[1]>0 and maxitem<item[0]:
                maxitem = item[0]
                idx = i

        if idx is None:
            return 0.

        v = valuePerWeight[idx][0]
        w = valuePerWeight[idx][1]

        if w <= capacity:
            value += v*w
            capacity -= w
        else:
            if w>0:
                value += capacity*v
                return value
        valueperweight.pop(idx)

    return value


if __name__ == "__main__":
    n = 6
    capacity = 10
    values = [52,25,24,15,70,12]
    weights = [4, 2.5, 3, 1, 3.5, 1.5]
    opt_value = select_item(capacity, weights, values)
    print("{:.2f}".format(opt_value))