カタンの最長交易路(Longest Road)を探すために半環を考える - Qiita

この記事はlotzさんの「動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜」という記事を読んで、自分の問題に対しても応用できないかと考えた結果をまとめたものです。 先に元の記事を読んでから以下の内容を読んで頂けるとスムーズかと思われます。 最長交易路とは 皆様は『カタン』というゲームをご存知でしょうか？ カタンは複数のプレイヤーが無人島を開拓して、最も繁栄させることができたプレイヤーが勝利するというボードゲームです。 このゲームには「最長交易路」というルールがあり、最も長い交易路を作ったプレイヤーに追加の得点が入ることになっています。 このゲームにおける交易路はグラフ理論の言葉を借りると無向多重グラフとみなすことができます。 そして、最長交易路を探すということは、無向多重グラフの中で最長の**小道（trail）**を探すことになります。 ここでは、ある頂点からある頂点

[lotz84]

小道の集合に半環の演算を入れて行列計算で最長交易路が計算できてる。よく考えられてるなぁ