Dynamic Programming(2)

모든 정점 간의 최단 경로(shortest path)

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 유형
  • 단일 출발점 최단 경로 → 하나의 특정 정점에서 다른 모든 정점으로의 최단 경로

  • 모든 정점 간의 최당 경로 → 모든 조합의 두 정점 간의 최단 경로

    → 플로이드 알고리즘

플로이드 알고리즘

• 동적 프로그래밍 방법 적용
• 가정 → 가중치의 합이 음수인 사이클이 존재하지 않음

• 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서

  V

  까지인 경로까지 하나씩 범위를 늘려 가면서 모든 정점 간의 최단 경로를 한꺼번에 구하는 알고리즘

• 가중 그래프를 인접 행렬로 표현. *즉 테이블로 표현

• G=(V,E),

  V

  =n

  • D(i,j,0)

    → 정점 i에서 정점 j까지 경유하는 정점 없이 간선으로 직접 연결된 경로의 길이

  • D(i,j,k)

    → 정점 i에서 정점 j까지 경로 중에서 정점 1부터 k까지의 정점만을 경유할 수 있는 최단 경로의 길이

• 알고리즘

    Floyd (G) {
    // D(i,j,0)
    D[][] ← 그래프를 인접 행렬로 초기화;
    D(i,j,0)=d(0) =w ij ij
     D(i, j,k)=d(k) ij
     // D(i,j,k)
    for (k=1부터 |V|까지) //경유하는 정점
    	for (i=1부터 |V|까지)//시작 정점 
    		for (j=1부터 |V|까지)//끝 정점
    			if ( D[i][j] > D[i][k] + D[k][j] )
    					D[i][j] = D[i][k] + D[k][j];
    return D[][]; }
  

  • 점화식 적용 순서

    D(0) → D(1) → D(2) → D(3)

    ⇒ 정점 없이 직접 연결 경로 → 정점 1을 거친 연결 경로 → 정점 2을 거친 연결 경로 → 정점 3을 거친 연결 경로

    ( 직접적으로 가는 간선이 없는 경우는 무한대로 표현)

    (D(0)을 이용해서 D(1)을 계산, 이를 반복한다.)

  • 성능분석

      Floyd(G)
      { 
      	D[][] <- 그래프를 인접 행렬로 초기화;
      	for (k=1부터 |V|까지)
      		for (i=1부터 |V|까지)
      			for (j=1부터 |V|까지)
      				if ( D[i][j] > D[i][k] + D[k][j] )
      					D[i][j] = D[i][k] + D[k][j];
      	return D[][];
      }
    

    성능 = O(

    V

    3) → **O(n3)**

저울문제

• 양팔 저울, n개의 추, 각 추의 무게 wi(1≤i≤n)가 있다는 전제 하에, 무게 M인 물체를 양펄 저울로 달 수 있는지 확인하는 문제

  가정 → 추의 무게 wi와 물체의 무게 M은 모두 정수

• 최적성의 원리

  • n개의 추로 무게 M인 물체를 확인하는 문제

    → k개의 추(s1, s2…, sk)가 선택된다고 한다면, M = ws1 + ws2 + … + ws3

    경우 1) 선택된 추에 n번 추가 포함되지 않는다면

    • 즉, 1~(n-1)번까지의 추를 이용하여 무게 M인 물체를 달 수 있는지의 문제

    경우 2) 선택되 추에 n번 추가 포함된다면(Sk = n으로 가정)

    • n번 추를 제외시키면, M-2sk

      → 1~(n-1)번까지의 추를 이용하여 무게 M-2sk인 물체를 달 수 있는지의 문제

• 점화식

  경우 1)

  • 1번부터 i번까지의 추를 이용하여 무게 k인 물체를 달 수 있는지의 여부

    *S*(*i*,*k*) = max[*S*(*i* −1,*k*),*S*(*i* −1,*k* − *w* )] *i*

• 알고리즘

    Scale (n, w[ ], M) {
    	int i, k, S[0..n][0..M];
    	for (i=0; i<=n; i++) S[i][0] = 1; // O(n)
    	for (k=1;k<=M;k++) S[0][k] = 0; // O(M)
    	for (i=1;i<=n;i++) //O(nM)
    		for (k=1;k<=M;k++)
    			if (k-w[i]<0) //S[i-1][k-w[i]] = S[i-1][음수]
    				S[i][k] = S[i-1][k]; 
    			else
    				S[i][k] = max(S[i-1][k],S[i-1][k-w[i]]);
    return S[n][M]; 
    }
  

• 성능분석

  O(nM) → **O(n2)**

• 특징
  • 무게 k의 증가를 추의 무게의 최대공약수 단위로 증가시키면 효과적
  • 테이블 S와 wi(1≤i≤n)를 이용하면 사용된 추를 구할 수 있음
  • 물체의 무게가 2n보다 크면 모든 경우를 따져보는 직관적인 방법보다 비효율적