플로이드 알고리즘

• 최적의 원칙이 반드시 성립해야 최적화 문제를 동적계획법으로 풀 수 있다.

최적의 원칙

어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 성립한다고 한다.

아래 그림을 리스트로 표현해보면 코드처럼 W가 된다.

import copy
def floyd(W):
    n = len(W)
    D = copy.deepcopy(W) # D0 만들어 deepcopy로 그냥 = 써버리면 D를 변경하는 순간 W도 변하니까 주의!
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    
    return D
            
max = 99999

W = [[0,1,max,1,5],[9,0,3,2,max],[max,max,0,4,max],[max,max,2,0,3],[3,max,max,max,0]]

D = floyd(W)

print(D)

K = 1 일때 D[4][0~4], D[4][1] + D[1][0~4]
K = 2 일때 D[4][0~4], D[4][2] + D[2][0~4]

이렇게 해서 0~4 모두 지나는 경우를 모든 간선에서 구해준다.

그럼 지나온 경로는 어떻게 출력할 것인가?

~~ 처음에는 이렇게 했다. 이 코드는 엄청난 문제가 있다!

import copy
def floyd(W):
   n = len(W)
   D = copy.deepcopy(W) # D0 만들어 deepcopy로 그냥 = 써버리면 D를 변경하는 순간 W도 변하니까 주의!
   P = [[-1]* n for _ in range(n)] 
   for k in range(n):
       for i in range(n):
           for j in range(n):
               if(D[i][j] > D[i][k] + D[k][j]):
                   D[i][j] = D[i][k] + D[k][j]
                   P[i][j] = k 
   
   return D,P

def path(P,i,j):
   num = P[i][j] 
   print(i, end=" -> ")
   if P[i][j] != -1:
       path(P,num, j)
   else:
       print(j)

바로 여기가 큰 문제

def path(P,i,j):
   num = P[i][j] 
   print(i, end=" -> ")
   if P[i][j] != -1:
       path(P,num, j)
   else:
       print(j)

P[i][j] 에는 i -> ...->k->j 이런 정보가 들어있다.
위와 같이 해버리면 path(P,num, j) 는 무조건 -1 이 나와서
i, num, j 밖에 print 하지 못 한다.

그러면 어떻게 해야하나?
i -> ... -> k 에서 ... 을 알아내야 한다.
그럼 i -> k 로 가는 가장 가까운 길을 알아내면 되겠지
path(P,i,num) 추가하고 print (num) 을 실행해준다.
num을 거쳐서 가니까!

def path(P,i,j):
    num = P[i][j] 
    if P[i][j] != -1:
        path(P,i,num)
        print (num, end= " -> ")

~~강의 에서는 ~~

def path(P,i,j):
    num = P[i][j] 
    if P[i][j] != -1:
        path(P,i,num)
        print (num, end= " -> ")
        path(P,num,j)

이렇게 해서 path(P,num,j)을 추가해줬는데 사실 path(P,num,j)는 의미 없는게 아닌가?
무조건 -1 나오는게 아닌가?
왜냐면 path(P,i,num) 하면

num이 -1이 아니면 i -> ... -> j 에서 i -> ..num -> j 이거니까 다시 i -> .. ->num
이 과정만 하면 되는거 아냐..?

아 아니다 아니다. 난 바보냐?

P[i][j] = k # i -> j 로 갈 때 마지막에 K를 거쳐서 감! (for문 다 끝났을 경우 의미 -1 이면 아무것도 안 거쳐서 감) 여기를 이렇게 생각해서

i -> ..->k -> j 라고 생각해 버렸다. 전혀 아니다.
코드를 보면 k는 그냥 가장 큰 인덱스 일 뿐이다.

그래서 i -> .. -> k -> .. -> j 이렇게 생각해야 한다.
그럼 코드는 어떻게 되는가?

import copy
def floyd(W):
    n = len(W)
    D = copy.deepcopy(W) # D0 만들어 deepcopy로 그냥 = 써버리면 D를 변경하는 순간 W도 변하니까 주의!
    P = [[-1]* n for _ in range(n)] 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if(D[i][j] > D[i][k] + D[k][j]):
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = k # i -> j 로 갈 때 거치는 인덱스 중 가장 큰 인덱스!
    
    return D,P

def path(P,i,j):
    num = P[i][j] 
    if P[i][j] != -1:
        path(P,i,num)
        print (num, end= " -> ")
        path(P,num,j)


max = 99999

W = [[0,1,max,1,5],[9,0,3,2,max],[max,max,0,4,max],[max,max,2,0,3],[3,max,max,max,0]]

D, P = floyd(W)

print(P)
path(P,4,2)

이렇게 된다.
왜?

i -> ... -> k -> ... -> j 이니까

i -> k 로 거쳐가는 값이 있는지 확인하고 있으면 (그 값은 x 라 해보자)

i ->.. -> x -> .. -> k 이렇게 되니 또 확인

그리고 k -> ... -> j 까지 어떤 것을 거치며 가는지 확인한다.

결국 k 앞 뒤를 -1이 나올 때 까지 확인하는 수 밖에 없다!!

참 이걸 코드를 보고 이해는 하지만 이걸 이렇게 까지 생각해서 푸는건... 아직은 안될듯