BFS解小孩分油问题-白红宇

BFS解小孩分油问题

阅读量：2395 次

发布时间：2019-05-10

本文共 2195 字，大约阅读时间需要 7 分钟。

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

用N表示初始结点列表(N待扩展)

如果N为空集，则退出并给出失败信号

n取为N的第一个结点，并在N中删除结点n，放入已访问结点列表

如果n为目标结点，则退出并给出成功信号

否则，将n的子结点加到N的末尾，并返回2步

分油问题描述:

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

分油问题的Java实现:

1、对问题建模：问题中的实体对象是空瓶，建立Bottle对象，包含空瓶容量以及当前油量属性

int volume = 0;int oil = 0;

2、确定分油的可行方式，并确定分油规则

switch (n) {case 1: // 瓶子1向瓶子2倒油	if (!bottle1.isEmpty() && !bottle2.isFull()) {		n = bottle2.needForFull() <= bottle1.oil ? bottle2				.needForFull() : bottle1.oil;		newState = new StateNode(bottle1.oil - n, bottle2.oil + n,				bottle3.oil, this);	}	break;case 2: // 瓶子1向瓶子3倒油	if (!bottle1.isEmpty() && !bottle3.isFull()) {		n = bottle3.needForFull() <= bottle1.oil ? bottle3				.needForFull() : bottle1.oil;		newState = new StateNode(bottle1.oil - n, bottle2.oil,				bottle3.oil + n, this);	}	break;case 3: // 瓶子2向瓶子1倒油	if (!bottle2.isEmpty() && !bottle1.isFull()) {		n = bottle1.needForFull() <= bottle2.oil ? bottle1				.needForFull() : bottle2.oil;		newState = new StateNode(bottle1.oil + n, bottle2.oil - n,				bottle3.oil, this);	}	break;case 4: // 瓶子2向瓶子3倒油	if (!bottle2.isEmpty() && !bottle3.isFull()) {		n = bottle3.needForFull() <= bottle2.oil ? bottle3				.needForFull() : bottle2.oil;		newState = new StateNode(bottle1.oil, bottle2.oil - n,				bottle3.oil + n, this);	}	break;case 5: // 瓶子3向瓶子1倒油	if (!bottle3.isEmpty() && !bottle1.isFull()) {		n = bottle1.needForFull() <= bottle3.oil ? bottle1				.needForFull() : bottle3.oil;		newState = new StateNode(bottle1.oil + n, bottle2.oil,				bottle3.oil - n, this);	}	break;case 6: // 瓶子3向瓶子1倒油	if (!bottle3.isEmpty() && !bottle2.isFull()) {		n = bottle2.needForFull() <= bottle3.oil ? bottle2				.needForFull() : bottle3.oil;		newState = new StateNode(bottle1.oil, bottle2.oil + n,				bottle3.oil - n, this);	}	break;}

3、在上述的规则，即广度优先搜索的搜索空间中，寻找目标状态。为提高搜索效率，可记住已经搜索过的节点，避免重复搜索，进入无限循环。

ArrayList
    
      stateList = new ArrayList
     
      (); // 存放所有出现过的状态的数组

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]

完整代码见附件

转载地址：http://ovwob.baihongyu.com/

你可能感兴趣的文章