グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) ↓その1です。 inarizuuuushi.hatenablog.com が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フ…

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

どーしても、Excelでグラフを大量に作成したいときには AppleScriptで書かせましょう。 (サンプルコード) tell application "Finder" --theListにファイルパスのリストを代入 set theList to {"ファイルパス,ファイルパス,....."} --for文 repeat with file_…

上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、それをどう厳密に表現するか?…

Mac book air のストレージ容量が溜まってきたなーと思ったので、 sudo du -sh /* で、ルート下のディレクトリについてその容量を計算させてみると (オプション-sは「ファイルやディレクトリの総計を表示する」、-hは「容量を適当な単位で表示する」という意…

brew cleanup homebrewでインストールしたパッケージの古いバージョンのキャッシュの削除を行います。 容量整理に

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

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

アルファベットが1文字ずつ入った配列の作り方です。 class Sample{ public static void main(String []args){ char []alphabet = new char[26]; char c = 'a'; for (int i = 0; i < 26; i++){ alphabet[i] = c++; } } } charクラスのオブジェクトにもインク…

ある二つの三角形について、その形と大きさが等しいとき、それらは「合同である」と言います。 この合同についてみなさん、中学校で以下の三つの合同条件を習ったと思います。 ・三辺相等 ・二辺狭角相等 ・二角狭辺相等 例えば三辺相等について、 三角形の…

完全マッチングについて面白い定理を見つけたので、ご紹介します。 まず、完全マッチングについて、 グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング…

jad を使えば、javaのclassファイルのデコンパイル(コンパイルをする前のソースコードを復元すること)ができます。 homebrewを使ってインストールするには brew tap caskroom/cask brew install caskroom/cask/jad を実行してやれば良いです。 homebrew/bina…

いつもはPythonの記事ばかり書いていますが、今回はJavaです。 Javaで、整数と配列と二次元配列の3つを一度に返す関数を作りたかったのですが、 Javaの関数は基本的に返り値が一つだけなので、 関数の返り値を保存するためだけのクラスを作ることにしました…

次のようなネットワークのフロー分解を考えます。 まず、フローとは何かという話ですが、 始点(図s)から終点に(図t)に水を流すことを考えます。 そのときの"水の流れ"のことをフローと呼びますが、それにはいくつか条件があります。 図のノード(丸)とノード…

今回は Chapter2 劣モジュラ最適化の基礎 2.4 列もジュラ最適化と多様体の 貪欲解の最適性についてです。 ラグランジュ緩和については以下のPDFが分かりやすくまとまっていると思います。 http://www.bunkyo.ac.jp/~nemoto/lecture/opt-model/2008/duality1-…

「劣モジュラ最適化と機械学習」という河原先生と永野先生が書かれた本を最近勉強しています。 https://www.amazon.co.jp/劣モジュラ最適化と機械学習-機械学習プロフェッショナルシリーズ-河原-吉伸/dp/4061529099/ref=sr_1_fkmr0_1?ie=UTF8&qid=1492411085…

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

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

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

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

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

標準出力をpbcopyに渡すと、クリップボードに保存されます。 # ls の出力結果をコピー ls | pbcopy # カレントディレクトリの絶対パスをコピー echo -n `pwd` | pbcopy 逆にpbpasteを使えば、クリップボードからペーストができます。 echo `pbpaste` 等..

ターミナル上からスリープ、シャットダウン、システム終了等を行うことができます。 osascriptというAppleScript を実行するためのコマンドを使用します。 スリープ osascript -e 'tell application "Finder" to sleep' 【豆】 逆にスリープを防ぐには caffe…

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で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形式で例えば{ゴリラ} という文字列を作りたいときは animal = 'ゴリラ' print('{{}}'.format(animal)) print('{{animal}}'.format(animal=animal)) と{を2つ重ねます。

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

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

Cythonを使ってPythonのコードを高速化します。 Cythonのインストール pip3 install cython コンパイル cythonのインストールが終わったら、スクリプトをc言語にコンパイルするために、以下のsetup.pyを用意します。 (ext_modules = [Extension('tsp', ['tsp…

巡回セールスマン問題をpythonで解きます。 01整数計画法を使っても解けますが、今回は動的計画法を使用します。 解説 解説用のpdfを文書を作成したので是非ご覧ください。 drive.google.com pythonコード DPは配列ではなく、辞書を使用しています。 次回か…