Greedy기법(최단 경로, 최소 신장 트리)

Algorithmday_2 정리 (2021.11.29 월요일)

욕심쟁이 기법(Greedy Method) 이어서....

• 최적 대합을 구성할 수 있는 집합을 만들기 위해 필요한 원소들 각 단계마다 하나씩 선택해 나가는 방법
• 선택을 하는 매 순간마다 현재 상태에서 가장 좋아보이는 원소를 선택하는 전략
• 최적의 해를 찾는 전형적인 방법
• 즉, 각 순간 지역적으로 가장 좋아 보이는 선택이 모여 최종적으로도 가장 좋을 것이라 생각하기 때문에 나온 기법
• 최적화 문제를 해결할 수는 없지만 많은 경우의 문제에 적용 가능

욕심쟁이 기법 적용 예(이어서....)

• 최단 경로 문제(Dijkstra의 최단 경로 알고리즘)
  • 하나의 출발점에서 모든 종착점으로의 최단 경로를 찾는 문제
  • 네트워크에서 하나의 시작 정점에서 모든 다른 정점까지 최단경로를 찾는 알고리즘
• 최소 비용 신장 트리(Prim 알고리즘, Kruscal 알고리즘)
  • MST(Minimum Spanning Tree)
  • 트리를 구성하는 간선들의 가중치를 합한 것이 최소가 되는 신장트리
  • 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 신장트리
  • 응용
    • 도시들을 모드 연결하면서 도로의 길이가 최소가 되도록 하는 문제
    • 단자들을 모두 연결하면서 전선의 길이가 최소가 되도록 하는 문제
    • 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
    • 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 하는 문제

최단 경로 문제(Dijkstra의 최단 경로 알고리즘)

• 하나의 출발점에서 모든 종착점으로의 최단 경로를 찾는 문제
• 네트워크에서 하나의 시작 정점에서 모든 다른 정점까지 최단경로를 찾는 알고리즘
• 집합 S
  • 시작 정점 V로 부터 최단 경로가 이미 발견된 정점들의 집합
• distance 배열
  • 최단 경로를 알려진 정점만을 통하여 각 정점까지 가는 최단 경로의 길이
  • 매 단계에서 가장 distance 값이 적은 (최적의)정점을 S에 추가

프림(Prim)의 알고리즘

• 한번에 하나의 간선을 선택하여 최소 비용 신장 트리 T에 추가
• 구축 전 과정을 통해 하나의 트리만을 계속 확장
• 이 과정은 트리가 n-1개의 간선을 가질 때 까지 계속

크루스컬(Kruscal)의 알고리즘

• 한번에 하나의 간선을 선택하여 최소 비용 신장 트리 T에 추가
• 비용이 가장 적은 간선을 선정하되, 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 추가
• 비용이 같은 간선들을 임의의 순서로 하나씩 추가