動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita

トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単

[joseph150]

ジョーク記事ではないのに、頭がジョークを読んでるモードになってしまって、内容が入ってこなかった。

[hevohevo]

面白すぎる。理解するためゆっくりと読んでいる途中、ふと気になったので調べたのですが、記事中に86回トロピカルと書かれていることを確認しました。

[ene0kcal]

やべぇ。理解してしまった。半解（半分）だけど。（※ただし学部生時代にPascalで動的計画法ソルバーを実装した経験アリ。PIVOTとかあったなぁ。）

[khtokage]

何が始まったのかと思って最後まで読んでみたら凄かった。てかトロピカルって名前が凄いｗ

[krrrr]

lotz先生の文章好きすぎる

[SWIMATH2]

動的計画法との対応がよく分からなかったけど、a_{ij}^{r+1}を求める操作がまんま動的計画法なのか、おもしろ/距離の計算に使われてた関数がまんま経路を求める関数に流用できるの、数学と Haskell しゅごい……ってなる

[nanakoso]

考えた人の名前をつけてあげろよ。トロピカルってなんだよざっくりしすぎだろ。ハンガリアン記法よりひどい。

[dette]

面白かった! ナイーブに使っている掛け算足し算もある意味恣意的で代替可能性があることがわかるのが良いな。

[takehikom]

むかし隣接行列を使ってぷよぷよの連結(消去)判定を書いたのを思いだした

[Nyoho]

トロピカルのでグラフ最短経路できるの知らだったー

[paulownia]

なるほど分からん

[wadara]

途中の問題2 3 0じゃないの？ 分からん。。

[tattyu]

だめだ、モノイドとその次で完全に何もわからなくなった。

[natu3kan]

＞そもそもなんで"トロピカル"幾何学と呼ばれるかというと、どうやらこの分野を研究し始めたのがブラジルの計算機科学者だから7らしい。

[sisidovski]

読んでる間ずっとトロピカ〜ル恋して〜るが頭の中で流れてた

[td2sk]

warshall-floyd法がトロピカル半環上の行列積になってるの全く気づかなかった……

[harapon1012]

半環やMax-plus代数ですね。このグラフ問題との関係性では1980年の古い本ですが次の本がわかりやすかったです https://www.amazon.co.jp/dp/0198596227/

[Insite]

行列ライブラリやGPUで扱えるのでいいってこと？

[pekee-nuee-nuee]

トロピカルの由来が適当すぎでウケる

[todays_mitsui]

おもしろい

[eru01]

半環の説明で謎用語めっちゃ出てくるの、あゝ代数学〜〜〜って感じする。あとでちゃんと読む

[knok]

数学は何かしら見慣れない単語がよく出てくるけどそれらを丁寧に解説してもらえたのでかなりわかりやすかった

[naglfar]

何も分からなかったけどとてつもなくトロピカルだった。

[igrep]

"頂点にとどまるという選択肢が増えた場合、各頂点を1回以上通る経路は最短になりえないので必ず 頂点の数-1回 以内の経路が最短になる。なので累乗もそれだけ行えば十分"

[yasuharu519]

導入スコ

[ruicc]

おもしろい。便利なのでは。

[kkobayashi]

うーん便利そうだけど何をやってるのか分からん！

[masayoshinym]

なるほど、わからん。

[suganoo]

うむ完全に理解できなかった

[flying-cat]

“た”

[hiroshi_revolution]

こういう話が理解できるようになりたい

[fullmated]

面白かった