- 浏览: 40328 次
- 性别:
最新评论
题目:给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短的路径。
import java.util.ArrayList; //主要是采用广度优先的算法。 /** * 广度度优先搜索 宽度优先搜索并不是一种很优秀的算法,只里只是简单介绍一下它。 具体方法是: 1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点(第二层结点),当然每个新结点要记录下其距离; 2、 再次以AB展开得到ABC、ABD、ABE三个新结点(第三层结点),而由AC结点可展开得到ACB、ACD、ACE三个新结点,自然AD可以展开得到ADB、ADC、ADE,AE可以展开得到AEB、AEC、AED等新结点,对于每个结点也须记录下其距离; 3、 再把第三层结点全部展开,得到所有的第四层结点:ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC,每个结点也需记录下其距离; 4、 再把第四层结点全部展开,得到所有的第五层结点:ABCDE、ABCED、…、AEDBC、AEDCB,每个结点也需记录下其距离; 5、 到此,所有可能的结点均已展开,而第五层结点中最小的那个就是题目的解了。 */ public class T6 { //模拟一个棋盘 String num[][] = new String[8][8]; //用来模拟队列的容器 ArrayList<point> duilie = new ArrayList<point>(); public static void main(String[] args) { T6 test = new T6(); } T6() { //对数组初始化,""代表没有访问过 for (int i = 0; i < num.length; i++) { for (int j = 0; j < num[0].length; j++) { num[i][j] = ""; } } //寻找最短路径,假如起点是7,0 寻找到0,7这个点的最短路径 zuiduan(7, 0); System.out.println("最短路径是:"+num[0][7].toString()+"0,7结束"); } public void xunzhao(int x, int y ,String lujing) { if (!(x < 0 || x > 7 || y < 0 || y > 7) && num[x][y].equals("")) { // 设置为访问过。并记录步数 num[x][y]=lujing; point id = new point(); id.setX(x); id.setY(y); // 入队 duilie.add(id); } } public void zuiduan(int i, int j) { // 访问原点,设置为访问过。 point id = new point(); num[i][j] ="开始"; id.setX(i); id.setY(j); // 入队 duilie.add(id); // 循环队列 while (duilie.size() != 0) { //终止循环的条件 if (!num[0][7].equals("")) break; // 出队 point id1 = duilie.get(0); duilie.remove(0); // 循环,一次搜索隔壁点 int x = id1.getX(); int y = id1.getY(); String lujing=num[x][y]+x+","+y+"-> "; // 判断,如果没有出界并且没有访问过 xunzhao(x - 1, y,lujing); xunzhao(x + 1, y,lujing); xunzhao(x, y - 1,lujing); xunzhao(x, y + 1,lujing); } } //用来记录寻找的每一个点 class point { int x; int y; public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } } }
寻找最短路径,假如起点是7,0 寻找到0,7这个点的最短路径
输出结果如下:
最短路径是:
开始7,0-> 6,0-> 5,0-> 4,0-> 3,0-> 2,0-> 1,0-> 0,0-> 0,1-> 0,2-> 0,3-> 0,4-> 0,5-> 0,6-> 0,7结束
发表评论
-
2012-03-16 20:52 最大公约数;最小公倍数
2012-05-18 21:45 1338求最小公倍数方法如下: (1)、两数相乘法。 ... -
裴波那契算法
2012-05-18 21:40 844裴波那契算法,数组算法 #include<st ... -
一些的算法的格式
2012-05-17 12:15 1051做题目做久了之后就会发现,算法是有格式的。 一、深度优 ... -
第三届蓝桥杯预赛真题-C++本科组-10题(Java实现)
2012-05-15 11:11 946今盒子里有n个小球,A、B两人轮流从盒中取球,每个 ... -
第三届蓝桥杯预赛真题-C++高职组-10题(Java实现)
2012-05-15 10:57 12592x3=6个方格中放入ABCDE五个字母,右下角的那个 ... -
第三届蓝桥杯预赛真题-Java高职组-10题
2012-05-14 13:16 1953匪警请拨110,即使手机欠 ... -
第三届蓝桥杯预赛真题-Java本科组-10题
2012-05-14 12:41 1486泊松是法国数学家、物理学家和力学家。他一生致力科学事 ... -
八皇后-位运算版
2012-01-12 18:38 1194八皇后问题,是一 ... -
计算24点-利用二叉树原理
2012-01-10 21:03 1629问题描述80年代全世界流行一种数字游戏,在中国我们把这种游戏称 ... -
吸血鬼数字
2012-01-09 20:32 912题目: 吸血鬼数字是 ... -
字符串的排列(A(m,n)),可重复选
2012-01-09 13:28 1273题目:现有ABCDE 5个球 构成的排列组合 可重复抽取 最多 ... -
蛇形矩阵
2012-01-09 13:38 1022Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上 ... -
字符串的排列(A(m,n))
2012-01-07 18:18 956题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
字符串的组合(C(m,n))
2012-01-07 17:46 1342题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
汉诺塔
2012-01-07 17:32 927关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers ... -
三角螺旋矩阵
2012-01-07 17:27 1088打印如下矩阵,如果 n=7 则输出: 1 18 2 ...
相关推荐
GPS寻找最短路径,本程序其实是一个简化版本,基本实现功能如下: 功能一: 输入:起点和终点(已知交通图) 输出:起点至终点的最短路径 功能二: 能够在已知的地图中加入新的城市,并且对其其他的功能不受影响,即 ...
实现迷宫寻找最短路径寻找最短路径寻找最短路径
寻找最短路径算法,进行多种算法叠加,选择最优算法,最快算法. 通过形成距阵.
一种用于寻找给定的加权图中顶点间最短路径的matlab算法,通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
这是我写的第一个java的完整程序
用A*算法寻找最短路径,文档中有详细的代码和实验结果
最短路径算法. 可执行,编译。 经典的最短路径算法
有障碍的路径图中寻找最短路径的程序-best,可以很好的运行,完整代码
能够根据输入的个点之间的路径找到从各点之间的最短路径消耗
MAPXTREME寻找最短路径的C#实现代码 FINDSHORTPATH
经过指定的中间节点集的最短路径算法的matlab源码,包括三种应用模式: 1、从起点过必经点到达终点; 2、从起点过必经点且不掉头到达终点; 3、有指定朝向点,从起点过必经点且不掉头到达终点。
因此它必须具备自行决定搜寻策略,在迷宫中前进、转弯、记忆迷宫墙壁资料、计算最短路径和搜寻终点等功能。一般来说,一只电脑鼠需具备下列三个基本能力 (1)拥有稳定且快速的行走能力; (2)能正确判断环境能力;...
附送Kruskal最小生成树算法,都是本人的劳动成果,包含输入输出的完整控制台程序,希望大家下完顶一下:)
此系统为C语言版高校导航系统。 采用图的数据结构,最短路径采用迪杰斯特拉算法求解。 可以指拿来做C语言的数据结构课设。 代码注释详细,可便于复用。
蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法,因此一般而言,蚁群算法用来解决最短路径问题,并真的在旅行商问题(TSP,一个寻找最短路径的问题)上取得了比较好的成效。目前,也已渐渐应用到其他...
自己写的一个跳马程序 按照中国象棋的马的行走方式 以最短的路径到达指定地点
NULL 博文链接:https://touch-2011.iteye.com/blog/1076031
AE寻找最短路径,AE寻找最短路径,AE寻找最短路径,
本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考,具体如下: 多叉树的最短路径: 思想: 传入start 和 end 两个 目标值 1 找到从根节点到目标节点的路径 2 从所在路径,寻找最近的...