サブロウ丸

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

レイティング・ランキングの数理

レイティング・ランキングの数理 の各章の概要をまとめたものです。 本当に概要をまとめただけなので, より詳しく知りたい方は書籍を参考にしてください。 レイティング・ランキングの数理 No.1は誰か?価格:5400円(税込、送料別) (2018/12/2時点)楽天で購…

順列と自然数の対応付け

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

Subgraph isomorphism (J. R. ULLMANNのアルゴリズム)

Qiitaに記事を投稿しました。 グラフ の中に が部分グラフとして存在するかどうかを判断する問題です. Subgraph isomorphismの解法として, J. R. ULLMANNのアルゴリズム [1] を紹介します. 参考文献 [1] ULLMANN, Julian R. An algorithm for subgraph isomo…

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

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

常微分方程式の数値解析による解軌跡の導出

Qiitaに記事を投稿しました。 一階の常微分方程式は, 一般に の形で記述されます。 は独立な変数, は既知の二変数関数であり, は求める未知関数です。 (中略) まずは, 1つの一階の常微分方程式の解軌跡を求める方法を紹介します。 また, この解法は高階の微…

雰囲気で理解する Yen's algorithm (Find the K shortest paths)

Qiitaに記事を投稿しました。 K Shortest Path Problem とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です. 色々バリエーションがあるみたいですが, 今回は多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法…

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

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

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

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である, イリノイ法, アンダーソンビューク法を紹介します。 挟み撃ち法(False position method) イリノイ法(Illinois method) アンダーソン・ビョーク法(Anderson & Björk's 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節 双対ノルムとフェンシエル共役 の中に以下のような記述があります。 劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ) [ 河原吉伸 ]価格:3024円(税込、送料無料) (2018/12/2時点)楽天…

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

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

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

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

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

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

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

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

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

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…