小孩分油问题

题目：

两个小孩去打油，一个人带了一个一斤的空瓶，另一个带了一个七两、一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，在回家的路上，两人想平分这一斤油，可是又没有其它工具，试仅用三个瓶子（一斤、七两、三两）精确地分成两个半斤油来。

算法设计：

设置三个油瓶分别为A, B, C，初始化三个油瓶的初始状态(10,0,0)，满油状态(10,7,3)，目标状态(5,5,0)。使用广度优先的搜索方法，对每一种可能情况进行遍历，最终取得结果。其中，对于每一种情况对应每一步操作，操作需要满足一定的约束条件：把A瓶中的油全部倒入B瓶或者把A瓶中的油部分倒入B瓶使B瓶满油。具体的约束条件见程序流程。本算法由python实现。

程序流程：

1.png

序号	规则	解释
1	(B,C) and B<7 -> (7,C)	B瓶不满的时候装满
2	(B,C) and C<3 -> (B,3)	C瓶不满的时候装满
3	(B,C) and B>0 -> (0,C)	B瓶不满的时候装满
4	(B,C) and C>0 -> (B,0)	C瓶不满的时候装满
5	(B,C) and B>0 and B+C<=3 -> (0,B+C)	B瓶的油全倒入C瓶
6	(B,C) and C>0 and B+C<=7 -> (B+C,0)	C瓶的油全倒入B瓶
7	(B,C) and B>0 and B+C>=3 -> (B+C-3,3)	B瓶的油全倒入C瓶
8	(B,C) and C>0 and B+C>=7 -> (7,B+C-7)	C瓶的油全倒入B瓶

1.png

核心伪代码：

Def 下一步：
下一个操作 = [
        (倒出瓶标签, 倒入瓶标签)
        for 倒出瓶标签 range(3) for 倒入瓶标签 in range(3)
if 倒入/出瓶标签不能相同 and 倒出的瓶不为空 and 已经满了的瓶不能再倒入    ]

    for 倒出瓶标签, 倒入瓶标签 in 下一步操作:
        if 倒出倒入瓶由量之后不超过倒入瓶最大容量
            倒出瓶油量 -= (倒入瓶最大容量-倒入瓶现有油量)
            倒入瓶油量 = 倒入瓶最大容量
        else:
            倒出瓶油量 = 0
            倒入瓶油量 = 倒入瓶现有油量 + 倒出瓶现有油量
        yield 下一步

Def 搜索结果:
for 操作in 下一步:
        if 没有试过该操作:
            将该操作加入队列
            if 当前结果== 目标结果:
              输出结果
            else:
                递归本函数‘搜索结果’
            删除队列最后一个

代码运行及测试：

·.png

结论：

由代码运行结果可知：整棵树一共有20种方法能够达到要求，其中最佳即路径最短的方法为第9种方法。

第9种方法:[10, 0, 0]->[3, 7, 0]->[3, 4, 3]->[6, 4, 0]->[6, 1, 3]->[9, 1, 0]->[9, 0, 1]->[2, 7, 1]->[2, 5, 3]->[5, 5, 0]

具体做法为：

​ 0) 初始化-->[10, 0, 0]
​ 1) A瓶倒满B瓶-->[3, 7, 0]
​ 2) B瓶倒满C瓶-->[3, 4, 3]
​ 3) C瓶倒满A瓶-->[6, 4, 0]
​ 4) B瓶倒满C瓶-->[6, 1, 3]
​ 5) C瓶倒满A瓶-->[9, 1, 0]
​ 6) B瓶倒满C瓶-->[9, 0, 1]
​ 7) A瓶倒满B瓶-->[2, 7, 1]
​ 8) B瓶倒满C瓶-->[2, 5, 3]
​ 9) C瓶倒满A瓶-->[5, 5, 0]

源代码：

'''
@author: 嘿芝麻

@software: garner
@file: main_oil.py
@time: 2018/10/5
'''
from collections import deque

def nextStep(current_state, oil_volume):
    next_action = [
        (from_, to_)
        for from_ in range(3) for to_ in range(3)
        if from_ != to_ and current_state[from_] > 0 and current_state[to_] < oil_volume[to_]
    ]

    for from_, to_ in next_action:
        next_state = list(current_state)
        if current_state[from_] + current_state[to_] > oil_volume[to_]:
            next_state[from_] -= (oil_volume[to_] - current_state[to_])
            next_state[to_] = oil_volume[to_]
        else:
            next_state[from_] = 0
            next_state[to_] = current_state[to_] + current_state[from_]
        yield next_state


def searchResult(record, oil_volume=[10, 7, 3], final_state=[5, 5, 0]):
    global num, record_list
    current_state = record[-1]
    next_stage = nextStep(current_state, oil_volume)

    for stage in next_stage:
        if stage not in record:
            record.append(stage)
            if stage == final_state:
                numm = num + 1
                s_numm = str(numm)
                str_record = ''
                for i in record:
                    str_record += str(i)
                    if i != [5, 5, 0]:
                        str_record += '->'
                print("方法{}:{}".format(s_numm, str_record))
                record_list.append(deque(record))
                num += 1
            else:
                searchResult(record, oil_volume, final_state)
            record.pop()


if __name__ == '__main__':
    initial_oil_state = [10, 0, 0]
    oil_volume = [10, 7, 3]
    num = 0
    record_list = []
    record = deque()
    record.append(initial_oil_state)
    searchResult(record)
    number = "广度优先搜索共有{}种方法".format(num)
    shortest = "路径最短的方法中操作步总数为{}".format(min([len(i) for i in record_list]))

    print(number)
    print(shortest)