雑談スレ - 1467740989 - したらば掲示板

1：名無しさん：2016/07/06(水) 02:49:49 ID:QjAtSIeQ: プロコン・競プロ・ハッカソン・CTF・オンラインジャッジなどをされる方々の雑談の場としたいです
雑談ですのでプロコン・競プロ・ハッカソン・CTF・オンラインジャッジなどに関係しない内容でも構いません。

当然ですが
したらば掲示板サービスの禁止事項に触れるような内容の雑談は禁止です
詳しくはガイドラインをお読みください
http://rentalbbs.shitaraba.com/rule/guideline.html
72：名無しさん：2017/02/16(木) 22:51:44 ID:KHIvLZmI: 蟻本って一部だけならグーグルの書籍検索でも読めるんだね
2chのスレでワーシャルフロイドの話あってちょろっと見てみた
中々簡潔に書かれてて読むの大変そう
73：名無しさん：2017/02/16(木) 22:56:44 ID:KHIvLZmI: なるほどdp[k][i][j]の頂点0～kのk+1個の頂点を使った場合のiとjの最短経路をあらわすのか
74：名無しさん：2017/02/16(木) 23:00:21 ID:KHIvLZmI: dp[k-1][i][j]は頂点0～(k-1)のk個の頂点だけを使ったときのiとjの最短経路か
そこに頂点kを加えたときのiとjの最短経路dp[k][i][j]を求めるってこととか
頂点(k-1)までを使った最短経路は求まっているのだから頂点kを経由する経路についてだけ新たに考えればよいと
75：名無しさん：2017/02/16(木) 23:04:06 ID:KHIvLZmI: dp[k-1][i][k]+dp[k-1][k][j]は
iとkのどこも経由しない直通と
kとjのどこも経由しない直通との和になってるはず(ここまでのDPでは頂点kについては考慮してないはずだから)
76：名無しさん：2017/02/16(木) 23:08:27 ID:KHIvLZmI: min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])は
頂点kを一切経由しない最短経路と
頂点kのみを経由する経路とで
最小のほうを選択して頂点0～k個使う場合のiとjの最短経路を求めている・・・
77：名無しさん：2017/02/16(木) 23:13:35 ID:KHIvLZmI: dp[k-1][i][j]は
i -> j の可能性もあるし
i -> a -> b -> j の可能性もある
その中での最短経路、そこに頂点kを加える
i -> k -> j と比較するわけだけど
例えば i -> a -> k -> j のほうが短くなったりしないのだろうか
78：名無しさん：2017/02/16(木) 23:17:46 ID:KHIvLZmI: そうか、本にあるコードは(k-1)を省略した2次元のほうのコードだから
それをそのままdp[k-1][i][j]の3次元のコードとして捉えちゃダメなんだな
使用する頂点の数を考慮する場合は本のとは違うコードにならなければならないのか
79：名無しさん：2017/02/16(木) 23:21:43 ID:KHIvLZmI: これ2次元版と3次元版のコードでは大掛かりな変形が必要な感じがする
80：名無しさん：2017/02/16(木) 23:28:17 ID:KHIvLZmI: これ3次元版から2次元版に落とし込むための理屈はかなり複雑になる気がする
81：名無しさん：2017/02/16(木) 23:33:11 ID:KHIvLZmI: 3次元版のときは最初に頂点kを始点あるいは終点とした最短経路を求めてから頂点kを経由する最短経路を求める必要があるのかな？
82：名無しさん：2017/02/16(木) 23:45:42 ID:KHIvLZmI: もし>>81の考え方が合ってるなら蟻本の説明が不適切なん気がするよ・・・
83：名無しさん：2017/02/16(木) 23:47:57 ID:KHIvLZmI: まぁでもワーシャルフロイド法って蟻本でなくても学習できることだし
メジャーなアルゴリズムの説明ならもっと分かりやすく説明してる本やサイトを探すのが解決には早そう
84：名無しさん：2017/02/16(木) 23:50:01 ID:KHIvLZmI: 人によって説明の仕方が違うから
一人の人の説明だけに頼らず色んな人の説明を参考にしたほうが
多少時間や手間がかかっても理解には直結しやすいと思うけど
85：名無しさん：2017/02/17(金) 00:19:28 ID:KHIvLZmI: 2次元版のは
全ての頂点(0～V)においてiからjまでの頂点0～(k-1)を経由する可能性のある最短経路に対して
頂点kをi,jにおいてそれぞれの頂点0～(k-1)を経由する可能性のある最短経路で経由させた場合に新たなiとjの最短経路になるかっていう感じ
86：名無しさん：2017/02/17(金) 00:26:38 ID:KHIvLZmI: あ、そうか、>>85を考えると>>81は間違いだわ
蟻本の「使う」の言葉の意味の解釈の問題だわ
87：名無しさん：2017/02/17(金) 00:33:01 ID:KHIvLZmI: 蟻本の「頂点0～kのみを使う」というのは「最短経路の経由点として使う」という意味なのか
>>73での間違い解釈はi,jに関しては0～(k-1)を使うと思ってたけどそうではなく0～Vを使う
「頂点0～kとi,jのみを使う」って一文、何か不自然さを感じてたけど、「と」による区切れがi,jは0～Vを使うという意味が含まれてたのか
88：名無しさん：2017/02/17(金) 00:37:12 ID:KHIvLZmI: >>73-81までの解釈は完全に間違いだということを理解した
89：名無しさん：2017/02/17(金) 00:44:12 ID:KHIvLZmI: つまり3次元版のdp[k][i][j]は頂点0～kを経由する可能性のあるi間j(頂点0～V)の最短経路を表す
90：名無しさん：2017/02/17(金) 00:54:20 ID:KHIvLZmI: >>73も>>89も間違いがあって
dp[k+1][i][j]が頂点0～kの範囲で
dp[k][i][j]は頂点0～(k-1)だった
91：名無しさん：2017/02/17(金) 01:25:59 ID:KHIvLZmI: 3次元を2次元に落とし込める理由は

入力側の頂点(k-1)を1度経由させる経路は
dp[k-1][i][k-1]もdp[k-1][k-1][j]もどちらも頂点(k-1)以降を経由しない(頂点0～(k-2)を経由する可能性のある)最短経路が保証され
2次元のdp[i][k-1]もdp[k-1][j]も同様のことが言える

更新される側の
2次元の場合、dp[i][j]が更新されていくわけで入力側に何らかの影響がありそうな雰囲気を感じることがあるのかもしれないけど
入力に影響がありそうに見えるのはこのiかjがどちらかが(k-1)だった場合、
つまり始点か終点が頂点(k-1)であり、それの最短経路の経由点に頂点(k-1)を含むことはないので入力に全く影響を与えない
3次元で言うと
dp[k][i][k-1]=min(dp[k-1][i][k-1],dp[k-1][i][k-1]+dp[k-1][k-1][k-1])これは常にdp[k][i][k-1]=dp[k-1][i][k-1] (どう見ても自明)
同様にdp[k][k-1][j]についてもいえる
i!=k-1かつj!=k-1のときはdp[k-1][][]からdp[k][][]への計算に再利用はされないから
3次元の最初の次元である使用する頂点の数というのを分けて考える必要ないから2次元に落とし込める

だめだ、俺も日本語下手だわ