「今日から使える！組合せ最適化 離散問題ガイドブック」サンプルプログラム

内容

書籍で説明している下記のアルゴリズムを説明するためのPythonによるサンプルプログラム(下記参照)です。

アルゴリズム名ファイル名アルゴリズム名ファイル名
ダイクストラ法01-Dijkstra.py フロー増加法02-AugmentingPath.py
負閉路除去法03-NegativeCycleCancel.py ハンガリー法04-Hungarian.py
エドモンズ法05-Edmonds.py シンプレックス法06-Simplex.py
内点法07-InteriorPoint.py 分枝限定法08-BranchBound.py
動的最適化法09-DynamicOptimization.py クラスカル法10-Kruskal.py
ジョンソン法11-Johnson.py 局所探索法12-LocalSearch.py
多スタート局所探索法13-MultiStartLocalSearch.py 列生成法14-ColumnGeneration.py

実行

コマンドプロンプト画面で、解凍・保存した上記プログラムファイルを保存したディレクトリに入り、「pyhon ファイル名」とタイプします。

たとえばpython 01-Dijkstra.pyとします。

すべてのプログラムは、2通りの計算をして結果を比較しています。

結果が同じであれば「All OK」と出力されます。

「局所探索法」と「多スタート局所探索法」は、近似解法なので、常に厳密解は出ません。ランダムな問題を100間解いた場合の厳密解との一致率を出力します。「列生成法」も近似解法ですが、サンプルでは厳密解が得られています。

動作環境

WindowsのAnaconda（Python2.7およびPython3.4）にて動作確認をしています。

Anacondaおよびpulpのインストール方法

Anacondaを用いれば、Python本体と必要なライブラリを同時にインストールできます。
手順を下記に示します。
すでに別のPythonがインストールしてある場合には、環境変数のPATHからそのパスを削除しておいてください。

  • インターネットに接続し、管理者権限のあるユーザで進めてください。
  • Anacondaのダウンロード先(下記参照)からご自分のOSのインストーラーをダウンロードしてください。
    Python2.7とPython3.4のどちらでも構いませんが、Python3.4をおすすめします。
    また、OSが64ビット版では、32ビット版と64ビット版のどちらでも動きますが、64ビット版をおすすめします。
    OSが32ビット版では、32ビット版をお選びください。
  • ダウンロードしたインストーラー(例:Anaconda3-2.2.0-Windows-x86_64.exe)を 管理者として実行してください。基本的に「Next」を押していけば大丈夫です。
  • コマンドプロンプト画面で「conda update conda」を実行してください。
  • コマンドプロンプト画面で「conda update networkx numpy」を実行してください。
  • コマンドプロンプト画面で「pip install pulp」を実行してください。

ダウンロードリンク

免責事項

  • 本プログラムは、上記書籍の理解を助ける目的のサンプルプログラムです。
  • 完全に正しいことを証明するものではありません。
  • 直接販売することを除き、商用でも無料で利用できます。
  • 利用において、損害等が発生しても利用者の責任とします。
  • License: Python Software Foundation License

ページトップへ

ダウンロード