hsimyu's diary

ゲームなどをします。

7/16 ゲリラ豪雨

7/16 (火)

うーん仕事が増えていく。今日やっていたやつは泥沼感が出てきたので一旦後回しにして、残りを片付けてしまうことに決めた。(今)

退社した瞬間めちゃくちゃ雨が降ってきて、靴がびしょ濡れになった。ひゃっほー。

娘はご機嫌タイム長め。しかし、朝寝昼寝をたくさんしたからか夜全然寝付かない。結局21時過ぎまで動いていた。

C++: std::optional の紹介

Expressiveness, Nullable Types, and Composition (Part 1)

空の返り値が返ってくる可能性があるような時は、 std::optional を使おう!

ただし、std::optional を単純に返り値にすると複雑になるし、すべての optional の null check をしないといけなくなる。C++20 で追加される Monadic interface を使うことで、これを解決できる。

    auto const zipCode = findPerson(customQuery)
    .and_then(findAddress)
    .map(getZipCode);
    
    if (!zipCode) return;
    use(zipCode.value());

トロピカル演算でグラフ計算

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

加法の逆元の公理がないものが半環

半環を成す→分配法則と零化の公理を満たしているかどうかを確認すればいい

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

へー。

トロピカル半環

  • 加法: min (x, y)
  • 乗法: x + y

実数 + 実数以外の何かで構成

(max(x,y) を採用してトロピカル半環と呼ぶケースもあるらしい)

トロピカル行列の積の各項は、a11・b11 +a12・b21 なので、つまり min(a11 + b11, a12 + b21) である。 (distance product)

重み付き有向グラフの隣接行列をトロピカル行列とみなす。この行列を m 乗した行列の i 行 j 列の値は、頂点 i から頂点 j まで m 回で到達できる経路のうち最小の距離(重みの和)を持つものの距離と対応する。(m-1 乗の各項が最小距離を表す時、min([隣接点までの m-1 までの最小距離 + 隣接点からの距離]のリスト) だから)

トロピカル行列の行列積による、全点対間最短経路問題の解法は、実はワーシャルフロイド法による解法と一致している。

ごはん

朝: オールブラン

昼: チキンライス

夜: 麻婆茄子