最小費用流についてのちょっとしたメモ - gdgdiary
恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ 最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何？)ので頑張って通すと良さそう。 Minimum cost b-flow フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました ぼくの考えたさいきょうのフローライブラリ - みさわめも みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。 b-flow というのは、各頂点に需
高速な詰将棋アルゴリズムを完全に理解したい（完成版） - コンピュータ将棋 Qhapaq
Qhapaq アドベント将棋記事10日目 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。 参考文献： memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn（厳密には非0のpn、dn
仮眠プログラマーのつぶやき : UnityでGPGPU応用編 バイトニックソートを高速化
2020年07月13日12:44 カテゴリUnityGPGPU UnityでGPGPU応用編 バイトニックソートを高速化 バイトニックソート(Bitonic Sort)の概要バイトニックソート(Bitonic Sort)は主にGPU等の並列計算器でソートを実装しようとするときに使われるソートである。 計算量のオーダーはO(n log^2 n)であり、クイックソートのO(n log n)には負けるものの並列化による高速化が勝るという感じなのでいろんなところに使われている。 対象読者キーワード「GPU」「バイトニックソート」で検索してこの記事にたどり着いただろう方が対象。 この記事では ・バイトニックソートでなぜソートできるか ・どうやったら高速化できるか という点について重点的に書いている。 高速化については OpenCLでバイトニックソートを実装している海外サイト をパクリ参考にした。 こ
有理数同士の大小比較
JAG の ICPC 模擬地区予選 2015 の最中に, ジャッジルームで思いついたこと. イントロ 誤差を避けるために有理数を使うとき, オーバーフローするボトルネックは, 多くの場合, 有理数同士の大小比較になる. (逆に, 有理数同士の大小比較がボトルネックにならないときは, 別のテクニックで誤差を避けられることがある) そこで, 有理数の分母分子自体はオーバーフローしていないときに, 有理数同士の比較を, なるべくオーバーフローさせずに行う方法を見る. つまり, 次のような sgn 関数を作りたい. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39template<class Int> struct Fraction{
MCTSの評価伝達遅延を防ぐ方法（MCTS-Solver） - inani_waonの日記
ネタバレ ぼくのかんがえたさいきょうの手法は既出で、MCTS-Solverというようです。 はじめに モンテカルロ木探索（MCTS）は、ゲーム木の各ノードを評価しながら探索を行える優秀な探索アルゴリズムです。 Wikipedia : モンテカルロ木探索 https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2 しかしCodinGame*1のUltimate Tic-Tac-ToeというゲームでMCTSを使っていたところ、シミュレーション結果が優勢にも関わらず、ある瞬間に劣勢に反転して負けてしまうことが多々ありました。ある手を指されると劣勢なのに、それが評価に反映されずに優勢と勘違いしている状態ですね。 左図：シミュレーション勝
木探索についての考察2 - 水たまり
以下の続き。 木探索がそもそもどういうものであるかと考えると、状態をノード、行動をエッジとして構築されるグラフ上を遷移しつつ、ノード上の価値を更新していく作業だと思われる。モンテカルロ木探索の選択ステップに「一個親のノードへ戻る」という選択肢を加えれば、理論上は木の自由な遷移ができるので、たとえば以下のようなことができる。 ステップ1 ステップ2 ステップ3 ステップ4 結局各ステップで解きたい問題は「木の遷移履歴が与えられるので、現ノードを適切に評価し次に遷移するエッジを決定する問題」としてまとめられそうだ。ここで、木の遷移履歴は状態を訪問順に並べた単なる時系列入力として扱える。（無茶かなぁ……）。状態の分散表現取得や、状態価値の評価にはAlphaZero的なモデルの分岐直前までの部分などを使うとして、次のようなやり方を今のところ想定している。 木のような句構造を持つことが多い自然言語文
ぼくの考えたさいきょうのフローライブラリ
要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
Segment Tree のお勉強(2) | maspyのHP
遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 概要 前回 → Segment Tree のお勉強 (1) を前提としています。 1点更新、区間作用、区間積取得が可能な Segment 木。いわゆる非再帰実装 1-based index$N=2^n$ を仮定しない モノイド $A$ がモノイド $X$ に右作用するとします。各々のモノイドの二項演算を、積の形で、$$\begin{align*}A\times A\longrightarrow A;\quad (a,b)\mapsto ab,\\X\times X\longrightarrow X;\quad (x,y)\mapsto xy\end{align*}$$ と書きます。作用は、$$X\times A\longrightarrow X;\quad (x,a)
セグメント木を徹底解説！0から遅延評価やモノイドまで | アルゴリズムロジック
セグメント木とは セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します
C言語による乱数生成
本文章はC言語を用いて様々な確率分布に従う乱数を生成する方法やコードをまとめたものである。rand関数やメルセンヌ・ツイスタの使い方から始まり, 正規分布・指数分布等の様々な確率分布に従う乱数の生成方法について解説する。このページは近江崇宏によって作られました。コードはご自由にお使いになってかまいませんが、バグ等によって生じた損失に対する責任は負いません。 道しるべ: ・Ｃ言語でお手軽に整数の乱数を発生させたい人 ==> C言語のrand関数の使い方 ・メルセンヌ・ツイスタの使い方を知りたい人 ==> メルセンヌ・ツイスタの使い方 ・一様乱数の生成方法を知りたい人 ==> 一様乱数 ・様々な確率分布に従う乱数生成法を知りたい人 ==> 各種の確率分布に従う乱数の生成法 入門編 C言語のrand関数の使い方 メルセンヌ・ツイスタの使い方 乱数生成の基礎 一様乱数 (Uniform Rando
わしの思うリッジ回帰(L2正則化)と正則化法。 - Pseudo Theory of Everything
1 はじめに 最近、我々+数名でスパースモデリングという分野を勉強しています。詳細はまた別の記事にて紹介するにして、今回はスパースモデリングの前段階に当たる リッジ回帰(ridge regresion) に脚光を当てます1。 読者には釈迦に説法かもしれませんが、リッジ回帰は L2 正則化とも呼ばれ機械学習の中でも非常にスタンダードな概念の一つになっています。しかし専門的に正則化法を扱ってみて、案外知らなかったことを知れたのでまとめました。 まず、リッジ回帰での損失関数は以下のような式で記述されます。 \begin{align} E = (y - X \vec{w})^2 + \alpha \vec{w}^T \vec{w} \end{align} 上記の損失を最小化するように係数の重みベクトル \(\vec{w}\) を推定します。解析的には \(\vec{w}\) について微分をしたもの
kuuso on Twitter: "超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 https://t.co/mQ68pGe6hG #Qiita 大作だった．いい記事．"
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Ryou Ezoe(江添 亮) on Twitter: "Bloom filterは無偽陰性と低擬陽性の特徴を持つ確率的で空間効率のよいデータ構造だと言われていたが、Coqでの検証により、思っているほど低擬陽性ではないそうだ。 https://t.co/60cL33frBD"
Hiroki Tanaka on Twitter: "新しい「数値計算の常識」のPDFを見つけた https://t.co/PJ27tYds6v"
cakes（ケイクス）
pitsu on Twitter: "(Aの任意倍)mod B の最大値が B - gcd(A,B) なの直感的にはわかるけど証明できない"
yowa on Twitter: "0.25*(popcount(rand64bit()) - 32) を正規乱数だと言い張るスタイル"
Mathematical Optimization in 60 minutes
tdual(ティーデュアル)@MatrixFlow on Twitter: "うおおおお！素晴らしい。ワイの疑問が載ってた。 自称機械学習の理論わかってるマンは読んだ方が良い。 わしの思うリッジ回帰(L2正則化)と正則化法。 - Pseudo Theory of Everything https://t.co/6Jkfp6NaQ6"