サブロウ丸

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

アルゴリズム周辺

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

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

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

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である, イリノイ法, アンダーソンビューク法を紹介します。 挟み撃ち法(False position method) 二分法のように根が存在するであろう探索区間を保ちながら, 次の探索点としては直線補間を用いる…

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

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

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

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

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

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

ダブリング

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

Hornerの公式

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

Python 巡回セールスマン問題

巡回セールスマン問題をpythonで解きます。 問題の概要はwikipediaをご覧ください。 巡回セールスマン問題 - Wikipedia 01整数計画法を使っても解けますが、今回は動的計画法を使用します。 擬似コード (字が汚くて、ごめんなさい) 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で実装しました