
# 熱帯代数（トロピカル代数）とは


最小値をとる操作と足し算の２つの二項演算によって定義される代数系のことを熱帯代数、トロピカル代数、min-plus代数といいます。オペレーションズ・リサーチにおいて幅広い応用があるそうです。


先日[Tatsuya Hirose](https://qiita.com/lotz)さんが投稿された[動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜](https://qiita.com/lotz/items/094bffd77b24e37bf20e)を拝見してこの分野を知り、関心をもつようになりました。2020年8月8日段階で445LGTMsを集めるなど世間での関心が高いことが伺えます。今回記載されている内容を自分でもPythonで実装してみることにしました。熱帯代数の詳しい定義や問題設定など、僕の記事での実装の背景はここでは改めて説明しないのでもとの記事をご覧ください。


# なぜPythonで実装するのか


上では最小値をとる演算と加算をもつ代数系と熱帯代数を説明しましたが、実際にはもう少し踏み込んで「最小値をとる演算を通常の加算の代わりに」「加算を通常の乗算の代わりに」利用して内積や行列積を定義するところがカギになってきます。Pythonでは`__add__`を定義することで`+`の、`__mul__`を定義することで`*`の振る舞いを実装することができますが、この機能を利用することで数式の見た目とコードの見た目が一致して可読性があがります。


また元の記事ではHaskellを採用しており、実際に順序付け関数を別々に実装することでグラフの辺と重みという異なる対象を同じmin演算で呼び出すという関数型らしい実装をしています。この機能も`__le__`, `__ge__`を定義して`<=`, `>=`の振る舞いを定義できるPythonでうまく再現できそうです。


# 最短経路問題


実際に実装する前に、今回やろうとしていることを簡単に解説します。


元記事に掲載されている重み付きグラフの画像は以下のようになります。

<img style="width: 100%;" src="https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.ap-northeast-1.amazonaws.com%2F0%2F17134%2Fedfca915-97bf-7792-0a09-2c06fd7baf83.png?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&s=2e159b210bc0ab1e351c76235fb4010a" alt="画像が表示されない場合は元の記事を参照ください"/>

もし点同士の間に橋がかかっていなければ、そこは渡ることができません。便宜上コスト無限大の橋がかかっていると見做すこともできます。


このグラフ上で各点から各点へちょうど$n$回で橋を渡って行ける方法のなかで最短（重みの和が最も小さい）のものを探します。なぜこれが熱帯代数と関係するのかはベクトルの内積のしかたに秘密があります。

例えば、点aから２回で点dに行きたいとします。

点aからは直接には点aや点dに行くことはできず（コスト無限大）、点bへはコスト２、点cにはコスト４で行くことができます。各点への移動のコストをa,b,c,dの順に並べてベクトルで表すと$(\infty, 2, 4, \infty)$となります。


点dに点a,b,c,dそれぞれ**から**直接行くときのコストを同じように並べると$(\infty, 9, 5, \infty)$となります。


点aから点bを経由して点dに行く時、コストは２つの橋の合計になりますから$(\infty, 2, 4, \infty)$の第2要素と$(\infty, 9, 5, \infty)$の第2要素の和11がコストになります。同様に各点を経由した時のコストはベクトルの要素同士の和を見ればわかります。

$$(\infty, 11, 9, \infty)$$


そしてこの中の最小値をとれば最短経路のコストがわかります。

このように、最短経路は

<center>ベクトルの要素を足す -> 結果の最小をとる</center>

で求めることができます。一方で通常、ベクトルの内積は

<center>ベクトルの要素をかける -> 結果の和をとる</center>

となります。つまり掛け算の代わりに足し算を、足し算の代わりに最小を使う熱帯代数ではベクトルの内積によって（行列の積はそれを繰り返すので、最終的には行列の積によって）最短経路問題を解くことができます。


# ソースコード

今回実装した内容はこちらにまとめているので参考にしてください。

https://github.com/yaufai/python-notebook/tree/master/python_notebook/tropical_algebra_shortest_path

* 前半の最短経路のコストを求めるところまで: https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py
* 後半の最短経路の経路を求めるところまで: https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py


# 熱帯ベクトルを実装して最短経路のコストを求める


まずベクトルを定義します。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=5:8"></script>

なお、`float("inf")`で無限大を表す`float`型のオブジェクトを作成できるので、重みを表現するのに必要な条件は`float`だけで十分です。


そして加法と乗法を定義します。ベクトル空間には乗法は定義する必要はありませんが、今回はベクトルの乗法は`float`型の乗法が通常の足し算であるとみなした時の内積になっています。普段使ったり意識しているベクトルの積と異なる場合は混乱しないよう気をつけてください。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=15:32"></script>


このベクトルとその内積をもとに行列と行列の積を定義します。数学では縦ベクトルをつかって行列を表記することが多い気がしますが、横ベクトルを並べたものを行列としているので注意です。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=35:38"></script>
<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=48:68"></script>

冪乗は指数を減少させる再帰処理で実装しました。本当は基本行列を定義するともっとすっきりします。


上のグラフ上で２回、３回の橋を渡って行ける最短経路のコストを求めます。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_1.py?slice=85:95"></script>


```
$ python tropical_algebra_1.py
['[inf, 2, 3, 9]', '[12, 0, 1, 6]', '[8, inf, inf, inf]', '[inf, 5, 7, inf]']
['[12, 2, 3, 8]', '[9, 0, 1, 6]', '[inf, 10, 12, inf]', '[inf, 5, 6, 12]']
```


# 橋にも代数系を定義して最短経路も求める

最短経路のコストはわかりましたが、最短経路自体がわからなければその解を実行することはできません。ここでは最短経路を求めるためにグラフの辺の集まり（経路）に対して最小と加算を定義していきます。そしてそのためにまずは抽象的な熱帯代数の枠組みを定義します。

まず熱帯代数の一つめの演算である「最小」についてですが、これは大小の比較さえ定まれば自明に決まります。一方、加法はそうではないので熱帯代数のクラスは大小比較(`__le__`, `__ge__`)と加法(ここでは乗法`__mul__`)を抽象メソッドにしたクラスとして定義します。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=9:36"></script>


前半までにやったような重みは

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=40:52"></script>

というように定義できます。
また経路に関しても同様に順序と乗法を定義すれば熱帯代数の元になれます。`None`は経路が存在しないことを示しています。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=53:70"></script>

まず大小比較ですが、経路のコストが小さいほどその経路が小さいと評価されることが重要です。つまりコストの最小化と経路の最小化が一致するので、あとで最小の演算が実行されるときに対応する最短経路が計算されることになります。乗法については通常のリストの結合と同じに定義してあります。コストの追加と対応する辺の経路への追加が一緒になるようになっています。


熱帯代数の元が定義できたのであとはそれを元にベクトルと行列を定義するだけです。これらは熱帯代数の元の加法（最小）と乗法（加法）を呼び出すだけで実際の熱帯代数の元の値などには依存しないので抽象クラスにする必要はありません。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=71:146"></script>


あとは重みを表現する隣接行列`A`と経路の行列`P`を以下のように定義すればグラフの描写は完了です。

<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=147:160"></script>



二乗を計算してみます。
<script src="https://gist-it.appspot.com/https://github.com/yaufai/python-notebook/blob/master/python_notebook/tropical_algebra_shortest_path/tropical_algebra_2.py?slice=162:165"></script>


```
$ python tropical_algebra_2.py
['[inf, 2, 3, 9]', '[12, 0, 1, 6]', '[8, inf, inf, inf]', '[inf, 5, 7, inf]']
['[None, [(1, 2), (2, 2)], [(1, 2), (2, 3)], [(1, 3), (3, 4)]]', '[[(2, 4), (4, 1)], [(2, 2), (2, 2)], [(2, 2), (2, 3)], [(2, 3), (3, 4)]]', '[[(3, 4), (4, 1)], None, None, None]', '[None, [(4, 1), (1, 2)], [(4, 1), (1, 3)], None]']
```

最短経路が求められていることがわかります。


# 結び

他の方がすでに実装された内容を他の言語で再実装しただけの簡単なものでしたが、Pythonなりの抽象化のしかたや表現のしかたが見せれたと思います。


僕としては代数的な性質を意識しながらプログラムしたのがはじめてだったので面白かったです。特に、グラフの経路に対してよくいう「数」と遜色なく演算を定義して問題を解けることを確認できたのは、現代数学の抽象化の威力を再確認できました。


熱帯代数については応用は狭くなさそうなので、これを機に他の応用例についての文献を勉強したり、また他に代数をうまく活用した問題解決があればそちらも見ていきたいです。

