サブロウ丸

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

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

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

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

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

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

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

【MATLAB】 fnplt カスタマイズ

MATLAB fnpltで関数をプロットできます。 このとき, メッシュ上の黒い枠線を消したいなーとか思っている人向けの記事です。(すごくニッチだ) fnpltは surfという, 関数の表面をプロットする関数をもとに作成されています。 なのでfnpltの中のsurfのオプショ…

HUE/360 色情報の取得

数学全く関係ないですが... このサイト([ HUE / 360 ] The Color Scheme Application)では, 色相環から適当に色を選ぶとその色と相性の良い色の候補を自動で絞り込んでくれますが, 選んだRGB情報が画面上に表示されません。 あくまで, macのsafari環境での話…

双対ノルム

「劣モジュラ最適化と機械学習」(講談社) 5.1.2節 双対ノルムとフェンシエル共役 の中に以下のような記述があります。 さらっと書いてありますが, 本当に双対ノルムの双対ノルムがもとのノルムになるかどうかを調べました。一部, Hahn-Banach定理という解析…

イラストロジックを解く 第4回 全探索

さて, 4回目の今回は全探索。 考えられる盤面を片っ端から全探索します。 アルゴリズム 一番上の行の最も左のキーをk_1, 2番目に左のキーをk_2, ..., 一番上の行の最も右のキーをk_i, 二番目に上の行の最も左のキーをk_{i+1},..., 一番下の行の最も右のキー…

イラストロジックを解く 第3回 ボゴ法

さっそくイラストロジックを解くアルゴリズムを考えていきます。 ボゴ法 ボゴソート(ボゴソート - Wikipedia)を参考にしたのでボゴ法と名付けました。神頼みによる解法になります。 まず各行それぞれについて、行の条件を満たすようにランダムにマスを塗る …

イラストロジックを解く 第2回 基盤プログラムの説明

これから紹介するアルゴリズムを記述する上で基盤とするプログラムの説明をします。 需要は低いと思いますが、自分用ということで... まずは問題の記述用ファイルから。 上のような問題に対して, 以下のファイルを作成します。 Rが行数(row) Cが列数(column)…

イラストロジックを解く 第1回 はじめに

これからイラストロジックを解くアルゴリズムとそのプログラミングをしたいと思います。(全何回になるかは決まっていませんが、シリーズものです) イラストロジックとは、ののぐらむ、イラストロジック、ピクロスや、お絵かきロジックとも呼ばれるパズルの一…

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

この記事の続きです。 今回やりたいのは, ある画像を元にノイズを付加した画像を数枚用意します。 そのノイズが付加した数枚の画像から元の画像を復元することを考えます。 前回の記事の\thetaを事後確率を用いて以下のように決定します。 ということで, 上…

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

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

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

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

Python 文字と整数の相互変換

忘れやすいので, メモ。 char -> int 例えば"A"を0, "B"を1, "C"を2, ...と変換したい場合はord関数を使います。 Excelのマス目の番地を指定して読み込むときとかに便利ですね。 ord('A') >>> 65 ord('B') >>> 66 このord関数は1 文字の Unicode 文字を表す…

shell または bashでのタプル型for文

Pythonでいう for i, j in [(1, 2), (3, 4), (5, 6)]: print(i, j) >>> 1 2 >>> 3 4 >>> 5 6 というタプル型のfor文をシェルスクリプトで行うのがこの記事の最終目標です。それにはデータ構造として配列を使うのですが、その配列の"構文"を理解、もしくは覚…

Python ショートコーディング Tips

Pythonはcやjavaよりも可読性が優れている言語です。 その可読性を十分に発揮する、つまり人が見て読みやすいプログラムにするには、プログラムにある程度冗長性を持たせる必要があります。 基本的には短いプログラムほど理解しやすいですが、技巧的に短くし…

pulp エラー集

