用回溯法求“韩信分油”问题所有解

裴南平

摘要：回溯法是一种常用的计算机程序设计方法。使用回溯法解决“韩信分油问题”也称“泊松分酒问题”，在算法中保存每一步执行的中间结果，程序扩展前，判斷程序是否进入“循环圈”，程序一旦进入“循环圈”，就不需要往下扩展，开始回溯了。如果能合理设计扩展的条件，防止程序陷入“循环圈”可以提高程序的效率。

关键词：算法；回溯法；泊松分酒；循环圈

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）34-0248-03

Abstract： Backtracking is a commonly used method of computer programming. The use of backtracking method to solve the "Han oil" also known as the " Poisson wine problem"， save every step of execution of the intermediate results in the algorithm， the expansion of the program before the procedure to determine whether to enter the "circle"， once the program into the circle， do not need to expand down and start backtracking. if can design reasonable expansion conditions to prevent the program into a "circle" can improve the efficiency of the program.

Key words： algorithm； backtracking method； Poisson wine； cycle ring

1 背景

韩信是家喻户晓的汉朝名将，聪明过人。传说有一天他骑马路过街市，见有二人争吵，下马细问，原来是一个卖油的只带了十斤、七斤、五斤三个油壶，十斤油壶装满了油，七斤、五斤油壶空的，没有带秤具，对方只想买一半，正为无法分出五斤油成交争执。韩信略加思考，立马给出了解决办法。

这其实是一个利用二个空的小容器将一个满的大容器均分的问题。法国数学家、物理学家和力学家泊松曾提出并研究该类问题，所以也称“泊松分酒问题”。

2 解题算法分析

计算机解决该类问题当然不需要用泊松研究的数学方法，只要利用自身强大快速的计算能力将所有的情况遍历，从而找出问题的所有解。

“韩信分油问题”的解是一步一步的步骤，例如韩信当时给出的分油办法如图1所示。

韩信的方法总共八步，当然解题方法不止一种，而且步骤可能是八步，也可能是九步、十步、...，由于每个解的步骤不相同，使用普通的穷举法无法实现，只能使用回溯法来穷举实现。

我们用a代表十斤油壶，b代表七斤油壶，c代表三斤油壶。进行下一步操作共有如下六种可能：

1） a倒入b；

2） a倒入c；

3） b倒入a；

4） b倒入c；

5） c倒入a；

6） c倒入b。

求解的每一步都市这六种可能的穷举，就这样一部一部扩展，直到某个油壶正好是要分的一半五斤油，就找到了一个解。

不过扩展到哪一步为止？然后回溯，正式文本论述的关键所在。普通的回溯法都是扩展到某一固定层数就开始回溯。分油问题因为每个解步数不相同，所以无法扩展到某一固定步数就开始回溯。当然可以规定到了足够多的n步开始回溯，但是n就不好定了，太小了可能漏掉解，太大了如n=50，就要穷举6的50次方，费事太长，普通的电脑短时间无法找到所有解。

当进行到某一步时三个油壶的油量与前面经历的某一步相同，可以称之为进入“循环圈”。一步一步扩展下去，如果没有找到解停下并回溯，肯定会进入“循环圈”。一旦进入“循环圈”，就不需要往下扩展，就可以回溯了。这样做，不但合理地设定了扩展的终止条件，而且大大提高了求解的效率，因为跳过了很多无聊的步骤，如一个油壶倒入另一油壶，立马又倒回来。

3 C语言完整程序

4 结束语

通过运行上面程序，可以求出“韩信分油问题”共有十七个不同的解，最长步骤的解要十七步，最短步骤的解只需要八步，也就是韩信给出的办法。

参考文献：

[1] 李青， 张军， 张学军. 解决排班问题的多目标优化模型及算法研究[J]. 北京航空航天大学学报， 2003（10）.

[2] 谢玉庚. 用回溯法编程求解爱因斯坦谜题[J]. 电脑与电信， 2016（10）.

[3] 徐永琳， 巫青山， 林川. 递归回溯法求解整数线性规划及MATLAB实现[J]. 兰州文理学院学报：自然科学版， 2014（7）.endprint