问题描述:
见下图,要求寻找A至Z的所有路径。
已知:两点之间的直接路径。例如:A-->B B-->C B-->E。。。。
解:
定义一个基本路径模型,属性:起始点和结束点。A-->B可抽象成new Road("A",'B');
package alogrim;
public class Road implements Cloneable {
public Road(String begin,String end) {
this.begin = begin;
this.end = end;
}
private String begin;
private String end;
public String toString() {
return begin + "->" + end;
}
public String getBegin() {
return begin;
}
public void setBegin(String begin) {
this.begin = begin;
}
public String getEnd() {
return end;
}
public void setEnd(String end) {
this.end = end;
}
public boolean equals(Object obj) {
Road r = (Road)obj;
if(this.getBegin().equals(r.getBegin()) && this.getEnd().equals(r.getEnd())) {
return true;
}
return false;
}
public Object clone() {
try {
return super.clone();
} catch (CloneNotSupportedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return null;
}
}
核心算法分两步:
1 过滤掉无用的路径。例如上图:G-->B G-->F D-->F都属于无效路径。
第一步:获取无效开始节点和无效结束点
/**
* 过滤掉无用的节点
* 获取到无效开始节点和无效结束点
* @param all 所有节点
* @return
*/
public Set<String> filterInvalidNode(Set<String> all, List<Road> roads,
Set<String> begins, Set<String> ends) {
Set<String> result = new HashSet<String>();
boolean isBegin = true;
boolean isEnd = true;
for (String str : all) {
if (!existEnd(str, roads)) { // 没有以此节点结尾的路径,则证明此节点为无用节点
isBegin = false;
begins.add(str);
// 删除以此节点为开始的路径
// this.deleteBegin(str, roads);
} else if (!existBegin(str, roads)) {// 没有以此节点开头的路径,则证明此节点为无用节点
isEnd = false;
ends.add(str);
// this.deleteEnd(str, roads);
} else {
result.add(str); // 有用的节点
}
}
if (isBegin == true && isEnd == true) {
return result;
} else {
return filterInvalidNode(result, roads, begins, ends);
}
}
第二步:删除无效路径
/**
* 获取到需要删除的路径
*
* @param begins
* ---无效起始节点
* @param ends
* ---无效终结点
* @param roads
*/
public Set<Road> deleteRoad(Set<String> begins, Set<String> ends,
List<Road> roads) {
Set<Road> set = new HashSet<Road>();
for (String str : begins) {
for (Road r : roads) {
if (r.getBegin().equals(str)) {
set.add(r);
}
if (r.getEnd().equals(str)) {
set.add(r);
}
}
}
return set;
}
2 路径遍历,确保找到两点之间的所有可通过路径,需要确保每条基本路径都被访问过。本算法采用自上而下遍历方式。详细含义如下:
List<Road> roadList = null; //已知的路径
List<String> backList = new ArrayList<String>(); //存放已经访问过的节点
Set<String> resultSet = new HashSet<String>(); //目的路径--访问结果
Set<Road> cirList = new HashSet<Road>(); //回路
/**
* 路径遍历的核心算法
* @param start
* ---需要寻找的起始节点。本案例为A
* @param destination
* ---需要寻找的终结点。本案例为Z
*/
public void getAllRoad(String start, String destination) {
backList.add(start);
for (int z = 0; z < roadList.size(); z++) {
if (roadList.get(z).getBegin().equals(start)) { //寻找找以start开始的路径
if (roadList.get(z).getEnd().equals(destination)) { //如果以destination结尾,则为一条有效路径
resultSet.add(backList.toString().substring(0, backList.toString().lastIndexOf("]")) + "," + destination + "]");
continue;
}
if (!backList.contains(roadList.get(z).getEnd())) {//此节点仍未遍历,则继续迭代
getAllRoad(roadList.get(z).getEnd(), destination);
} else {//證明有回路
cirList.add(roadList.get(z));
//System.out.println("wwww");
}
}
}
backList.remove(start);
}
至此已经完成‘两点之间所有路径’的核心算法。详细代码见附件,main方法在MapVisit里
分享到:
相关推荐
一个可以模拟两点寻找最短路径的算法,动态显示出算法。
用java面向对象程序设计语言,设计和实现一电脑鼠走迷宫的软件程序,即一个假想的小车能在图示的迷宫中根据设定的起始点和终点自主寻找路径。本综合实践分成两部分:第一部分为算法设计和实现部分,第二部分为界面...
JAVA平台提供了两个类:String和StringBuffer,它们可以储存和操作字符串,即包含多个字符的字符数据。这个String类提供了数值不可改变的字符串。而这个StringBuffer类提供的字符串进行修改。当你知道字符数据要改变...
另一个问题是package和import问题,如何来寻找类的路径问题。把这两个问题摸索清楚了,就扫除了学习Java和使用JDK的最大障碍。推荐看一下王森的《Java深度历险》,对这两个问题进行了深入的探讨。
这3个加载器分别对应着编译器去寻找类文件的优先级别和不同的路径:BootClassLoader对应jre/classes路径,是编译器最优先寻找class的地方 ExtClassLoader对应jre/lib/ext路径,是编译器次优先寻找class的地方 ...
JAVA平台提供了两个类:String和StringBuffer,它们可以储存和操作字符串,即包含多个字符的字符数据。这个String类提供了数值不可改变的字符串。而这个StringBuffer类提供的字符串进行修改。当你知道字符数据要...
寻找两顶点间的最短路径的算法很多目前公认最好的算法是Dijkstra在1959 年提出的它不仅求出从始点到终点的最短路径而且最后所得到的实际上是始点到各顶点的最短路径对Dijkstra 算法进行补充得出的步骤如下: ...
它是控制所有游戏功能的主程序,包括画面的处理,路径寻找算法的实现,接收玩家的设置等。 所以鉴定一个游戏的好坏,从内部设计的原因上说,是从游戏的后台设计体现出来的。一个游戏的后台设计,直接关系到游戏设计...
在这个程序里,Crowther设计了一张地图,地图 上不规则的分布着陷阱,游戏者必须寻找路径避开陷阱。这个程序在后来被认为是最早 的电脑游戏程序。而如今,游戏产业已经发展成为一个拥有巨大利润的成熟产业。从上 ...
由上面的命令的错误提示可以看出,ant命令默认寻找build.xml文件。若文件名为hello.xml时,读者还需要对命令做少许改变,改为:ant –f hello.xml sayHelloWorld、ant –buildfile hello.xml sayHelloWorld或ant –...
主要用于关键信息的搜索,类似于在空间中的二分搜索,大大提高了搜索效率,在寻找目标元素时,使用了DFS深度优先的方式和回溯进行最近点的寻找。详细介绍链接 MS-Apriori 基于多支持度的Apriori算法。是Apriori...
书中的算法以英语加伪代码的形式给出,只要有一点程序设计经验的人都能读懂,并可以用任何计算机语言(如C/C++和Java等)方便地实现。在书中,作者将算法的讨论集中在一些比较现代的例子上,它们来自分子生物学(如...
四叉树用于地理位置 四叉树是一种树数据结构,具有4个“子级”,通常称为节点,这些节点中的每个节点内还有4个以上的节点,依此类推,直到达到指定的粒度为止。...使用两个点的经度和纬度,我们可以计算出以度为单位
Agent技术的应用 ---- Microsoft Agent是微软公司于1997年9...ReadReturn //当完成了上面两个动作时候用,可回到标准状态 (接上两个中的一个用) Reading //一直认真地读,连续状态 (可用) Note: This animation...
<<page 1>> page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 ... 比尔....这一天 微软公司正式推出了其下一代...
10.2.4 寻找其他优化机会 266 10.2.5 将子查询因子化应用到PL/SQL中 270 10.3 递归子查询 273 10.3.1 一个CONNECT BY的例子 274 10.3.2 使用RSF的例子 275 10.3.3 RSF的限制条件 276 10.3.4 与CONNECT BY的...
“库文件名”以.lib或.obj为后缀的将被视为静态库,可使用绝对路径或相对路径(相对当前源代码所在目录),如依赖多个静态库请分别列出并以逗号分隔;“在库中的对应命令名”请务必准确填写静态库中公开导出的符号...