- 浏览: 465419 次
- 性别:
- 来自: 广州
-
文章分类
- 全部博客 (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 796http://www.vckbase.com/document ... -
线性运动
2012-02-07 14:03 838线性运动:y=ax+z ==> P=(x0+ax ... -
SQ题
2011-11-17 11:16 6711.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
钦天监
2011-10-28 15:42 711http://www.360doc.com/content/0 ... -
排序....
2011-08-25 14:17 734http://zh.wikipedia.org/wiki/%E ... -
给far的单链表代码
2011-03-30 22:31 489纯纪念 #include <stdio.h> # ... -
贪心取最大和
2011-03-28 12:03 795贪婪算法: 1、不追求最优解,故不穷举所有可能性,故效率高; ... -
数组环、链表环、约瑟夫环
2011-03-28 09:40 900双向循环链表 struct node { int id ... -
单链表倒数N个的地址
2011-03-08 08:52 851又给人问倒了~ 单链表的长度L,那么倒数N个的位置:L - ... -
折半查找
2011-03-08 08:51 807最近被人问题,事隔三年了,貌似没什么进步,又写了一遍。 ... -
Hash哈希表
2010-12-16 22:36 703比较方法: 一、直接原数据的比较 二、数据通过某种映射后比较 ... -
Hannoi
2010-11-03 11:38 716每次看问题的层次,偶尔有不同的想法,看来层次提高了 # ... -
KMP字符串匹配
2010-09-26 15:49 599http://lemonmilk.blog.51cto.com ...
相关推荐
python学习资源
jfinal-undertow 用于开发、部署由 jfinal 开发的 web 项目
基于Andorid的音乐播放器项目设计(国外开源)实现源码,主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。
python学习资源
python学习资源
python学习一些项目和资源
【毕业设计】java-springboot+vue家具销售平台实现源码(完整前后端+mysql+说明文档+LunW).zip
HTML+CSS+JavaScarip开发的前端网页源代码
python学习资源
【毕业设计】java-springboot-vue健身房信息管理系统源码(完整前后端+mysql+说明文档+LunW).zip
成绩管理系统C/Go。大学生期末小作业,指针实现,C语言版本(ANSI C)和Go语言版本
1_基于大数据的智能菜品个性化推荐与点餐系统的设计与实现.docx
【毕业设计】java-springboot-vue交流互动平台实现源码(完整前后端+mysql+说明文档+LunW).zip
内容概要:本文主要探讨了在高并发情况下如何设计并优化火车票秒杀系统,确保系统的高性能与稳定性。通过对比分析三种库存管理模式(下单减库存、支付减库存、预扣库存),强调了预扣库存结合本地缓存及远程Redis统一库存的优势,同时介绍了如何利用Nginx的加权轮询策略、MQ消息队列异步处理等方式降低系统压力,保障交易完整性和数据一致性,防止超卖现象。 适用人群:具有一定互联网应用开发经验的研发人员和技术管理人员。 使用场景及目标:适用于电商、票务等行业需要处理大量瞬时并发请求的业务场景。其目标在于通过合理的架构规划,实现在高峰期保持平台的稳定运行,保证用户体验的同时最大化销售额。 其他说明:文中提及的技术细节如Epoll I/O多路复用模型以及分布式系统中的容错措施等内容,对于深入理解大规模并发系统的构建有着重要指导意义。
基于 OpenCV 和 PyTorch 的深度车牌识别
【毕业设计-java】springboot-vue教学资料管理系统实现源码(完整前后端+mysql+说明文档+LunW).zip
此数据集包含有关出租车行程的详细信息,包括乘客人数、行程距离、付款类型、车费金额和行程时长。它可用于各种数据分析和机器学习应用程序,例如票价预测和乘车模式分析。
把代码放到Word中,通过开发工具——Visual Basic——插入模块,粘贴在里在,把在硅基流动中申请的API放到VBA代码中。在Word中,选择一个问题,运行这个DeepSeekV3的宏就可以实现在线问答
【毕业设计】java-springboot+vue机动车号牌管理系统实现源码(完整前后端+mysql+说明文档+LunW).zip
【毕业设计】java-springboot-vue交通管理在线服务系统的开发源码(完整前后端+mysql+说明文档+LunW).zip