サブロウ丸

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

python周辺

順列と自然数の対応付け

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

Preflow Push-Relabel アルゴリズム 改良

Qiitaに記事を投稿しました。 qiita.com 概要 preflow-push algorithm はネットワーク G=(V, E)上の最大フローを求めるアルゴリズムです. (中略) この記事では, 計算量を削減する改良として, FIFO Preflow-Push AlgorithmとHighest-Label Preflow-Push Algor…

Matplotlib 日本語の使用

Pythonの代表的なグラフ描写モジュールmatplotlibでグラフタイトルや凡例に日本語を使う方法をメモります。 環境: OS: macOS High Sierra 10.13.3 Python: Python3.6 基本的には, 以下のサイトを参考にすれば上手くいくと思いますが /usr/local/lib/python3.…

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

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

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

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

最小カットを用いたモノクロ画像のノイズ除去 その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 文字を表す…

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

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

【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)) と書きます。 …

Newtonの差分商補間(後編)

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

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

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

python pulp 変数和

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

【Matlab】【Python】ディレクトリ内のファイルに対し反復処理を行う

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

最短路問題を線形計画法で解く (Python)

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…

【Python】 newton法(非線形計画)

newton法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 関数fと勾配、初期点を問題に合わせて入力する必要があります。

【Python】 最急降下法(非線形計画)

最急降下法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 目的関数fと勾配、初期点を問題に合わせて入力する必要があります。

Python 要素1のタプルの宣言

要素が一つのタプルを作りたいときに a = (1) としても, >>> a 1 >>> type(a) <class 'int'> でaは整数型になっていることが分かります。 じゃあ、どうすればいいかというと a = (1, ) もしくは a = 1, としてやれば、いいです。 なんか気持ち悪いですね。</class>

Python 数独を解く(整数線形計画法)

pythonのpulpモジュールを用いて、数独を線形計画法で解きます。 pulpはpip3 install pulpでインストールできます。

Python multiprocessingで並列処理

pythonの標準モジュールmultiprocessingを使用すれば、並列処理を行うことができます。 Pool map 基本的な使い方は from multiprocessing import Pool with Pool(processes=None) as pool: pool.map(func, iter) Poolの引数であるprocessesには並列処理に使…

Python ジェネレーター内包表記

普通にリストの内包表記の感覚でタプルの内包表記を書こうとすると a = (i for i in range(10)) type(a) > <class 'generator'> と、ジェネレータが作成されてしまいます。 タプルが欲しいのに….と言うときは、 b = tuple(a) とtupleでジェネレーターをラップさせればokです。 </class>…

Python pickle プロトコルの指定

今までpickleファイルを作成するときは、 with open(file, 'wb') as f: pickle.dump(obj=obj, file=f) としていましたが、プロトコルバージョンを高いものに指定してやると、より速く読み込めるpickleファイルが作れるらしい。。 最新のプロトコルバージョン…

Python reduce関数

functoolsのreduce関数を使って、リストの中身を全て足したり掛けたり、といった操作を行えます。 from functools import reduce from operator import add, mul a = [1, 2, 3, 4] # 適当なリスト reduce(add, a) # 総和 > 10 reduce(mul, a) # 総乗 > 24 こ…

Python osmnxのインストール

pythonでopen street mapのデータを読み込めるosmnxという便利なモジュールがあるのですが、 pip3 install osmnxとインストールしようとすると、 fiona/_transform.cpp:473:10: fatal error: 'cpl_conv.h' file not found #include "cpl_conv.h" ^ 1 error g…

Python format形式の中で{}を使う。

pythonのformat形式で例えば{ゴリラ} という文字列を作りたいときは animal = 'ゴリラ' print('{{}}'.format(animal)) print('{{animal}}'.format(animal=animal)) と{を2つ重ねます。

Cython その3 配列の型付け

Cython その2 - サブロウ丸の続きです。 今回はCythonでの配列の型付けの話をします。 配列の要素が全て同一の型の場合、(当然ですが)そのことを宣言した方がより高速になります。 Cythonで上記を実現するにはメモリービューと呼ばれるものを使用します。 nu…

Cython その2 変数の型付け

Cython その1 - サブロウ丸 前回からの続きです。 cython tsp.pyx --annotate もしくは cython tsp.pyx -a を実行すると tsp.html というファイルが作られます。 tsp.html · GitHub これをブラウザ等で開くと という、画面が出てきます。 簡単に言うと、濃い…