Python入門トップページ


目次

  1. 「ゴチ」バトルの問題
  2. ナップサック問題と両替問題
  3. 準備
  4. Python で問題を解く
  5. ファイルを読み込んで問題を解く
  6. 遺伝的アルゴリズムを実装する
  7. 参考資料

「ゴチ」バトル

準備

前述の通り「ゴチ」バトルの問題ナップサック問題の一種である.Python では ortoolpy (OR の Tool という意味) モジュールをインポートすれば,ナップサック問題を簡単かつ高速に解くことができる.

ortoolpy は anaconda をインストールしただけではインストールされていないので,まずは ortoolpy を pip によってインストールする.ortoolpy のインストールは「Anaconda PowerShell」または「Anaconda Prompt」で pip install ortoolpy を実行すれば良い.なお,学内の情報処理実習室では pip install ortoolpy --user のように --user オプションを指定する必要があるかもしれません.また,インストールされているモジュールの一覧は pip list で確認できる.なお,Jupyter Notebook のマジックコマンドを利用しても構いません.

目次に戻る

Anaconda Prompt で ortoolpy をインストール

Anaconda Promptを起動し(Anaconda のインストール時にパスを通している場合は コマンドプロンプトや Windows PowerShell でも可能),pip list コマンドを使って現在インストールされているパッケージの一覧を表示する.

(base) C:\Users\bk182005>pip list ⏎
Package                            Version
---------------------------------- --------
alabaster                          0.7.12
anaconda-client                    1.7.2
anaconda-navigator                 1.9.7
anaconda-project                   0.8.2
asn1crypto                         0.24.0
astroid                            2.2.5
astropy                            3.1.2
atomicwrites                       1.3.0
attrs                              19.1.0
Babel                              2.6.0
backcall                           0.1.0
backports.os                       0.1.1

...(中略)...

wrapt                              1.11.1
xlrd                               1.2.0
XlsxWriter                         1.1.5
xlwings                            0.15.4
xlwt                               1.3.0
zict                               0.1.4
zipp                               0.3.3

(base) C:\Users\bk182005>

上のコマンドでパッケージの一覧を表示したが,その中から ortoolpy があるかどうかを探すことは手間がかかる.うまく検索できれば短時間で調べることができる.検索には,find コマンドで検索するとよい.なお,以下のコマンドで list | find| は縦棒で,パイプの記号とも呼ばれる.キーボードからは「Shift」 + 「\」で入力できる.

(base) C:\Users\bk182005>pip list | find "ortoolpy" ⏎

(base) C:\Users\bk182005>

まだ ortoolpy がインストールされていないことが確認できたので,pip install ortoolpy と入力してイントールする.なお,学内から多数の学生がほぼ同時にインストールしようとすると,特定のサイトにアクセスが集中するため大変時間がかかったり,その結果タイムアウトになることがある.このような場合は Ctrl + C で強制終了させた後,時間をおいて再度インストールのコマンドを実行すると良い.

(base) C:\Users\bk182005>pip install ortoolpy ⏎
Collecting ortoolpy
  Downloading https://files.pythonhosted.org/packages/63/78/34a9085a40dc7aa973cf
1ec26699172a1f5c6c2c20139e5eabbea3140e6c/ortoolpy-0.2.23.tar.gz
Collecting pulp (from ortoolpy)
  Downloading https://files.pythonhosted.org/packages/2d/33/3ae6d9d2ac8c7068937a
f6372fd8828ac605e62a8b17106fe57110930d38/PuLP-1.6.10.zip (13.6MB)
    100% |████████████████████████████████| 13.6MB 1.2MB/s
Requirement already satisfied: pyparsing>=2.0.1 in c:\users\bk182005\appdata\loc
al\continuum\anaconda3\lib\site-packages (from pulp->ortoolpy) (2.3.1)
Building wheels for collected packages: ortoolpy, pulp
  Building wheel for ortoolpy (setup.py) ... done
  Stored in directory: C:\Users\bk182005\AppData\Local\pip\Cache\wheels\a1\b8\3a
\9effdb7e92db6030c7cd1022b95ee05dd01c7281734645f3dc
  Building wheel for pulp (setup.py) ... done
  Stored in directory: C:\Users\bk182005\AppData\Local\pip\Cache\wheels\5e\76\77
\e28b22219e46e3b4b033f02e8b36b2770ae545bdcf60c2b224
Successfully built ortoolpy pulp
Installing collected packages: pulp, ortoolpy
Successfully installed ortoolpy-0.2.23 pulp-1.6.10

(base) C:\Users\bk182005>

場合によっては次のように EnvironmentError: [WinError 5] アクセスが拒否されました。と表示されるかもしれません.(これは pandas のアップデートがユーザ権限では実行できないためだと思われます.)

(base) C:\Users\bk182005>pip install ortoolpy ⏎
Collecting ortoolpy
  ...(中略)...
