Zenn
🌴

トロピカル半環をPythonで実装してみる

に公開
tropical
tech

はじめに

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

この記事で紹介されていたトロピカル演算でのグラフ最短経路計算が大変面白かったので、Pythonで実装してみる

トロピカル半環の実装

トロピカル半環の定義

\mathbb{R} \cup \{ \infty \} において、以下の演算を定義する

  • 加法
    • 演算: a \oplus b = \min(a, b)
    • 単位元: \infty
  • 乗法
    • 演算: a \otimes b = a + b
    • 単位元: 0

Python実装

  • TropicalNumberクラスとして実装
  • Pythonの演算子オーバーロードを使って、加法と乗法を定義
class TropicalNumber:
    def __init__(self, value):
        if isinstance(value, TropicalNumber):
            self.value = value.value
        else:
            self.value = value

    def __add__(self, other):
        return TropicalNumber(min(self.value, other.value))

    def __mul__(self, other):
        return TropicalNumber(self.value + other.value)

    @staticmethod
    def zero():
        return TropicalNumber(float("inf"))

    @staticmethod
    def one():
        return TropicalNumber(0)

    def __repr__(self):
        return str(self.value)

動作確認

  • 動作確認コード
tn1 = TropicalNumber(1)
tn2 = TropicalNumber(2)
tn3 = TropicalNumber(3)
tn4 = TropicalNumber(4)

print(tn1 * (tn2 + tn3))
print((tn1 + tn2) * (tn3 + tn4) )
  • 出力
3
4
  • 以下より期待通りの結果が得られていることが確認できる
    • 1 \otimes (2 \oplus 3) = 1 + min(2, 3) = 3
    • (1 \oplus 2) \otimes (3 \oplus 4) = min(1, 2) + min(3, 4) = 4

トロピカル行列の実装

トロピカル行列の定義

  • トロピカル行列は、トロピカル数の行列である
  • 2 \times 2の例でトロピカル行列の和と積を紹介
A = \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix}, B = \begin{pmatrix} b_1 & b_2 \\ b_3 & b_4 \end{pmatrix}

トロピカル行列の和

A \oplus B = \begin{pmatrix} a_1 \oplus b_1 & a_2 \oplus b_2 \\ a_3 \oplus b_3 & a_4 \oplus b_4 \end{pmatrix}

トロピカル行列の積

A \otimes B = \begin{pmatrix} a_1 \otimes b_1 \oplus a_2 \otimes b_3 & a_1 \otimes b_2 \oplus a_2 \otimes b_4 \\ a_3 \otimes b_1 \oplus a_4 \otimes b_3 & a_3 \otimes b_2 \oplus a_4 \otimes b_4 \end{pmatrix}

トロピカル行列の累乗

A^0 = E = \begin{pmatrix} 0 & \infty \\ \infty & 0 \end{pmatrix}
A^n = \underbrace{A \otimes A \otimes \cdots \otimes A}_{n}

Python実装

class TropicalMatrix:
    def __init__(self, matrix):
        self.matrix = [[TropicalNumber(value) for value in row] for row in matrix]

    def __add__(self, other):
        assert len(self.matrix) == len(other.matrix) and len(self.matrix[0]) == len(
            other.matrix[0]
        ), "Matrices must have the same dimensions to add them"
        result = [
            [TropicalNumber.zero() for _ in range(len(self.matrix[0]))]
            for _ in range(len(self.matrix))
        ]
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix[0])):
                result[i][j] = self.matrix[i][j] + other.matrix[i][j]
        return TropicalMatrix(result)

    def __mul__(self, other):
        result = [
            [TropicalNumber(float("inf")) for _ in range(len(other.matrix[0]))]
            for _ in range(len(self.matrix))
        ]
        for i in range(len(self.matrix)):
            for j in range(len(other.matrix[0])):
                for k in range(len(self.matrix[0])):
                    result[i][j] = result[i][j] + (
                        self.matrix[i][k] * other.matrix[k][j]
                    )
        return TropicalMatrix(result)

    def __pow__(self, exponent):
        assert (
            isinstance(exponent, int) and exponent >= 0
        ), "Exponent must be a non-negative integer"
        if exponent == 0:
            # Return the identity matrix
            size = len(self.matrix)
            return TropicalMatrix(
                [
                    [
                        TropicalNumber.one() if i == j else TropicalNumber.zero()
                        for j in range(size)
                    ]
                    for i in range(size)
                ]
            )
        result = self
        for _ in range(1, exponent):
            result = result * self
        return result

    def __repr__(self):
        return str(self.matrix)

トロピカル行列の可視化コード

  • トロピカル行列を隣接行列とするグラフとして可視化するためのコード
def visualize_tropical_graph(matrix):
    dot = Digraph(comment="Tropical Graph")

    # ノードの追加
    n = len(matrix.matrix)
    for i in range(n):
        dot.node(str(i), f"Node {i}")

    # エッジの追加
    for i in range(n):
        for j in range(n):
            if matrix.matrix[i][j].value != float("inf"):
                dot.edge(str(i), str(j), label=str(matrix.matrix[i][j].value))

    return dot

可視化の動作確認

