做网站的为什么那么多骗子,前端开发需要学什么语言,ui基础教程入门,wordpress怎么在底部调用友情链接目录 一、设想功能描述
想法缘起
目标功能
二、问题抽象
三、算法设计和优化
1. 易想的朴素搜索 / dp
搜索想法
动态规划#xff08;dp#xff09;想法
2. 思考与优化
四、算法实现
五、结果示例
附#xff1a;使用的地图API 一、设想功能描述
想法缘起 OSM 导出…目录 一、设想功能描述
想法缘起
目标功能
二、问题抽象
三、算法设计和优化
1. 易想的朴素搜索 / dp
搜索想法
动态规划dp想法
2. 思考与优化
四、算法实现
五、结果示例
附使用的地图API 一、设想功能描述
想法缘起 OSM 导出的地图数据中有 “amenity”便民设施点并在 tag kamenity v.../ 中标记了每个 amenity 的具体类型比如fast_food, pub, toilets…… 而人们在路途或旅途中常常关注最近的某种类型常为 amenity如卫生间、停车车场的最近处而尚未明确目的地。从而容易想到去设计一个扩展功能给定 amenity查询距离当前点最近的该类的点。显然这个问题仍用 Dijkstra 求单源最短路即可。 然而有时人们想连续去多个便民点比如先去停车场停车再去吃饭最后逛逛周边的公园等等。为了提高效率与体验很可能需要一个总路程最短的方案这就是功能二考虑的问题。
目标功能
★ 用户给定当前位置并指定一个 amenity 种类的顺序。求出最短路线并呈现在地图上。 二、问题抽象
地图上有某些点带有颜色。给出起点 s 与颜色序列 尽可能快地求出一条以 s 为起点的最短路线 要求其依次经过颜色为 的点。
存在数据约束与特征其中 为 颜色点集此外各种颜色的点大致均匀分布。 三、算法设计和优化
1. 易想的朴素搜索 / dp
搜索想法
直接以每个 为阶段进行深度优先搜索DFS这部分时间复杂度已经有 虽然可以进行剪枝即当前搜素的长度 cur 超过搜到的最短长度 res就直接 return但光这样时间复杂度不变的。
动态规划dp想法
以每个 为阶段设计 dp易得状态转移方程类似如下形式 然而显然其时间复杂度是同搜索的而且还很难剪枝所以比搜索更差。
此外还要计算中间相邻颜色两点的最短路从而全求出来的时间复杂度应比上面更大空间复杂度亦大。
2. 思考与优化
直观地最终答案的路线几乎不可能 “兜得很远”这启发我们优化搜索顺序。对于每个 我们考虑先走到离最近的 搜索下去回溯后再搜次近的 ……可以想象这样搜出来的前几条路已经得到或较接近最终答案。进一步来看又因为各种颜色的点大致均匀分布所以这样的剪枝效果一定是非常显著的。
不过如何求出搜 的顺序其实我们完全不必先预处理出最短路然后排序。注意到 Dijkstra 的最短路算法就是按照距离由到达的顺序得到 “确定点” 的。所以我们把 Dijkstra 算法 “嵌入” 搜索框架之中从当前 做 Dijkstra遍历到一个下一颜色的 我们就从 递归进行搜索。这样相当于又解决了花大代价计算最短路的问题。 总之本问题基于搜索的大框架而其内部融入 Dijkstra每个结点处的下一个点通过 Dijkstra 确定当前搜索路上的每个点都保留了一个 Dijkstra 状态。
四、算法实现
关键在于构建搜索的代码尤其是解决 “每一层” 都在做 Dijkstra 带来的问题。
原始 Dijkstra 只有一个答案数组 d[MAXN] 这里我们显然需要多个不过我们若开 n 个这样的数组内存开销较大且可能不易扩展。注意到 {d[u], u} 保留在原始 Dijkstra 的 std::priority_queue 中我们可以用 std::set 代替这个 std::priority_queue既可以取出最小值又存下来当前有用的 {d[u], u} 且能 std::find 得到 {d[v], v}而 vis 数组可用 std::unordered_set 代替。
这样我们相当于仅在搜索路上开 C 的容器空间开销显著减小而并未增大过多增加时间常数且易于扩展。
void DFS(int s, int x, double cur) {if (x Ord.size()) { // ... }setpairdouble, int d; d.insert({0.0, s});unordered_setint vis;while (d.size()) {int u d.begin()-second;double dis d.begin()-first;if (cur dis ans) return;
d.erase(d.begin());if (vis.find(u) ! vis.end()) continue;vis.insert(u);auto itt M.p[u].Ames.find(Ord[x]);if (itt ! M.p[u].Ames.end()) {curOrd.push_back(u);DFS(u, x1, curdis);curOrd.pop_back();}
for (int e M.head[u]; e; e M.nxt[e]) {// ...auto it d.upper_bound({-1.0, v});if (itd.end() || it-second!v || diswit-first) d.insert({disw, v});}}
}
五、结果示例 n6起点在徐家汇一带较为随意地指定下面 6 个 Amenity Type 的顺序 附使用的地图API 基于 Leaflet.js 库的 Python 交互式地图包 Folium
