サブロウ丸

サブロウ丸

主にプログラミングと数学

アルゴリズム周辺

DFS(深さ優先探索); Python

二分木構造に関するDFSで、1. 行きがけ、2. 帰りがけ、 3. 通りがけ、 4. 全記録、のPythonコードを紹介します。本稿では下記の木を例に使用します。 深さ優先探索(DFS)はご存知のようにオレンジ色の順番のように、深く(子孫側に)進む方向を優先して二分…

フラクショナルカスケーディング応用

k-th number 方法 fractional cascading 実装 プログラムのまとめ まとめ k-th number 数列a_1, a_2, ..., a_nとクエリを表す数の3つ組みがm個与えられる。各クエリ(i, j, k)に対しa_i, ..., a_jを昇順にソートした際のk番目の数を出力せよ。 n ≤ 1000000 m …

beam search; ビームサーチ; python

幅優先探索の亜種ですね。 rootノードのみからなるpath一つを持つpathsを生成 paths内の全てのpathを1階層分だけ展開しpathsを更新 スコアが最も高いk個のpathのみをpathsに残す 2に戻る 補足: https://www.baeldung.com/cs/beam-search 下記のように実装し…

Python 巡回セールスマン問題

記事の更新をしたのでお知らせ。 bit-dpの理論と実装の解説pdfを作成しました。 inarizuuuushi.hatenablog.com

Master Mind探索プログラム

MasterMind というボードゲームの 最善手探索用プログラムを公開しました. github.com policyやcode_iterに関数を追加して, master_mind.pyの上部をいじれば改良できますので, アイデアがある方はよろしくお願いします. サンプル 3色 2ピンの場合 python mas…

generatorを用いた二分木におけるパスの全列挙; Python

このような番号付けで表現される二分木におけるpathの全列挙を考えます. pathのノード情報をリストでほしい場合 再帰 gist.github.com を実行すると >> [[0, 1, 3], [0, 1, 4], [0, 2, 5], [0, 2, 6]] が出力されます. 深さ優先探索で左側からノードを探索し…

順列と自然数の対応付け

なぜこうなるかは、実際に順列を書き出して番号をつけて眺めてみれば分かると思います。 以下は上記アルゴリズムを元にpythonで実装したものです。(少し変えています) 関数 perm2int(perm)が順列を自然数に変換し、 関数int2perm(n)が自然数を順列に変換しま…

Eppstein's Algorithm (Find the K shortest paths) 解説と実装 (Python)

Qiitaに記事を投稿しました。 K Shortest Path Problem (KSP) とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です。 多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法として Eppsteinの アルゴリズムを実装し…

常微分方程式の数値解析による解軌跡の導出

Qiitaに記事を投稿しました。 一階の常微分方程式は, 一般に の形で記述されます。 は独立な変数, は既知の二変数関数であり, は求める未知関数です。 (中略) まずは, 1つの一階の常微分方程式の解軌跡を求める方法を紹介します。 また, この解法は高階の微…

雰囲気で理解する Yen's algorithm (Find the K shortest paths)

Qiitaに記事を投稿しました。 K Shortest Path Problem とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です. 色々バリエーションがあるみたいですが, 今回は多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法…

求根アルゴリズム デッカー法 ブレント法 [3/3]

さて, 求根アルゴリズム最終回はデッカー法とそれを改良したブレント法を紹介します。 ブレント法はMATLABの非線形関数の根をみつける関数fzeroにも用いられている有用なアルゴリズムになっています。 デッカー法(Dekker method) ブレント法(Brent method) …

求根アルゴリズム 挟み撃ち法 / イリノイ法 / アンダーソン・ビョーク法 [2/3]

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である イリノイ法とアンダーソンビューク法を紹介します。 挟み撃ち法(False position method) イリノイ法(Illinois method) アンダーソン・ビョーク法(Anderson & Björk's method) 挟み撃ち法(F…

求根アルゴリズム 二分法 / 割線法 [1/3]

本稿から3回に分けて様々な求根アルゴリズムを紹介したいと思います。 求根とは、ある関数 の根, すなわち を満たす を求めることです。 もし が微分可能であれば微積分の知見を用いて根を見つけることは容易な場合も多いですが、今回は関数 が微分不可能、…

最小カットを用いたモノクロ画像のノイズ除去 その1

「劣モジュラ最適化と機械学習」(講談社)の4.2節 「マルコフ確率場における推論とグラフカット」で取り上げられている 劣モジュラを満たすエネルギー関数最小化による画像ノイズ除去手法を実際にプログラム実装してみました。 行いたいことに特化した簡単な…

ナップサック問題 近似アルゴリズム

言わずと知れたナップサック問題は、動的計画法を用いると最適解を商品の個数とナップサックの容量に対して1次のオーダーで計算することができます。 また、この問題については近似解法が知られています. とりあえず2通りの近似解法を知っているので, 動的計…

ダブリング

ダブリングという計算手法に感動したので、No.572 妖精の演奏 - yukicoderこの問題の解説を書こうと思います。 問題文を読むと、なるほどいかにも動的計画法チックな問題ですね、 ということで、最初は普通に以下のような定式化を行いました。 gist.github.c…

Hornerの公式

Hornerの公式という多項式の計算を高速に行う方法があります。 と言っても仕組みは簡単で以下のような式変形を行うだけです。 単純に項ごとを足し合わせるよりも、掛け算の回数が減っていることが分かりますね。 計算量はそれぞれ となっています。 実験 # P…

bitDPで巡回セールスマン問題を解く; Python

巡回セールスマン問題をpythonで解きます。 01整数計画法を使っても解けますが、今回は動的計画法を使用します。 解説 解説用のpdfを文書を作成したので是非ご覧ください。 drive.google.com pythonコード DPは配列ではなく、辞書を使用しています。 次回か…

Python 集合と自然数との対応付け

下記のような、集合と自然数の対応付けを考えます。 {0, 1, 2, 3} <—> 15 基本的な考えは2進数表記です。 {0, 1, 2, 3} <—> 20 + 21 + 22 + 23 = 15 {0, 1, 3} <—> 20 + 21 + 23 = 11 これをそのまま関数にすると、 def set2int(_iter): res = 0 for i in _i…

Pythonで素数列挙

エラトステネスの篩を使った素数判定法をpythonで実装しました