- 浏览: 554773 次
- 性别:
- 来自: 济南
文章分类
- 全部博客 (270)
- Ask chenwq (10)
- JSF (2)
- ExtJS (5)
- Life (19)
- jQuery (5)
- ASP (7)
- JavaScript (5)
- SQL Server (1)
- MySQL (4)
- En (1)
- development tools (14)
- Data mining related (35)
- Hadoop (33)
- Oracle (13)
- To Do (2)
- SSO (2)
- work/study diary (10)
- SOA (6)
- Ubuntu (7)
- J2SE (18)
- NetWorks (1)
- Struts2 (2)
- algorithm (9)
- funny (1)
- BMP (1)
- Paper Reading (2)
- MapReduce (23)
- Weka (3)
- web design (1)
- Data visualisation&R (1)
- Mahout (7)
- Social Recommendation (1)
- statistical methods (1)
- Git&GitHub (1)
- Python (1)
- Linux (1)
最新评论
-
brandNewUser:
楼主你好,问个问题,为什么我写的如下的:JobConf pha ...
Hadoop ChainMap -
Molisa:
Molisa 写道mapred.min.split.size指 ...
Hadoop MapReduce Job性能调优——修改Map和Reduce个数 -
Molisa:
mapred.min.split.size指的是block数, ...
Hadoop MapReduce Job性能调优——修改Map和Reduce个数 -
heyongcs:
请问导入之后,那些错误怎么解决?
Eclipse导入Mahout -
a420144030:
看了你的文章深受启发,想请教你几个问题我的数据都放到hbase ...
Mahout clustering Canopy+K-means 源码分析
广度优先搜索(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<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]
完整代码见附件
- chp1.rar (2.2 KB)
- 下载次数: 25
发表评论
-
Java 常用正则表达式以及示例
2012-06-19 16:55 865众所周知,在程序开 ... -
Java实现排列组合
2012-06-15 21:47 17471、全排列 package cn.edu.xmu.dm ... -
Java: Sort a HashMap by its Value
2012-05-29 18:16 801When you use a TreeMap, the ... -
Java 动态代理机制分析及扩展
2012-05-19 23:26 0http://www.ibm.com/developerwor ... -
Java 编程的动态性—— 类、类装入以及反射机制
2012-05-19 23:23 0http://www.ibm.com/developerwor ... -
Java泛型
2012-05-19 23:16 01、Java泛型介绍 ... -
详解Java内存机制(堆与栈)的分配
2012-05-16 10:24 744Java 把内存划分成两种:一种是栈内存,另一种是堆 ... -
[转]Java操作(DOM、SAX、JDOM、DOM4J)xml方式的四种比较与详解
2012-04-09 17:34 933DOM(JAXP Crimson解析器) ... -
贪心算法解背包问题
2012-03-27 21:27 6063背包问题:与0-1背包问题类似,所不同的是在选择物品i装 ... -
Java多线程入门
2012-03-02 00:36 1423搞起一个有意思的.. 了解下多线程可以干嘛 第一个多 ... -
sun.misc.BASE64Encoder找不到jar包的解决办法
2012-02-29 18:42 985转自:http://archive.cnblogs.com/a ... -
Java Comparator 对象比较器
2012-02-17 17:39 849package cn.edu.xmu.ru.utils; ... -
Java反编译小工具!
2011-11-08 20:49 734你是否下载到一个jar,发现他的输入和输出不和你心愿,你没法调 ... -
myeclipse 解决内存溢出
2011-11-06 16:14 8591、修改eclipse.ini 在Myeclipse安装目录下 ... -
Java判断字符串是否全由数字组成
2011-10-26 19:19 3173public class RegxUtils { /** ... -
使用StringTokenizer统计文本行单词个数
2011-10-24 16:36 1025StringTokenizer strToke = new S ... -
Java时间戳计算代码执行时间
2011-10-24 09:56 2872import java.util.Calendar; p ... -
Java 常见异常Top 10
2011-10-23 21:25 732NO. 10 java.lang.StackOverf ... -
小技巧:代码中添加以下注解以方便代码的审查
2011-10-23 21:04 1052//TODO 作者名称 (待写入) //XXX 作者名称 ( ... -
遍历HashMap的两种方式比较
2011-10-22 09:41 1019HashMap存储的是键值对,所以一般情况下其遍历 ...
相关推荐
以动画的方式采用bfs算法实现八数码问题的解决,html文件可直接运行
在图1,3*3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空。 如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态(图1左)到目标状态(图1右)。...
使用深度优先和广度优先搜索算法以及迭代加深的深度优先算法求解15拼图问题
通过双向的BFS算法,使得公交安排这样一个问题在最大程度上减少了时间复杂度。而且对于换乘次数的限制一直是一个瓶颈,会严重增加时间复杂度,但本程序通过matlab巧妙的设计,使得换乘10次以内都可以理想时间内解答...
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
降群法解魔方 哈哈师大 使用双向BFS搜素
2分图匹配的BFS实现,C/C++源码。适用于稀疏二分图,边较少,增广路较短。
详细地介绍BFS的思路模式以及用几个案例教授怎么运用BFS去解题。
simulink BFSK仿真
题解:Bfs找最短路径(正解,绝对正确)这是c++中一道题的题解
动态内存+BFS #include #include #include #include using namespace std; void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; ...
压缩文件里的“bfs-node.h”是头文件,需要在Visual Studio中附加在头文件。这里采取了有向图的邻接链表表现形式,起作用的bfs函数的代码格式参考了《算法导论》这本书上的伪代码。
bfstree代码
现有的分布式文件系统(如HDFS等)无法满足低延迟、高可用、跨地域扩展等方面的需求,所以我们从百度搜索的业务特点出发,开发了自己的分布式文件系统BFS。 设计目标 高可靠、高可用通过将数据副本进行多机房、多...
C++ BFS迷宫.cpp
经典的八码难题BFS广度优先算法的源代码。
算法之BFS与DFS
BFS算法的课程作业,宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想