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

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

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

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

Pythonでいう for i, j in [(1, 2), (3, 4), (5, 6)]: print(i, j) >>> 1 2 >>> 3 4 >>> 5 6 というタプル型のfor文をシェルスクリプトで行うのがこの記事の最終目標です。 結論から言うと下記のようにします. a=(1 3 5) b=(2 4 6) for ix in ${!a[@]} do ec…

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

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='…

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

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

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

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…

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

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

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

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

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

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

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

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

PythonユーザーのためのMatlab対応表を作っていこうと思います。 Matlabのドキュメントは初心者殺しっぽいところがありますよね... 徐々に増やしていく予定です。 list 宣言・要素の追加 リストの結合 set 重複する要素の削除 要素の存在判定 dictionary 辞…

この記事の続きです。 inarizuuuushi.hatenablog.com この記事の中で2通りの方法を載せていますが、どちらの方が良いか調べてみたのでその報告です。 上の問題を解きます。 それぞれ制約の入れ方は 以前の記事では、2つ目のパターンでは分数の形で記述してい…

件名がルー大柴みたいになってしまいました。 python3.6.2にupgradeすると、なぜかpip3が使えなくなってしまいました。 $ pip3 -bash: pip3: command not found 一旦brew uninstall --ignore-dependencies python3 でpython3をアンインストールした後で もう…

brewにてopencv3のupgradeがあったのですが homebrew/science/opencv3 3.3.0_1 ==> Upgrading homebrew/science/opencv3 --with-python3 ==> Downloading https://github.com/opencv/opencv/archive/3.3.0.tar.gz Already downloaded: /Users/tateiwanariaki…

pythonの 線形計画モデリングツール pulp についてです。 変数の和を表現するときにsumよりもlpSumを使った方が高速に処理が行われます。 この簡単な最小化問題を例に。aは定数、bは実変数です。 import pulp from random import randint # A new Lp problem…

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

パスワード付きのzipファイルをコマンドライン上(ターミナル)で作成する方法です。 文法は zip -e (圧縮後ファイル名) (圧縮対象のファイルパス) あとは指示に従うだけです。 $ zip -e sample.zip sample.txt Enter password: (パスワードを入力) Verify pas…

python from glob import glob files = glob('パス名'); for file_name in files: pass file_nameにはファイルパスが代入されます。 files = glob('tmp/*.txt') など matlab files = dir('パス名’) numfiles = length(files); for i =1:numfiles file = file…

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

typespeed タイピングゲームが楽しめます tldr (too long, don’t read)の略で manコマンドを簡潔にしたコマンドです。 man は長すぎるので「tldr」