サブロウ丸

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

イラストロジックを解く 第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…

PythonユーザーのためのMatlab対応表

PythonユーザーのためのMatlab対応表を作っていこうと思います。 Matlabのドキュメントは初心者殺しっぽいところがありますよね... 徐々に増やしていく予定です。 list 宣言・要素の追加 python a = [1, 2] a.append(3) # a = [1, 2, 3] a.append(4) # a = […

線形計画問題における、とある条件を持つバイナリ変数の表現方法について - その2

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

brewでpython3をupgradeするとpip3が使えなくなった件

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

opencv3.3.0 インストール エラー

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 変数和

pulpです。 変数の和を表現するときにsumよりもlpSumを使った方が高速にプログラムが動くという話です。 この簡単な最小化問題を例に。aは定数、bは実変数です。 import pulp from random import randint # A new Lp problem prob = pulp.LpProblem('sample'…

線形計画問題における、とある条件を持つバイナリ変数の表現方法について

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

【Mac】パスワード付きzipファイルの作成

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