Installing collected packages: pulp, pandas, ortoolpy
  Attempting uninstall: pandas
    Found existing installation: pandas 1.1.3
    Uninstalling pandas-1.1.3:
ERROR: Could not install packages due to an EnvironmentError: [WinError 5] アクセスが拒否されました。: 'c:\\programdata\\anaconda3\\lib\\site-packages\\pandas-1.1.3.dist-info\\direct_url.json'
Consider using the `--user` option or check the permissions.

(base) C:\Users\bk182005>

そのような場合は --user オプションを指定してインストールを実行してください.

(base) C:\Users\bk182005>pip install ortoolpy --user ⏎
Collecting ortoolpy
  ...(中略)...
Installing collected packages: pandas, ortoolpy
Successfully installed ortoolpy-0.2.38 pandas-1.4.3

(base) C:\Users\bk182005>

正しくインストールされているか確認する.

(base) C:\Users\bk182005>pip list | find "ortoolpy" ⏎
ortoolpy                           0.2.38

(base) C:\Users\bk182005>

目次に戻る

仮想開発環境で ortoolpy をインストール

ここの手順を参考に構築した仮想開発環境(あるいは Mac)でもほぼ同様の方法でインストール可能です. まず,pip list コマンドを使って現在インストールされているパッケージの一覧を表示する.

% vagrant ssh ⏎
Last login: Tue Mar 30 09:29:15 2021 from 10.0.2.2
[vagrant@centos8 ~]$ pip list ⏎
Package                            Version
---------------------------------- -------------------
alabaster                          0.7.12
anaconda-client                    1.7.2
anaconda-navigator                 1.10.0
anaconda-project                   0.8.3

(中略)

zict                               2.0.0
zipp                               3.4.0
zope.event                         4.5.0
zope.interface                     5.1.2
[vagrant@centos8 ~]$

上のコマンドでパッケージの一覧を表示したが,その中から ortoolpy があるかどうかを探すことは手間がかかる.うまく検索できれば短時間で調べることができる.Linux や Mac の場合は,grep コマンドで検索するとよい.なお,以下のコマンドで list | grep| は縦棒で,パイプの記号とも呼ばれる.キーボードからはShift + ¥で入力できる.

[vagrant@centos8 ~]$ pip list | grep ortoolpy ⏎
[vagrant@centos8 ~]$

まだ ortoolpy がインストールされていないことが確認できたので,pip install ortoolpy と入力してイントールする.

[vagrant@centos8 ~]$ pip install ortoolpy ⏎
Collecting ortoolpy
  Downloading ortoolpy-0.2.38-py3-none-any.whl (24 kB)
Collecting pandas<2.0.0,>=1.1.4
  Downloading pandas-1.2.3-cp38-cp38-manylinux1_x86_64.whl (9.7 MB)
     |████████████████████████████████| 9.7 MB 3.0 MB/s
Requirement already satisfied: more-itertools<9.0.0,>=8.6.0 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from ortoolpy) (8.6.0)
Collecting pulp<3.0.0,>=2.3.1
  Downloading PuLP-2.4-py3-none-any.whl (40.6 MB)
     |████████████████████████████████| 40.6 MB 760 kB/s
Requirement already satisfied: numpy>=1.16.5 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from pandas<2.0.0,>=1.1.4->ortoolpy) (1.19.2)
Requirement already satisfied: python-dateutil>=2.7.3 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from pandas<2.0.0,>=1.1.4->ortoolpy) (2.8.1)
Requirement already satisfied: pytz>=2017.3 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from pandas<2.0.0,>=1.1.4->ortoolpy) (2020.1)
Collecting amply>=0.1.2
  Downloading amply-0.1.4-py3-none-any.whl (16 kB)
Requirement already satisfied: six>=1.5 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from python-dateutil>=2.7.3->pandas<2.0.0,>=1.1.4->ortoolpy) (1.15.0)
Requirement already satisfied: docutils>=0.3 in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from amply>=0.1.2->pulp<3.0.0,>=2.3.1->ortoolpy) (0.16)
Requirement already satisfied: pyparsing in ./.pyenv/versions/anaconda3-2020.11/lib/python3.8/site-packages (from amply>=0.1.2->pulp<3.0.0,>=2.3.1->ortoolpy) (2.4.7)
Installing collected packages: pandas, amply, pulp, ortoolpy
  Attempting uninstall: pandas
    Found existing installation: pandas 1.1.3
    Uninstalling pandas-1.1.3:
      Successfully uninstalled pandas-1.1.3
Successfully installed amply-0.1.4 ortoolpy-0.2.38 pandas-1.2.3 pulp-2.4
[vagrant@centos8 ~]$

正しくインストールされているか確認する.

[vagrant@centos8 ~]$ pip list | grep ortoolpy ⏎
ortoolpy                           0.2.38
[vagrant@centos8 ~]$

目次に戻る