輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
mod で計算するときに零の重複度も持つテク - うさぎ小屋
概要 通常の整数の乗除算を、計算過程に出現する数の最大値を小さくするなどの目的で、ある $p$ に対して $\bmod~ p$ で計算することがあります。 しかし、$p$ が途中に出現する数より小さい場合には、もともとは $0$ ではないのだが $\bmod~ p$ では $0$ になってしまうような数が問題となることがあります。 このような場合には、整数 $a$ に対して $b = a ~\bmod~ p$ の値だけでなく、その整数 $a$ が約数として $p$ をいくつ含むかの数 $c$ も管理するとうまくいくことがあります。 つまり $a = b p^c$ に対して単に $b$ のみを持つのでなく組 $(b, c)$ を持つようにするとうまくいくことがあります。 また、計算の過程では $c \lt 0$ のような組 $(b, c)$ を許して考えると便利です。 例題 1: AtCod
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