G = TropicalMatrix([[float('inf'), 2, 4, float('inf')],
[float('inf'), 0, 1, 9],
[float('inf'), float('inf'), float('inf'), 5],
[3, float('inf'), float('inf'), float('inf')],
])
dot = visualize_tropical_graph(G)
dot.render('G', format='png', cleanup=True)

G

トロピカル行列演算の動作確認

サンプルグラフGの定義

G = \begin{pmatrix} \infty & 2 & 4 & \infty \\ \infty & 0 & 1 & 9 \\ \infty & \infty & \infty & 5 \\ 3 & \infty & \infty & \infty \end{pmatrix}
G = TropicalMatrix([[float('inf'), 2, 4, float('inf')],
[float('inf'), 0, 1, 9],
[float('inf'), float('inf'), float('inf'), 5],
[3, float('inf'), float('inf'), float('inf')],
])

G

G^nを計算して、ちょうどn回で到達できる最短経路のコストを求める

G^0の計算

G**0

[[0, inf, inf, inf], [inf, 0, inf, inf], [inf, inf, 0, inf], [inf, inf, inf, 0]]

G^0 = \begin{pmatrix} 0 & \infty & \infty & \infty \\ \infty & 0 & \infty & \infty \\ \infty & \infty & 0 & \infty \\ \infty & \infty & \infty & 0 \end{pmatrix}

G0

G^2の計算

G ** 2

[[inf, 2, 3, 9], [12, 0, 1, 6], [8, inf, inf, inf], [inf, 5, 7, inf]]

G^2 = \begin{pmatrix} \infty & 2 & 3 & 9 \\ 12 & 0 & 1 & 6 \\ 8 & \infty & \infty & \infty \\ \infty & 5 & 7 & \infty \end{pmatrix}

G2

G^3の計算

G ** 3

[[12, 2, 3, 8], [9, 0, 1, 6], [inf, 10, 12, inf], [inf, 5, 6, 12]]

G^3 = \begin{pmatrix} 12 & 2 & 3 & 8 \\ 9 & 0 & 1 & 6 \\ \infty & 10 & 12 & \infty \\ \infty & 5 & 6 & 12 \end{pmatrix}

G3

G^6の計算

G ** 6

[[11, 2, 3, 8], [9, 0, 1, 6], [19, 10, 11, 16], [14, 5, 6, 11]]

G^6 = \begin{pmatrix} 11 & 2 & 3 & 8 \\ 9 & 0 & 1 & 6 \\ 19 & 10 & 11 & 16 \\ 14 & 5 & 6 & 11 \end{pmatrix}

G6

G^{100}の計算

  • G^{100}は、G^6と同じ結果になる
G ** 100

[[11, 2, 3, 8], [9, 0, 1, 6], [19, 10, 11, 16], [14, 5, 6, 11]]

G^{100} = \begin{pmatrix} 11 & 2 & 3 & 8 \\ 9 & 0 & 1 & 6 \\ 19 & 10 & 11 & 16 \\ 14 & 5 & 6 & 11 \end{pmatrix}

G100

最短経路の計算

(G+E)^nを計算することで、n回以内で到達できる最短経路のコストを求める

G + E 

G + (G ** 0)

[[0, 2, 4, inf], [inf, 0, 1, 9], [inf, inf, 0, 5], [3, inf, inf, 0]]

G + E = \begin{pmatrix} 0 & 2 & 4 & \infty \\ \infty & 0 & 1 & 9 \\ \infty & \infty & 0 & 5 \\ 3 & \infty & \infty & 0 \end{pmatrix}

clo

(G + E)^2 

(G + (G ** 0)) ** 2

[[0, 2, 3, 9], [12, 0, 1, 6], [8, inf, 0, 5], [3, 5, 7, 0]]

(G + E)^2 = \begin{pmatrix} 0 & 2 & 3 & 9 \\ 12 & 0 & 1 & 6 \\ 8 & \infty & 0 & 5 \\ 3 & 5 & 7 & 0 \end{pmatrix}

clo2

(G + E)^3 

(G + (G ** 0)) ** 3

[[0, 2, 3, 8], [9, 0, 1, 6], [8, 10, 0, 5], [3, 5, 6, 0]]

(G + E)^3 = \begin{pmatrix} 0 & 2 & 3 & 8 \\ 9 & 0 & 1 & 6 \\ 8 & 10 & 0 & 5 \\ 3 & 5 & 6 & 0 \end{pmatrix}

clo3

(G + E)^4

  • (G + E)^4は、(G + E)^3と同じ結果になる
(G + (G ** 0)) ** 4

[[0, 2, 3, 8], [9, 0, 1, 6], [8, 10, 0, 5], [3, 5, 6, 0]]

(G + E)^4 = \begin{pmatrix} 0 & 2 & 3 & 8 \\ 9 & 0 & 1 & 6 \\ 8 & 10 & 0 & 5 \\ 3 & 5 & 6 & 0 \end{pmatrix}

clo4

おわりに

  • トロピカル半環とトロピカル行列の実装を通じて、トロピカル演算の面白さを体感できた
  • GPUで高速計算とかもやってみたい気がする🤔

Discussion