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

56 数学通报 2015年 第 54卷 第 1期 完整状态转移图法求三桶分油问题全部解 彭世康 李春梅 彭金瑾。 (1．许 昌许继软件技术有限公司 100085；2．北京市海淀区西二旗小学 100085) 1 三桶分油 问题概述 形状更直观 ，能轻松地找 出最优解及其它要求 的 《轻巧夺冠优化训练．三年级数学 (上)(北 师 解．但是 ，它们之间还是有关联 的，即借助于几何 大版)》_】有一道动脑筋题 ：有 A、B、C三个油桶 ， 坐标状态 图可以快捷地绘制 出完整状态转移图． A桶可装 12千克油 ，B桶可装 8千克油 ，C桶可 为了便于说明完整状态转移 图解法 ，本文先 装 5千克油 ，现有 l2千克油全部装在 A桶 中，要 对下列术语进行解释． 将它分成两个 6千克油，请 问该如何来倒? 最大桶 ：指三个桶之间容积最大的一个桶． 该题实质是 ，没有可计量的量器 ，只有三个不 非最大桶 ：指三桶 中不是最大桶 的任意一个 规则的油桶 ，已知每个桶的容积 ，通过将油在三个 桶 ，它又分为最小桶和中间桶． 桶之间倒来倒去，把最大桶 的满桶油均分为两等 特殊装油桶 ：简称特殊桶 ，指一眼就能看出其 份，该如何进行倒油操作．这里的 “桶”是指一类不 现有装油量的桶．有两种特殊桶 ，即满油桶和空油 规则容器，可 以代指缸 、罐 、瓢 、箩等其他容器 ； 桶．满油桶简称满桶 ，指装满 了油 的桶 ，其装油量 “油”是指一类可细分的物品 ，可 以换为酒 、盐 、米 、 为该 桶 的容 积 ；空 油 桶 简称 空桶，指 没 有装 油 豆等物 品．本文 以此题为例，论述 了三桶分油 问题 的桶 ． 的简便解法 ，以及如何求取其全部的解． 普通装油桶：简称普通桶 ，指不能一眼就看 出 对于三桶分油 问题 ，文献l2 论述 了不定方 其现有装油量的桶．普通桶的装油量比空桶多 ，比 程法 ，即通过求解一个二元一次不定方程式的整 满桶少 ，只有通过分析计算才能得到其精确值． 数解来获得最优 的分油过程 ．文献[4 提 出图解 各桶装油状况 ：又称为油量状态，简称状态或 法，图解法也称为几何坐标法 ，分为二维平面坐标 状态点 ，指当前时刻三个桶的各桶实际装油量情 法和三维立体坐标法，是通过在直角坐标系中各 况．按照容积从大到小排列的三个桶 的实际装油 个状态点的转移关系图来求解． 量次序 ，用三维坐标值表示各桶装油状况． 本文提 出了一种新 的解法——完整状态转移 特殊状态 ：包括初始状态 、最终状态和特殊 中 图法．根据三个油桶所有可能 的中间阶段各桶装 间状态．初始状态指分油前各桶初始的装油状况 ； 油状况 ，以及这些中间装油状况之间的转移关 系， 最终状态指分油要求达 到的最终 的 目标装油状 可以绘制出全部 中间装油状况之间的完整的状态 况 ；特殊中间状态指分油过程 中出现的三个桶 中 转移路线图，即完整状态转移图．利用该图可 以轻 至少含有两个特殊桶的装油状态． 松地求取三桶分油 问题的全部解和各种特殊要求 普通状态 ：又称为普通中间状态 ，指分油过程 的解 ，如最优解 、最长解 、经过某一油量状 态的最 中出现 的三 个 桶 中只含有 一 个 特 殊 桶 的装 油 优解或全部解 、经过某一倒油操作 的最优解或全 状态． 部解 、符合指定倒油次数的全部解 ，等等． 顺序解 ：又称为