等代価捜索——川を渡る問題

このブログでは、川を渡る問題について説明します.具体的な問題は、(1)花(2)バッタ(3)カエル(4)ヘビ(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)鷹(5)誰も見ていなければ、鷹は蛇を食べ、蛇はカエルを食べ、カエルはバッタを食べ、バッタは花を破壊する.あなたの船は一度に最大であなたを除いた2つを乗せることができます.主にpythonコードの問題について説明します.
util.py
まず、データ構造の作成です.これは優先キューで、heapqライブラリの関数を具体的に使用しています.具体的にはPython標準ライブラリのheapqについて説明します.

import heaqp

#includeに相当し、このライブラリの関数を呼び出すことができます.

# Data structure for supporting uniform cost search.
class PriorityQueue:
    def  __init__(self):
        self.DONE = -100000
        self.heap = []
        self.priorities = {}  # Map from state to priority

    # Insert |state| into the heap with priority |newPriority| if
    # |state| isn't in the heap or |newPriority| is smaller than the existing
    # priority.
    # Return whether the priority queue was updated.
    def update(self, state, newPriority):
        oldPriority = self.priorities.get(state)
        if oldPriority == None or newPriority < oldPriority:
            self.priorities[state] = newPriority
            heapq.heappush(self.heap, (newPriority, state))
            return True
        return False

    # Returns (state with minimum priority, priority)
    # or (None, None) if the priority queue is empty.
    def removeMin(self):
        while len(self.heap) > 0:
            priority, state = heapq.heappop(self.heap)
            if self.priorities[state] == self.DONE: continue  # Outdated priority, skip
            self.priorities[state] = self.DONE
            return (state, priority)
        return (None, None) # Nothing left...

このコードでは、PriorityQueueクラスを構築し、姉がutilにカプセル化することに相当する.pyでは、import utilだけで関数を呼び出すことができます.def init(self)は、このクラスを初期化することに相当する.初期化中にDone、heap、prioritiesが設定され、Doneは比較に使用され、このノードが遍歴すると優先度がDoneに設定されます.heapはリストであり、この図の優先キューが格納されます.prioritiesは、mapに似たpythonのデータ構造に属する辞書です.update関数は、ステータスの優先度を変更します.このステータスが優先キューに含まれていない場合は、優先度を比較します.新しい優先度が長い優先度より小さい場合は、更新キューのこのステータスの優先度removeMinは、優先キューの優先度が最も小さい(Doneではない)ノードと優先度を返します.ノードの優先度をDoneに設定します.
CrossRiverProblem.py

import util

まずutilというファイルを呼び出すには、私たちが使いたい方法があります.

def allSubsets(s, limit):
    if len(s) == 0 or limit == 0:
        return [[]]
    return allSubsets(s[1:], limit) \
           + [[s[0]] + r for r in allSubsets(s[1:], limit-1)]

AllSubsets関数は、単純に1つのセットをすべてのサブセットに戻すことです(サブセットの長さはlimitより小さい).このうちここのlimitは船が一度に持ち運ぶことができる動物の数に相当します.eg:s=(1,4),return[(1,4),(1),(4),()という関数の書き方は再帰を用いており,まずsという集合の長さがゼロまたはlimitが0であれば空のリストを返すと判断した.0でなければこの関数を呼び出し続け、ここで「次の行を接続する」という意味です.[1:]はスライスで、[start:end]endのデフォルトを最後に選択し、startのデフォルトを0番目に選択します.すなわち、第1以外のすべての要素が選択され、対応するlimitが1減少し、すなわち[1:]において長さlimit−1または長さがlimit−1未満のサブセットが選択される.次にlimit-1のフィルタリングのために1つの要素を除去します.すなわち、s[0]でフィルタされた要素を結合する.pythonでは、リスト加算は、c++のstring加算と同様にマージに相当します.例を挙げる

nums1 = [1,2]
nums2 = [2,3]
nums = nums1+nums2
print(nums)

out:[1,2,2,3]この関数は農夫が動植物を持ち去ることができる集合を返した.

class CrossRiverProblem:
    # what is a state e.g. ((1,1,1,1,1), 0),((0,1,1,0,1), 0)
    # state   
    def __init__(self, N, S):
        self.N = N #N=5
        self.S = S #S=2

    # Return start state ((0,0,0,.....,0),0)
    def startState(self):
        return (tuple(0 for _ in range(self.N)), 0)

    # Return TRUE if state is a goal state ((1,1,.....,1),1)
    def isEnd(self, state):
        return state == ((tuple(1 for _ in range(self.N))), 1)
    # Return a list of successor states and costs
    # (        of state）
    def succAndCost(self, state):
        print("expand: " + str(state))
        animals = state[0]
        ship = state[1]
        result = []
        for s in allSubsets([i for i in range(self.N) if animals[i] == ship], self.S):
            temp = list(animals)
            for i in s:
                temp[i] = 1-ship

            newState = (tuple(temp), 1-ship)
            if self.isValidState(newState):
                result.append((newState, 1))
        return result

    def isValidState(self, state):
        animals = state[0]
        ship = state[1]
        for i in range(self.N - 1):
            if animals[i] != ship and animals[i+1] != ship:
                return False
        return True

まず、Nは農夫以外のすべての動植物であり、Sは農夫が一度に川を渡ることができる最大数である.(この問題ではNは5 Sが2)startStateは、初期状態の元グループに戻り、最初は農夫とすべての動植物が川を渡っていなかったことを知っていたので、状態はすべて0で、ここで農夫を単独で1つの要素に設定した.したがって,(0,0,0,0,0),0)isEndは終了するか否かを判定し,終了しない場合はメタグループに0が含まれているので,ここでメタグループ全1と比較した結果を返す.まずisValidStateという関数について述べ,現在の状態が安全状態に合致しているか否かを判断し,状態が隣接する動植物が河岸にあり農夫がいない場合は不安全状態である.state[0]は動物の位置であり、初期状態state[0]が(0,0,0,0),state[1]=0であると仮定する.succAndCost関数は、農夫と対岸の動植物の集合選択、すなわち最初のallSubsets関数を選択し、農夫の位置を入れ替え(ゼロからゼロへ、ゼロから1へ、ここでは減算)し、安全状態に合致するか否かを判断し、合致すればresultに追加する.append((newState,1))は、(newState,1)メタグループをresultに追加します.

#      
# (TotalCost of optimal solution, history of solution)
def uniformCostSearch(problem):
    state = problem.startState()
    open = util.PriorityQueue()
    open.update(state, 0)
    while True:
        state, pastCost = open.removeMin()
        if problem.isEnd(state):
            print("Total cost: " + str(pastCost))
            return pastCost, []
        for newState, cost in problem.succAndCost(state):
            open.update(newState, pastCost + cost)

等代価検索,openはutilに書かれた優先キュークラスであり,アルゴリズムに対応するopenテーブルである.そして等代価検索を行います.