Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ワーシャルフロイド法で嵌ったらDPテーブルのインデックスは集合というパターンがみえた

f:id:akiradeveloper529:20190307134820j:plain

中国人郵便配達問題

www.rustforbeginners.com

でワーシャルフロイド法を使って全点間最小距離を求めましたが、私の初期の解答はAOJの37番目のテストでこけてしまい、色々試行錯誤して間違いに気づくのに1時間かかりました。

f:id:akiradeveloper529:20190307134833j:plain

その間違いは、ワーシャルフロイド法でループを正しいk,i,jではなく、i,j,kで行っていたことです。(以下が正しいコード)

for k in 0..V {
    for i in 0..V {
        for j in 0..V {
            if k==i || k==j { continue; }
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
     }
}

なぜこのような過ちに至ったかというと、ワーシャルフロイド法もDPも本質的にはわかってないからです。しかし、誤ったコードを書いても37番目までバグ検知されないというのは結構ビビリました。世の中には誤った順で書いてるけどバグを踏んでないワーシャルフロイドのコードが結構存在するのではないでしょうか。

ワーシャルフロイド法をもう一度学び直したら、DPのパターンについて一つ学びを得たので共有します。

wikiを見ると、集合K={1..k}を考えて、KU{i,j}の中での最短路を求めるを拡大していくと書いています。蟻本でも同様で、dp[k][i][j]を考えて、これをk方向について配列を再利用しながら実装することによって上のようなコードを導くとしています。

つまり、ワーシャルフロイドにおけるkというインデックスは集合なのです。本当は{1..k}と書きたいけど、それを省略してkと書いてるにすぎません。これは、k番目のノードを見るという意味ではないのです。だからこれを1,2,4,8,16,...のようにビットで表しても実装出来るということになります。こう考えると、巡回セールスマン問題で使ったビットDPはDPの特殊な場合ではなくより一般的な場合と考えることが出来ます。

こう見ると、多くのDPでは、

  1. i番目までを考えたときの〜 = つまり0からi番目の集合を考えた時の〜
  2. これこれの集合を考えた時の〜

というパターンが多く、集合成分を第一要素にとるDPテーブルを設計することが多いことがわかります。DPがそもそも、サブセットでの計算結果を再利用して次の計算に繋げていくというものですから、この結果は当たり前かもしれませんが、単なるインデックスの場合(上でいう1)とビットDPの場合(上でいう2)を統一して見えることが出来るという意味では、解法を考える時には役立ちます。なぜ私がi,j,kの順番でループさせてしまったかというと、そもそもkが集合だということが分かっておらず、単に三重ループを回して最小距離を更新していくアルゴリズムとしか捉えられていなかったからです。kが集合に見えていれば、このような間違いはしなかったはずです。

同様に、kからl番目までを集合として考えるなども、小さな情報量で集合を表現する方法としてはあり得るので、今のところ見たことがないように思いますが、候補としてはあり得るのかもしれませんね。