Greedy Approach - Prim's Algorithm

Greedy Approach

: 반복 알고리즘으로써 매번 Step에서 무엇인가 선택을 할 때 목적함수 값을 최대화 하거나 최소화하는 방향으로 선택하는 것

 

결과적으로는 최선의 선택이 되지 않는다.

 

동전을 거슬러 주는 횟수를 최소화 하기 위해선?

동전을 큰 것부터 주자.

1. Selection procedure : 동전의 단위가 큰거부터 체크한다.

2. Feasibiliy check : 조건의 맞는 것을 체크한다. 

3. Solution check : 거스름돈이 완성됐는지 체크한다.

---

Minimum Spanning Tree

undirected graph : 무향 그래프

directed graph : 유향 그래프

 

Tree : Acyclic connected graph : 연결 그래프이면서 싸이클이 없는 그래프

Rooted Tree : 특정한 하나가 Root인 트리

 

Spanning Tree를 표현할 때는 Spanning Tree를 이루는 edge로 표현한다.

매번 step에서 선택할 때 edge를 선택한다.

 

v1에서 출발한다면

v1에서 연결된 edge들 중에서 가장 작은 것을 선택한다. >> v1-v2 선택

 

그 다음 v1, v2에 연결된 edge들 중에서 가장 작은 것을 선택한다. >> v1-v3 선택

 

그 다음 v1, v2, v3에 연결된 edge들 중에서 가장 작은 것을 선택한다. >> v3-v5 선택

그 다음 v1, v2, v3, v5에 연결된 edge들 중에서 가장 작은 것을 선택한다. >> v3-v4 선택

 

Spanning Tree는 모든 Vertex를 포함하면서 Cycle이 없으면 되므로 선택이 끝난다.

 

Tree는

노드가 n개 있다면

엣지는 n-1개 있다.

 

---

어떻게 구현할 것인가?

 

Weight Martix = W[i][j]

 

nearest[i] = vi 와 가장 가까운 Vertex의 번호
distance[i] = vi와 가장 가까운 Vertex의 가중치

i = 1 일 때

분홍색 이라는 것은 트리 안으로 들어온 것이고

흰색 이라는 것은 트리 안으로 아직 들어오지 않은 것이다.

 

distance와 nearest를 어떻게 사용할 것이냐면

각각의 흰색 vertex가 제일 가까운 분홍색 vertex가 무엇인지 기억하고

그리고 그 weight가 얼마인지 기억하는데 사용하는 것이다.

 

그리고 loop이 돌아가고 V2가 선택이 될 것이다.

그러면 V2 도 분홍색이 된다.

 

그 후 남아있는 V3, V4, V5도 제일 가까운 분홍색 vertex가 무엇인지 확인해야 한다.

 

V3를 보자

V3가 현재 기억하는 가장 가까운 분홍색 vertex는 V1으로 기억했는데,

혹시나 가장 가까운 분홍색 vertex가 V2일 수도 있다.

그러나 동점이므로 업데이트할 필요가 없다.

 

V4를 보자.

V4와 가장 가까운 분홍색 vertex(V1,V2)중 가장 가까운 vertex는 V2이다.

그리고 nearest를 V2로 고쳐준다.

 

V5를 보자.

V5와 V2의 거리를 보고 둘다 거리가 무한대이므로 업데이트 하지 않는다. 

 

이제 남아있는 하얀색 Vertex를 업데이트 할 필요가 발생한다. 

 

V3도 분홍색 Vertex가 된다.

그러면

 

 

선택 됐다면 선택됐다는 의미로 (-) 값으로 해준 것이다. 그것이 분홍색이라는 뜻이다.

 