pulp solvers.PulpSolverError pulp.solvers.PulpSolverError: Pulp: Error while executing /usr/local/lib/python3.6/site-packages/pulp/solverdir/cbc/osx/64/cbc このエラーが起きた時は, ソルバー自体の問題ではなく、宣言した変数名LpVariable(name='…

【Python】順序付きビンパッキング問題

この記事の応用です。 商品とビンに順序をつけた場合のビンパッキング問題になります。 ソースコード 実行結果 入力 うさぎ0が食べるりんごの量は1.2 うさぎ1が食べるりんごの量は2.2 うさぎ2が食べるりんごの量は1.0 うさぎ3が食べるりんごの量は0.7 うさぎ…

【Python】ビンパッキング問題

離散数学の組合せ論の代表的な問題としてビンパッキング問題というのがあります。 十分に用意された品物を、複数個のビン(容器)に詰めるときの最大利益を求める問題です。 このときビンの個数が1つであればナップサック問題と呼ばれる問題になります。 この…

Networkx バージョン更新に伴うエラー

Python上でグラフを取り扱うモジュールであるNetworkxのversionが1.11 -> 2.0に更新された際に、以前あった関数の幾つかが使えなくなっています。 現在、分かっているものを列挙していきます。 (旧) g.edge[i][j]['weight'] = 1 # i, jはノード (新) g[i][j]…

【Python】pulp CBC並列処理・ソルバー選択

CBCソルバー(デフォルト)並列処理 pythonの線形計画法ソルバーpulpを並列で計算する方法です。 例えば、4スレッドで実行するなら import pulp prob = pulp.LpProblem(sense=pulp.LpMinimize) (省略) prob.solve(pulp.PULP_CBC_CMD(threads=4)) と書きます。 …

ダブリング

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

deBoorの公式

上の記事で紹介したMATLABのcsapiはdeBoorの公式を用いて双3次スプラインを行っています。 この記事ではそのdeBoorの公式を自作してみたいと思います。 アルゴリズム さて、ここでどのようにfxやfyを計算するかというと、 この記事の方法を用います。スプラ…

【Matlab】双3次スプライン(csapi)

csapi関数を用いて双3次スプライン関数の生成と復元を行います。 双スプラインとは2変数のスプライン関数のことです。 言い換えれば平面の補間関数になります。 まずはソースコードから。 peaksというMatlabのサンプル関数からいくつかを標本点を取り出して…

有限差分法による勾配の計算(一次, 二次, 三次)

問題設定 一次近似 二次近似 三次近似 この三次近似について、幾何的にどう捉えられるのかを考えてみました。 (面積で議論することもできると思います) 四次近似については’Runge-Kutta法’という方法が知られています。 それについては、こちらをどうぞ ルン…

【Matlab】 有理スプライン補間

有理スプライン補間をMatlabで実装してみました。 有理スプライン補間とは3次スプライン補間の3次の項を双曲線関数に置き換えたものです。 有理スプラインはパラーメータをうまく調節することで、 3次スプライン補間(参考: 3 次スプライン データ内挿 - MATL…

【Mac】Cbcソルバー 並列処理

Cbcとはオープンソースの混合整数線形計画(mixed integer liner program)ソルバーです。 混合整数線形計画問題とは読んで字のごとく、 線形計画問題の中に連続変数と、整数変数が混合している問題のことになります。 そのCbcソルバーで並列処理を行えるよう…

【Matlab】 ビルトイン関数を表示する

Matlabでビルトイン関数(標準関数)は edit 関数名 で表示できます。 こんな感じ。

Newtonの差分商補間(後編)

これの後編です。 実際に簡単な関数でいくつか補間による近似を行なってみたいと思います。 fが近似したい関数、gがデータ点(0, 0) (1, 1) (2, 2)から構成した差分商補間になります。 fは2次式でかつ、前編の最後の定理「剰余なしのn項からなるNewtonの差分…

Newtonの差分商補間(前編)

Newtonの差分商補間の理論についてです。内容は高校レベルでしょうか。 最後の定理は強力ですね。 補間といえば、他にはLagrange補間が有名ですが、 Lagrange補間よりも計算量が少ないことが特徴です。 一番最後の証明は、「n点を補間するn-1次の多項式はLag…