BFS解小孩分油问题

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

 

1. 用N表示初始结点列表(N待扩展)
2. 如果N为空集，则退出并给出失败信号
3. n取为N的第一个结点，并在N中删除结点n，放入已访问结点列表
4. 如果n为目标结点，则退出并给出成功信号
5. 否则，将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<StateNode> stateList = new ArrayList<StateNode>(); // 存放所有出现过的状态的数组

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]

完整代码见附件