void prim (int n, const number W[][], set_of_edge& F)
{
    int i, vnear;         // 
    int min;             // 
    edge e;                 //
    int nearest[2...n];   // 가장 가까운 정점
    int distance[2...n]; // 가장 가까운 정점과의 거리
    
    F = empty set; // 공집합
    for (i = 2; i<=n; i++){
        nearest[i] = 1;     // v2와 가장 가까운 정점을 v1로 초기화
        distance[i] = W[1][i]; // v1에서 vi까지 가장 가까운 정점과의 거리 저장
    }
    
    repeat (n-1 times){
    
        min = infinity; // min = 이때까지의 경로중 가장 작은 경로
        
        for(i=2; i<=n; i++)
            if(0 <= distance[i] < min){ // v1~vi까지 거리가 min보다 작다면
                min = distance[i];      // v1~vi까지 거리를 min값을 저장, 업데이트
                vnear = i;              // vnear를 현재 업데이트된 i로 대체
            }
        
        e = edge connecting vertices indexed by vnear and nearest[vnear];
        // e = (vnear, nearest[vnear]); 
        
        add e to F;
        distance[vnear] = -1;
        
        for (i=2; i<=n; i++)
            if (W[i][vnear] < distance[i]){
                distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
    }
}
        

---

Greedy Algorithm

동적 프로그래밍과 함께 최적화 문제의 해결에 많이 사용된다.

문제 해결을 위해 데이터를 선택할 때, 그 순간에 가장 최고인 것을 선택한다.

지역적으로는 최적이지만 전체적인 최적은 확신할 수 없다.

알고리즘이 항상 최적해를 주는지 확인이 필요하다.

---

Greedy Algorithm 적용 단계

1. 선택 과정(Selction procdure) : 현재 상태에서 최선인 답을 찾아 해답에 포함한다.
2. 적정성 검사(Feasibilty check) : 새로 결정된 해답들이 적정한지 검사한다.
3. 해답 점검(Solution check) : 새로 얻은 해답들이 최적인지 검사한다.

---

배낭 문제 (Knapsack Problem)

n개의 물건과 배낭이 있다고 가정하자.

각각의 물건에는 무게와 가치가 주어진다.

배낭에 물건을 넣을 때, 그 배낭이 견딜 수 있는 최대 하중이 W라고 가정하자.

 

목표 

: 배낭에 넣을 수 있는 물건의 가치를 최대화하면서 최대 하중 W를 초과하지 않도록 한다.

 

문제의 정의

Wi = 물건 Xi 의 무게

Pi = 물건 Xi 의 가치

A ⊂ S = 물건들의 집합 A가 S의 부분집합이라고 가정하자 

: 배낭문제의 목표 함수

 

 

---

최소비용 신장트리(Minimum Spanning Tree)

 

가중 그래프

: 연결선에 가중치를 부여한 그래프로써 네트워크 라고도 한다.

가중 그래프의 예

: 각 vertex들을 도시라 하고 edge들은 그 도시를 잇는 도로라 했을 때, edge에 할당된 가중치는 각 도로에 대한 교툥량이나 또한 도시 사이의 거리라고 생각할 수 있다.

신장 트리의 비용

: 가중 그래프로부터 신장 트리를 생성하여 그 신장 트리를 구성하는 모든 연결선들의 가중치를 합한 값

 

최소 비용 신장 트리

: 모든 신장 트리들 중에 최소비용을 가진 신장 트리

최소  비용 신장트리를 생성하는 알고리즘

: Prim, Kruskal 알고리즘

---

Prim's 알고리즘

전체 연결선 중에서 가장 작은 가중치를 갖는 연결선을 선택하여 최소비용신장트리에 추가시키고 

정점들은 정점들의 집합 V에 추가

 

다음은 V에 속한 정점들과 인접한 연결선들 중 가장 작은 가중치를 갖는 연결선을 MST에 추가하고

정점 또한 집합 V에 추가

 

이러한 과정을 신장트리의 연결선 개수가 n-1이 될때까지 반복

 

float Prim(int E[][size], float cost[][size], int n, int t[][2])
{
    int near[size],j,k,l;
    let (k,l) be an edge of minimum cost in E;
    float mincost = cost[k][l];   t[1][1] = k;   t[1][2] = 1;

    for (int i=1; i < = n ; i++)  //initialization
        if (cost[i][1] < cost[i][k])  near[i] = 1;
        else  near[i] =k;

    near[k] = near[1] = 0;

    for (i=2;  i< = n-1 ; I++) {
        let j be an index such that near[j]!=0 and 
        cost[j]near[j] is minimum;   t[i][1] = j;   t[i][2] = near[j];
        mincost = mincost + cost[j][near[j]];      near[j] = 0;
        
        for (k=1;  k < = n ; k++)
            if ((near[k] != 0) && (cost[k][near[k[] > cost[k][j]))   
            near[k] = j;
    }
    return(mincost);
}