- 浏览: 439891 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (538)
- C/C++ Primer (69)
- Objective-C Primer (102)
- Python Primer (19)
- JavaScript Primer (1)
- Java Primer (37)
- PHP Primer (17)
- 泛 Linux (37)
- Shell Script (21)
- APUE (21)
- UNP__1&2 (19)
- NetWork (7)
- Oracle周边 (38)
- Mysql里边 (6)
- Windows技 (9)
- 简单算法 & 数据结构 (14)
- 设计模式 (6)
- GTK历程 (12)
- 工具使用 (25)
- 杂事 (23)
- 一些概念 (17)
- Web方面 (10)
- myCodeTools (9)
- ^未 竟$ (13)
- 硬件通信 (2)
- Games (1)
最新评论
class PathInfo //数据存储结构 { String from; String to; int distance; boolean skip; // used in backtracking PathInfo(String f, String t, int d) { from = f; to = t; distance = d; skip = false; } }
public class Depth { final int MAX = 100; PathInfo paths[] = new PathInfo[MAX]; int pathCount = 0; Stack<PathInfo> goInfo = new Stack<PathInfo>(); public static void main(String args[]) { String from = "", to = ""; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { System.out.print("From? "); from = br.readLine(); System.out.print("To? "); to = br.readLine(); } catch (IOException exc) { System.out.println("Error on input."); } Depth depth = new Depth(); depth.setup(); depth.isOK(from, to); depth.route(); } void isOK(String from, String to)// 将可行的路径压栈 { int dist = match(from, to); if (dist != 0) // 一站到达 { goInfo.push(new PathInfo(from, to, dist)); return; } PathInfo pinfo = findFrom(from); if (pinfo != null) { goInfo.push(new PathInfo(from, to, pinfo.distance)); isOK(pinfo.to, to); // 直到有“一站到达” } else if (goInfo.size() > 0) { pinfo = (PathInfo) goInfo.pop();// 死路一条 isOK(pinfo.from, pinfo.to);// 回头再走,成立即可 } } void route() { if (goInfo.size() == 0) return; int num = goInfo.size(); Stack<PathInfo> backInfo = new Stack(); for (int i = 0; i < num; i++) backInfo.push(goInfo.pop());// 倒出来,再pop,就是正序了 int dist = 0; PathInfo pinfo = null; for (int i = 0; i < num; i++) { pinfo = (PathInfo) backInfo.pop(); System.out.print(pinfo.from + " to "); dist += pinfo.distance; } System.out.println(pinfo.to); System.out.println("Distance is " + dist); } // 看能不能直到,能的话,就返回权重,不能返回0 int match(String from, String to) { for (int i = pathCount - 1; i > -1; i--) { if (paths[i].from.equals(from) && paths[i].to.equals(to) && !paths[i].skip) { paths[i].skip = true; // prevent reuse return paths[i].distance; } } return 0; } // Put flights into the database. void addFlight(String from, String to, int dist) { if (pathCount < MAX) { paths[pathCount] = new PathInfo(from, to, dist); pathCount++; } else System.out.println("Flight database full.\n"); } // Given from, find any connection. // 找到一个起点为from的,并再new一份出来,这段路的条件是未走过。 PathInfo findFrom(String from) { for (int i = 0; i < pathCount; i++) { if (paths[i].from.equals(from) && !paths[i].skip) { PathInfo pinfo = new PathInfo(paths[i].from, paths[i].to, paths[i].distance); paths[i].skip = true; // prevent reuse return pinfo; } } return null; } // Initialize the path database. // 地图是有限的,每个点周边相邻的点,两两成一直线,且是有方向性的 // 查找的时候,数据的分布,会影响结果 public void setup() { databaseGen(); } private void databaseGen() { addFlight("A", "B", 500); addFlight("A", "D", 900); addFlight("A", "C", 1800); addFlight("A", "J", 700); addFlight("J", "K", 300); addFlight("B", "A", 1700); addFlight("B", "F", 1700); // addFlight("B", "H", 600); addFlight("B", "D", 500); addFlight("C", "G", 1000); addFlight("C", "E", 1000); addFlight("C", "H", 1000); addFlight("D", "C", 1000); addFlight("E", "H", 1500); } private void databaseGood() // 最理想的情况,A to B { addFlight("A", "B", 500); } private void databaseLong()// 不理想的数据分布, A to J { addFlight("A", "B", 1500); addFlight("A", "I", 1500); addFlight("I", "J", 1500); addFlight("B", "C", 1500); addFlight("B", "A", 1500); addFlight("C", "D", 1500); addFlight("C", "B", 1500); addFlight("D", "C", 1500); } private void databaseLong2()// 不理想的数据分布, A to J { addFlight("A", "B", 1500); addFlight("A", "I", 1500); addFlight("I", "J", 1500); addFlight("B", "A", 1500);// -- addFlight("B", "C", 1500);// -- addFlight("C", "B", 1500);// -- addFlight("C", "D", 1500);// -- addFlight("D", "C", 1500); } }
数据存储特征:
一、上面的地图数据结构,映射为二维表。
二、起点集合性(就是from集在一起)
三、from按A->Z,to 是A->Z 或 Z->A
数据查找特征:
一、深度优先,如果是二维表的角度来说是,从左到右,从上至下。
查找优化:
一、将from分成块,那就能加快from的查找;
二、较短路径:
1、先得到起点与终点的直线距离X值,再由X经某种公式得到K值。
2、查找时判断时,排除权值大于K的
飞机就是典型、理想的点对点模型,
汽车的GPS导航就更复杂了,有路径最短、最省钱、最快速的
发表评论
-
A星寻路+堆排序
2012-03-27 22:24 679http://www.vckbase.com/document ... -
线性运动
2012-02-07 14:03 737线性运动:y=ax+z ==> P=(x0+ax ... -
SQ题
2011-11-17 11:16 6271.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
钦天监
2011-10-28 15:42 675http://www.360doc.com/content/0 ... -
排序....
2011-08-25 14:17 665http://zh.wikipedia.org/wiki/%E ... -
给far的单链表代码
2011-03-30 22:31 445纯纪念 #include <stdio.h> # ... -
贪心取最大和
2011-03-28 12:03 738贪婪算法: 1、不追求最优解,故不穷举所有可能性,故效率高; ... -
数组环、链表环、约瑟夫环
2011-03-28 09:40 844双向循环链表 struct node { int id ... -
单链表倒数N个的地址
2011-03-08 08:52 795又给人问倒了~ 单链表的长度L,那么倒数N个的位置:L - ... -
折半查找
2011-03-08 08:51 766最近被人问题,事隔三年了,貌似没什么进步,又写了一遍。 ... -
Hash哈希表
2010-12-16 22:36 664比较方法: 一、直接原数据的比较 二、数据通过某种映射后比较 ... -
Hannoi
2010-11-03 11:38 665每次看问题的层次,偶尔有不同的想法,看来层次提高了 # ... -
KMP字符串匹配
2010-09-26 15:49 535http://lemonmilk.blog.51cto.com ...
相关推荐
深度优先寻路算法是路径规划算法中的经典路径规划算法。
在类似于迷宫的地图上,采用深度优先搜索的策略(递归回朔)计算从起始点到目标点之间的一条最短路径。
迷宫路径的深度优先搜索算法的C语言简单实现,迷宫用二位数组存储
该代码解决了最短路径问题(给定带权有向图G=(V, E),对任意顶点vi,vj∈V(i≠j),求顶点vi到顶点vj的最短路径...代码使用了广度优先搜索和深度优先搜索;枚举法、回溯法来解决最短路径问题,其中结果存储使用文件。
BFS DFS 深度优先搜索 广度优先搜索 图 输出所有路径 输出最短路径 随便输出一条可能的路径
直接演示:求深度优先遍历、广度优先遍历、最短路径、最小生成树
要求建立图的存储结构(邻接表或邻接矩阵),输入任意的一个图,显示图的深度优先搜索遍历路径。
大学课程、数据结构、图的存储结构、深度优先搜索遍历路径、代码
人工智能的八数码的深度优先算法c++实现
资源分为两块,有注释代码,一定会收获很多,信就来下载,菜鸟不要抱怨代码
js--最短路径问题游戏 用深度优先算法,优先与广度优先的区别,js的实现,可以了解
利用深度优先算法求解网络中两点之间的所有路径数目
经典栈队列以及深度优先算法的代码例子,便于学习和参考。
深度优先搜索(DFS)是一种常用的图遍历算法,用于寻找图中的路径。它从起始节点开始,沿着一条路径尽可能深入地探索,直到无法继续为止,然后回溯到上一个节点,继续探索其他路径。DFS的核心原理是通过递归或栈的...
①使用深度优先搜索来解决八数码问题 ②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识, 连同如何使用这些知识的方法,均...
flash as3.0 求解迷宫最短路径 深度优先策略 flash as3.0 求解迷宫最短路径 深度优先策略 flash as3.0 求解迷宫最短路径 深度优先策略 flash as3.0 求解迷宫最短路径 深度优先策略 flash as3.0 求解迷宫最短路径 ...
这是一个基于实时路况的出行路径规划实现,里面包含了预测原数据,预测算法实现和路径规划实现,路径规划算法使用了深度优先算法改进。
全部功能采用Matlab编写,程序的功能是寻找从出发点到目的地的全部可行路径,最后只显示了最佳和最劣路径的动画效果,对每一步的移动进行了动画演示。
数据结构 广度 深度 拓扑 最短路径 最小生成树 c语言的算法实现
多路径匹配追踪深度优先(MMP-DF),包含深度优先程序代码,方便理解该算法的原子搜索方式