「simpleai」とは
お手軽に探索アルゴリズムを実装可能なPythonのパッケージです。
https://pypi.org/project/simpleai/
下記によりインストールが可能です。
!pip install simpleai
探索アルゴリズムの実装イメージ
解きたい問題を定義し、使用したい探索アルゴリズムで解きます。
参考：https://simpleai.readthedocs.io/en/latest/search_problems.html
探索問題の定義
「simpleai.search.SearchProblem」というクラスを継承し、いくつかのメソッドをオーバーライドします。
SearchProblemクラスのオーバーライド
actions(cur_state)
「現在の状態」を受け取り、ゴールに向けた「アクション」をlist型で返す。最終状態または、これ以上進めない状態になった場合は空リストを返すのが通例。
result(cur_state, action)
「現在の状態」および「アクション」を受け取り、新しい状態を作りだして返します。
is_goal(cur_state)
ゴールに到達したかどうかを返します（True/False）。
cost(cur_state, action, next_state) ※任意
「現在の状態」と「アクション」および「次の状態（候補）」を受け取り、「現在の状態」から「次の状態」へ移る際のコストを返します。
heuristic(cur_state) ※任意
「現在の状態」を受け取り、ゴールまでの距離（残コスト）を返します。
アルゴリズムの実行
SearchProblemクラスをオーバーライドして問題を定義したクラスを、使用したい探索アルゴリズム用メソッドへ引き渡し呼び出します。
使用できる探索用アルゴリズムは下記の通りです。
いずれも「simpleai.search.traditional」というパッケージからimportします。
- astar
- breadth_first
- depth_first
- greedy
- iterative_limited_depth_first
- limited_depth_first
ざっくりとした処理の流れ
- actions()が呼び出され、次のアクション用リストを取得します。
- 次のアクション用リストからアクションを1つずつ取り出し、リスト長の回数だけresult()が呼び出されます。
- 各result()の結果に対しheuristic()やcost()、およびis_goal()を呼び出して、ゴールまでのコストを推定しながら次の状態が決定します。
- 手順の先頭に戻り、処理が繰り返されます。
「simple」による貪欲法のサンプルプログラム
貪欲法とは
局所最適選択する探索手法です。局所的に次のステップしか考慮せず、全体最適な最終解を考慮しません。つまり、ステップの都度、利益を最大化する選択を取り込んでいき解を得ます。そのため、多くの問題で全体最適な解にはたどり着けないですが、短時間でそれなりに全体最適解の近似解を得られることが期待されます。
お題
ここではよくある例として、金額（円）が与えられたときに、支払いに必要な効果の最小枚数を求める問題を解いてみます。
例えば、目標が「687円」として与えられたら、解として「500円×1枚、100円×1枚、50円×1枚、10円×3枚、5円×1枚、1円×2枚」が求まるような問題です。
探索問題定義クラスの実装
import simpleai.search as ss
class CoinsProblem(ss.SearchProblem):
def set_target(self, target_yen):
self.target_yen = target_yen
def actions(self, cur_state):
if cur_state < self.target_yen:
return [1, 5, 10, 50, 100, 500]
else:
# 目標金額を現在の金額が通りこしてしまったら次のアクションは空とする
return []
def result(self, cur_state, action):
# 現在の金額とアクション（選択されている硬貨）を合算して返す
return cur_state + action
def is_goal(self, cur_state):
return cur_state == self.target_yen
def heuristic(self, cur_state):
# 目標金額と現在の金額との差異（距離）を返す
return self.target_yen - cur_state
ソルバーを実行する
出力結果（list）の各要素のタプル[0]が、ステップ毎に選択された硬貨を示しています。
「500円×1枚、100円×1枚、50円×1枚、10円×3枚、5円×1枚、1円×2枚」を選択していることが分かります。
TARGET_YEN = 687
problem = CoinsProblem(initial_state=0)
problem.set_target(TARGET_YEN)
result = ss.greedy(problem)
print(result.path())
# 出力結果
[(None, 0), (500, 500), (100, 600), (50, 650), (10, 660), (10, 670), (10, 680), (5, 685), (1, 686), (1, 687)]
以上です。