Lesson4-4: Pouring Problem
目次
問題のイメージ
良くありがちな、二つの容器を使用して特定の分量を測定してくださいという問題。
問題を解く方向性としては、探索問題となる。
既に探索した領域を記憶し、新たな領域を探索するイメージ
実装
def pour_problem(X, Y, goal, start=(0, 0)): """ X and Y are the capacity oc glasses; (x, y) is current fill levels and represents a state. Hte goal is a level that can be in either glass. Start at start state and follow successors until we reach the goal. Keep track of frontier and previously explored; fail when no frontier """ if goal in start: return [start] explored = set() # set of states we have visited frontier = [[start]] # ordered list of paths we have blazed while frontier: path = frontier.pop(0) (x, y) = path[-1] for (state, action) in successors(x, y, X, Y).items(): if state not in explored: # the successors state has not be explored(don't re-explored) explored.add(state) path2 = path + [action, state] if goal in path2: return path2 else: frontier.append(path2) return Fail Fail = [] def successors(x, y, X, Y): assert x <= X and y <= Y return {(0, x + y) if x + y < Y else (x - (Y - y), y + (Y - y)) : 'x => y', (x + y, 0) if x + y < X else (x + (X - x), y - (X - x)) : 'x <= y', (x, Y): 'fill up y', (X, y): 'Fill up x', (0, y): 'empty y', (x, 0): 'empty x'} print(pour_problem(10, 12, (10, 6)))