夜光精讲 Opentcs 三大算法（七）路径算法

夜光序言：

 

 

 

生活多么无趣，但一则则无趣的生活编织在一起，才构成了生命的繁华。

 

 

 

 

 

 

 

 

 

正文：

 

４．哈希表实现
（１）哈希表底层结构体的实现

（２）哈希表节点类型

 

（３）哈希表操作方法实现

（４）时间复杂度和空间复杂度

空间消耗由维护局部更新数据和哈希表产生。假设地图有ｎ个点，那么最多有ｎ＊ｎ个需要插入的元索，ｔａｂleＳｉｚｅ大小设为ｎ。

ＩＮＳＥＲＴ操作的最坏情况时间为０（１）。

ＤＥＬＥＴＥ操作的最坏情况时间为０（ｎ）。

查找不成功的ＳＥＡＲＣＨ操作的平均运行时间为０（ｎ），最坏情况时间为０（ｎ）。
 

查找成功的ＳＥＡＲＣＨ操作的平均运行时间为０（（ｎ＋Ｕ／２），最坏情况时间为０（ｎ）。

---

哈希表存储有较明显的优势：

ａ．访问速度快，存储大小可拓展。
ｂ．省去每次新路径读入时，都要重新计算窗口中相同起点终点出现次数的比较，提高算法的效率。保证输出结果有较小的延时。
Ｃ．记录维护各自的ｈａｓｈ表。（分区域仓库中毎个ｍａｐ／ａｒｅａ都有自己的哈希表；整个仓库有拓扑哈希表。这样利于维护，只需要更新局部数据）
 

---

评估函数和性能指标的确定

该系统的路径解决方案设定一下以下评估指标：

１．距离Ｄｉｓｔａｎｃｅ：小车行驶的路径长度；
２．转弯数目Ｔｕr nｓ：尽量避免小车的转弯，从而提高运行速度和效率；
３．运行时间ＴｒａｖｅｌＴｉｍｅ：区分＂距离＂指标，对于相同长度的两条边，可能预设的限速值不同，从而经过两条边的用时也不同；
４．跳数Ｈｏｐｓ：一条路径上经历的点或区域地图块的数目越多，就需要ＡＧＶ进行更多的坐标扫描定位和位置信息上报通信，甚至需要ＡＧＶ乘坐电梯进行跨区域任务，因此应尽量减少跳数，提高运作效率。
 

【沉下心来，好好研究】

---

函数实现和调用流程

给定要寻找的路的起始点和终止点（Ｐｏｉｎｔ Ａ－＞ＰｏｉｎｔＢ）

１）首先要调用ｉｓＲｏu tａｂｌｅ（）判断此两点之间是否可达（可通行）
２）调用ｇｅｔＣｏｓｔ（）函数计算给定路径的花费，
３）毎走一步，需要判定未经过的点是否可以通行（不能通行要上报，重新指派）

需要注意，当起始点和目标点是同一点时，返回的路径不为空（ＮＵＬＬ），将此点放入路径链路表中，因此ＡＧＶ相当于在此点停留一次。

 

---