浮動小数点アルゴリズム

最適化の原則は、動的計画法で最適化問題を解くために成立しなければならない.

ベストプラクティス

ある問題の入力事例の最適解が常にその入力事例を分割する一部の事例に対する最適解を含む場合,その問題は最適原則を成立する.
次の図はリストで表され、コードのように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じゃないの?
パス(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が出るまでしか確認できません!
この和弦を見れば理解できるけど、こうやってこの問題を解いていきたい.今はまだだめです.