Archives of learned topics

Lesson4-4: Pouring Problem

目次


問題のイメージ


良くありがちな、二つの容器を使用して特定の分量を測定してくださいという問題。 問題を解く方向性としては、探索問題となる。 Imgur
既に探索した領域を記憶し、新たな領域を探索するイメージ

実装

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)))