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

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

2018-12-03

順列と自然数の対応付け

python アルゴリズム周辺

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

2018-11-15

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

グラフ理論 python

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

2018-11-08

Matplotlib 日本語の使用

python

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

2018-09-27

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

グラフ理論

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

2018-09-13

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

グラフ理論 python アルゴリズム周辺

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

2018-09-06

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

数学アルゴリズム周辺

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

2018-08-30

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

アルゴリズム周辺グラフ理論

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

2018-06-11

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

数学アルゴリズム周辺

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

2018-06-04

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

数学アルゴリズム周辺

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形であるイリノイ法とアンダーソンビューク法を紹介します。挟み撃ち法(False position method) イリノイ法(Illinois method) アンダーソン・ビョーク法(Anderson & Björk's method) 挟み撃ち法(F…

2018-05-28

求根アルゴリズム二分法 / 割線法 [1/3]

数学アルゴリズム周辺

本稿から3回に分けて様々な求根アルゴリズムを紹介したいと思います。求根とは、ある関数の根, すなわちを満たすを求めることです。もしが微分可能であれば微積分の知見を用いて根を見つけることは容易な場合も多いですが、今回は関数が微分不可能、…

2018-04-18

【MATLAB】 fnplt カスタマイズ

Matlab

MATLAB fnpltで関数をプロットできます。このとき, メッシュ上の黒い枠線を消したいなーとか思っている人向けの記事です。(すごくニッチだ) fnpltは surfという, 関数の表面をプロットする関数をもとに作成されています。なのでfnpltの中のsurfのオプショ…

2018-04-11

HUE/360 色情報の取得

数学全く関係ないですが... このサイト([ HUE / 360 ] The Color Scheme Application)では, 色相環から適当に色を選ぶとその色と相性の良い色の候補を自動で絞り込んでくれますが, 選んだRGB情報が画面上に表示されません。あくまで, macのsafari環境での話…