完整状态转移图法求三桶分油问题全部解

《完整状态转移图法求三桶分油问题全部解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、56数学通报2015年第54卷第1期完整状态转移图法求三桶分油问题全部解彭世康李春梅彭金瑾。(1．许昌许继软件技术有限公司100085；2．北京市海淀区西二旗小学100085)1三桶分油问题概述形状更直观，能轻松地找出最优解及其它要求的《轻巧夺冠优化训练．三年级数学(上)(北师解．但是，它们之间还是有关联的，即借助于几何大版)》_】有一道动脑筋题：有A、B、C三个油桶，坐标状态图可以快捷地绘制出完整状态转移图．A桶可装12千克油，B桶可装8千克油，C桶可为了便于说明完整状态转移图解法，本文先装5千克油，现有l2千克油全部装在A桶中，要

2、对下列术语进行解释．将它分成两个6千克油，请问该如何来倒?最大桶：指三个桶之间容积最大的一个桶．该题实质是，没有可计量的量器，只有三个不非最大桶：指三桶中不是最大桶的任意一个规则的油桶，已知每个桶的容积，通过将油在三个桶，它又分为最小桶和中间桶．桶之间倒来倒去，把最大桶的满桶油均分为两等特殊装油桶：简称特殊桶，指一眼就能看出其份，该如何进行倒油操作．这里的“桶”是指一类不现有装油量的桶．有两种特殊桶，即满油桶和空油规则容器，可以代指缸、罐、瓢、箩等其他容器；桶．满油桶简称满桶，指装满了油的桶，其装油量“油”是指一类可细分的物品，可以换

3、为酒、盐、米、为该桶的容积；空油桶简称空桶，指没有装油豆等物品．本文以此题为例，论述了三桶分油问题的桶．的简便解法，以及如何求取其全部的解．普通装油桶：简称普通桶，指不能一眼就看出对于三桶分油问题，文献l2论述了不定方其现有装油量的桶．普通桶的装油量比空桶多，比程法，即通过求解一个二元一次不定方程式的整满桶少，只有通过分析计算才能得到其精确值．数解来获得最优的分油过程．文献[4提出图解各桶装油状况：又称为油量状态，简称状态或法，图解法也称为几何坐标法，分为二维平面坐标状态点，指当前时刻三个桶的各桶实际装油量情法和三维立体坐标法，是通过

4、在直角坐标系中各况．按照容积从大到小排列的三个桶的实际装油个状态点的转移关系图来求解．量次序，用三维坐标值表示各桶装油状况．本文提出了一种新的解法——完整状态转移特殊状态：包括初始状态、最终状态和特殊中图法．根据三个油桶所有可能的中间阶段各桶装间状态．初始状态指分油前各桶初始的装油状况；油状况，以及这些中间装油状况之间的转移关系，最终状态指分油要求达到的最终的目标装油状可以绘制出全部中间装油状况之间的完整的状态况；特殊中间状态指分油过程中出现的三个桶中转移路线图，即完整状态转移图．利用该图可以轻至少含有两个特殊桶的装油状态．松地求取三

5、桶分油问题的全部解和各种特殊要求普通状态：又称为普通中间状态，指分油过程的解，如最优解、最长解、经过某一油量状态的最中出现的三个桶中只含有一个特殊桶的装油优解或全部解、经过某一倒油操作的最优解或全状态．部解、符合指定倒油次数的全部解，等等．顺序解：又称为从小到大次序分油解，指持续图解法的几何坐标状态图只能求解三桶分油而循环地按照从小桶往大桶倒油的规则来分油而问题的顺序解与逆序解，并通过比较二者的倒油获得的解．次数来获取问题的最优解．完整状态转移图比几逆序解：又称为从大Nil,次序分油解，指持续何坐标状态图具有两大优势：一是功能更强大，

6、能而循环地按照从大桶往小桶倒油的规则来分油而求取问题的全部解以及各种特殊要求的解；二是获得的解．2015年第54卷第1期数学通报57最优解：又称为最短解，指倒油操作次数最少个特殊状态中的一个或两个点．这种单向转移关的解．系，通过图中与状态点对应的状态值下面的“一”最长解：指倒油操作次数最多的解．之后的特殊状态点编号来标示．例如中间状态值对于三桶分油问题，本文约定一个正确的解(2，8，2)下面的“一C，D”，表示该状态点可以单向为一个开环解，即整个倒油过程中任意一种中间转移到特殊状态C点和D点．阶段油量状态只能出现一次，不能出现两次以上

7、．由完整状态转移图可知：本文示例分油问题如果某一个倒油过程中出现了重复的油量状的任何一个从O点至E点的解，必定首先经过A态(称之为一个闭环解)，则必须将通往重复的油点或D点，最后到达C点或D点，并经由以下两量状态方向转移的倒油操作全部删除掉，从而获条路径之一抵达E点．得一个开环解．本文不考虑闭环解，只考虑开环路径1：C一(8，0，4)一(8，4，0)一(3，4，5)解，并认为只有开环解才是正确的解．一(3，8，1)一(11，0，1)一(11，1，0)一(6，1，5)一个三桶分油问题可以存在多个解，不同的一E解对应于不同的的油量状态序列

8、．路径2：D一(4，3，5)一(9，3，0)一(9，0，3)2完整状态转移图一(1，8，3)一(1，6，5)一E根据三桶分油问题的倒油规律，可以求出三本文以“Ec⋯E3”代表8步倒油操作的路径个油桶所有可能的中间油量状态