サブロウ丸

Sabrou-mal サブロウ丸

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

python

flopt 統合型最適化モデラーとソルバーの開発 その1

統合型最適化Pythonフレームワーク flopt をオープンソースで開発中です. floptは 最適化問題のモデリングツールであり, ソルバーであり 他ソルバーのOverwraperであり, 手法比較ベンチマーク を目標に作成しています. Github PyPI Read and Docs PuLP Pytho…

[ python ] 自作クラスをnumpy ndarrayに使用する

Subclassing ndarray — NumPy v1.18 Manual (公式)を参考にすれば良いでしょう. 以下, 簡単な実装例. class Element: def __init__(self, r, c): self.r = r self.c = c def __repr__(self): return f'Element({self.r},{self.c})' 上の自作クラスを, 2次元n…

【python】 matplotlib: color をRGB, RGBAで指定した際のwarning

matplotlibのplotやscatterでcolorを (0.0, 0.0, 0.803921568627451, 1.0) のようなRGBや, RGBAで指定した場合 plt.plot(..., c=(0.0, 0.0, 0.803921568627451, 1.0)) 'c' argument looks like a single numeric RGB or RGBA sequence, which should be avoi…

Master Mind探索プログラム

MasterMind というボードゲームの 最善手探索用プログラムを公開しました. github.com policyやcode_iterに関数を追加して, master_mind.pyの上部をいじれば改良できますので, アイデアがある方はよろしくお願いします. サンプル 3色 2ピンの場合 python mas…

【Python】pulp, CPLEXで並列数指定

pulpでsolverとしてCPLEXを指定する場合, 並列数はDefault設定では使用可能なthread数を全て使用する設定になっています. 並列数を自分で指定したい場合は, 以下のようにすれば良いです. import pulp class MyCPLEX(pulp.CPLEX): def __init__(self, mpi=Tru…

【Python】PuLP; 多段階最適化

まだ PuLPのdocumentに載っていない(執筆時)関数ですが sequentialSolveという多段階最適化を行う関数が実装されています import pulp from pulp import LpVariable # 問題の宣言 problem = pulp.LpProblem() # 変数の宣言(連続変数, 上限2) x = LpVariable(…

generatorを用いた二分木におけるパスの全列挙; Python

このような番号付けで表現される二分木におけるpathの全列挙を考えます. pathのノード情報をリストでほしい場合 再帰 gist.github.com を実行すると >> [[0, 1, 3], [0, 1, 4], [0, 2, 5], [0, 2, 6]] が出力されます. 深さ優先探索で左側からノードを探索し…

PyTorch autograd で Newton法実装

Qiitaに記事を投稿しました. PyTorchは主にニューラルネットワークの学習に使用されるライブラリですが, autogradはより幅広い使い方ができます. 今回はその機能を用いてNewton法を実装しました. qiita.com

Pulp ソルバー選択 / 並列計算 (python)

Pulpについて Pulp は線形計画問題を解く Python パッケージです. install pip install pulp pulpの処理フロー Pulpについて 使用できるソルバ一覧 CBC CBC > オプション(並列計算など) CBC > 自分でインストールしたCBCソルバーを使用する CBC > 1. 公式サ…

【Python】scipy KD treeの使い方

kd treeは k dimensional treeで, k次元領域の点探索などに用いられるデータ構造です。 kd treeを取り扱うモジュールがscipyにあります。 import scipy.spatial as ss from random import random # データ数 N = 10000 # (x座標, y座標)のデータリスト data …

順列と自然数の対応付け

なぜこうなるかは、実際に順列を書き出して番号をつけて眺めてみれば分かると思います。 以下は上記アルゴリズムを元に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…

【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 宣言・要素の追加 リストの結合 set 重複する要素の削除 要素の存在判定 dictionary 辞…

python pulp 変数和

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

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

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…

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

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

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

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

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

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