和尚和妖怪过河问题

[likebeta]

有3个和尚和3个妖怪需要过河。河边有一个小船，小船一次最多载两个。任意时间船上和河岸两侧出现妖怪比和尚多时，妖怪都会吃掉和尚。帮忙给出和尚和妖怪安全过河的方法。
这个问题和3个桶等分8升水类似。只是这里不需要区分每个个体，只用把和尚和妖怪的人数抽象下就行。下面用穷举法求出所有过河方法。

状态模型

我们可以用5元组[monk, monster, remote_monk, remote_monster, position]来抽象当前的状态，分别对应河边的和尚和妖怪，对岸的和尚和妖怪，船的位置。那么初始状态就是[3, 3, 0, 0, 1]，终止状态就是就是[0, 0, 3, 3, 0]。其实我们是可以用3元组[monk, monster, position]表示状态的, 因为和尚和妖怪都不会凭空消失。但是5元组可以很清晰，更直观，下面用5元组为例。

过河动作模型

过河动作分为过河和返回。我们可以用正负来统一这两种行为。动作模型可以抽象成3元组[和尚数量, 妖怪数量, 方向]。比如1个妖怪和1个和尚过河可以表示为[-1, -1, -1]， 1一个妖怪和1一个和尚返回可以表示为[1, 1, 1]。和状态模型相同， 这里也可以使用2元组表示动作模型， 也就是不要方向这个变量，根据正负来判断方向。3元组可以更容易的进行一致性处理，本例也是使用3元组。

实现

#!/usr/bin/env python
# -*- coding=utf-8 -*-

# Author: likebeta <ixxoo.me@gmail.com>
# Create: 2016-08-06

POSITION_LEFT = 1
POSITION_RIGHT = 0

DIRECTION_LEFT = 1
DIRECTION_RIGHT = -1


class State(object):
    def __init__(self, monk, monster, remote_monk, remote_monster, direction):
        self.monk = monk
        self.monster = monster
        self.remote_monk = remote_monk
        self.remote_monster = remote_monster
        self.direction = direction

    def clone(self):
        return State(self.monk, self.monster, self.remote_monk, self.remote_monster, self.direction)

    def __eq__(self, other):
        return self.direction == other.direction and \
               self.monk == other.monk and \
               self.monster == other.monster and \
               self.remote_monk == other.remote_monk and \
               self.remote_monster == other.remote_monster

    def __ne__(self, other):
        return not self.__eq__(other)

    def __str__(self):
        return '[%d, %d, %d, %d, %d]' % (self.monk, self.monster, self.remote_monk, self.remote_monster, self.direction)

    __repr__ = __str__


class Action(object):
    def __init__(self, monk, monster, direction, desc):
        self.monk = monk
        self.monster = monster
        self.direction = direction
        self.desc = desc

    def clone(self):
        return Action(self.monk, self.monster, self.direction, self.desc)


class Step(object):
    def __init__(self, state):
        self.state = state.clone()
        self.action = None

    def do_action(self, action):
        self.action = action.clone()
        self.state.monk += action.monk
        self.state.monster += action.monster
        self.state.remote_monk -= action.monk
        self.state.remote_monster -= action.monster
        self.state.direction += action.direction

    def __eq__(self, other):
        return self.state == other.state

    def __ne__(self, other):
        return not self.__eq__(other)


class Algorithm(object):
    def __init__(self, monk, monster):
        self.start = State(monk, monster, 0, 0, POSITION_LEFT)
        self.end = State(0, 0, monk, monster, POSITION_RIGHT)
        self.actions = [
            Action(-1, 0, -1, u'1个和尚过河'),
            Action(-2, 0, -1, u'2个和尚过河'),
            Action(-1, -1, -1, u'1个和尚和1个妖怪过河'),
            Action(0, -1, -1, u'1个妖怪过河'),
            Action(0, -2, -1, u'2个妖怪过河'),
            Action(1, 0, 1, u'1个和尚返回'),
            Action(2, 0, 1, u'2个和尚返回'),
            Action(1, 1, 1, u'1个和尚和1个妖怪返回'),
            Action(0, 1, 1, u'1个妖怪返回'),
            Action(0, 2, 1, u'2个妖怪返回'),
        ]

    def search(self, stack=None):
        if stack is None:
            stack = [Step(self.start)]
        curr = stack[-1]
        if self.is_finished(curr):
            self.print_result(stack)
            return
        for action in self.actions:
            self.step_it(stack, curr, action)

    def step_it(self, stack, current, action):
        new_step = self.do_action(current.state, action)
        if new_step:
            if not self.is_processed_step(stack, new_step):
                stack.append(new_step)
                self.search(stack)
                stack.pop()

    def do_action(self, current, action):
        new_step = Step(current)
        new_step.do_action(action)
        state = new_step.state
        if state.direction != POSITION_LEFT and state.direction != POSITION_RIGHT:
            return False
        if state.monk < 0 or state.monster < 0 or state.remote_monk < 0 or state.remote_monster < 0:
            return False
        if 0 < state.monk < state.monster or 0 < state.remote_monk < state.remote_monster:
            return False
        return new_step

    def is_finished(self, current):
        return current.state == self.end

    def is_processed_step(self, stack, new_step):
        for one in stack:
            if one == new_step:
                return True
        return False

    def print_result(self, stack):
        print (u'需要%d步' % (len(stack) - 1)).encode('utf-8')
        for step in stack:
            if step.action:
                s = step.action.desc
            else:
                s = ''
            print (u'%s <== %s' % (step.state, s)).encode('utf-8')
        print '\n'


if __name__ == '__main__':
    alg = Algorithm(3, 3)
    alg.search()

运行可以看到只有4种方法，都是11步。