BFS解小孩分油有关问题

BFS解小孩分油问题

广度优先搜索(Breadth-first Search)算法描述:

?

用N表示初始结点列表(N待扩展)如果N为空集，则退出并给出失败信号n取为N的第一个结点，并在N中删除结点n，放入已访问结点列表如果n为目标结点，则退出并给出成功信号否则，将n的子结点加到N的末尾，并返回2步

分油问题描述:两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两、一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，在回家的路上，二人想平分这一斤油，可是又没有其它工具。试仅用三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。
分油问题的Java实现:1、对问题建模：问题中的实体对象是空瓶，建立Bottle对象，包含空瓶容量以及当前油量属性

if (!tag) { // 如没出现过 加入状态队列和数组stateQueue.addFirst(newState);stateList.add(newState);}

??

测试结果:[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]

完整代码见附件?

查看更多 下一篇