氷運搬問題

グラフ上に半環の値を付与して最適問題を解くのは、行列計算とお絵描きをつなぐ良い例題だ。

係数をmax-plus代数にすると、時間的／空間的移動に伴い累積する値を大小比較で判定される（少ないと負け）状況を表現できる。実数区間[0, 1]のmax-times代数の場合は、移動に伴い減衰する非負値を大小比較で判定される状況を表現できる。

例えば、あるノードから全員同じ重さの氷を運ぶとして、変ごとに70%とか50%とかで重さが減る（解ける）とする。各ノードでは誰の氷が一番重いかを判定して、負けた人は脱落する。この設定では、どうしたら氷を解かさないで運べるか、目的地到着時の氷の重さの最大値とかを云々できる。