我为 Garmin 手表创建了一个离线导航应用程序,它包含一个路由算法,以便通过代表存储在应用程序中的欧洲路线图的坐标数据进行离线路由。路由算法非常慢,生成从伦敦到格拉斯哥的路由可能需要 25 分钟,我有兴趣将其修改得更快或将更快的算法转换为 ConnectIQ,我这样做的能力因 ConnectIQ 缺乏一些功能而受到阻碍其他语言的功能,反之亦然,以及文档非常行话或没有解释每个步骤。我已在我的代码中添加了注释和上下文数据示例:
缩短的数据示例,目的地和起点始终是数据中的数字之一:
[[-0.369,53.795,-0.477,53.843,-0.656,53.859,-0.789,53.919,-1.012,53.957],[-0.993,51.448,-0.979,51.451],[-0.985,50.848, -0.988, 50.786]]
if (MapArr != null) {
if (RoutePick != Map.size()){
//go through all inner arrays of current MapArr to find the closest point to start
var array = MapArr[add];
for (var j = 0; j < array.size(); j+=2) {
var CurrentX = array[j];
var CurrentY = array[j+1];
var package = [startLat,startLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
//check if route contains point already
if (distance < minDistanceToStart && CurrentX != startLon && CurrentY != startLat && hasit == -1 && hasit2 == -1) {
currentArr = array;
minDistanceToStart = distance;
c2SIndex = j;
}
}
if (add == (MapArr.size() - 1)){
if (RoutePick != (Map.size() - 1)){
add = 0;
RoutePick = RoutePick + 1;
//go through the current array to find the closest point to destination
WatchUi.requestUpdate();}
else if (RoutePick == (Map.size() - 1)){
for (var k=0; k<currentArr.size(); k+=2) {
var CurrentX = currentArr[k];
var CurrentY = currentArr[k+1];
var package = [destLat,destLon,CurrentX,CurrentY];
var distance = distance(package);
hasit = route.indexOf(CurrentX);
hasit2 = route.indexOf(CurrentY);
//check if route contains point already
if (distance < minDistanceToDest && hasit == -1) {
closestToDestX = CurrentX;
closestToDestY = CurrentY;
minDistanceToDest = distance;
c2DIndex = k;
}
}
//reverse array if start index is greater than destination index and Add the points to the route array.
router = [];
if (c2SIndex > c2DIndex) {
for (var l = c2SIndex; l > c2DIndex; l-=2){
router.addAll([currentArr[l],currentArr[l+1]]);
}
}
// Add the points to the route array.
else if (c2SIndex < c2DIndex){
for (var l = c2SIndex; l < c2DIndex; l+=2) {
router.addAll([currentArr[l],currentArr[l+1]]);
}
//System.println(c2DIndex + "," + c2SIndex + "Don't reverse");
}
//if points are equal then add the points to the route array this way.
else if (c2SIndex == c2DIndex){
router.addAll([currentArr[c2SIndex],currentArr[c2SIndex + 1]]);
}
hasit = route.indexOf(router);
if (router.size() > 0 && hasit == -1){
route.addAll(router);}
router = null;
//if destination found then finish
if (closestToDestX == destLon && closestToDestY == destLat || route[0] == destLat && route[1] == destLon){
RoutePick = Map.size();
System.println("route finished");
route.add(destLon);
route.add(destLat);
generateRoute = null;
NumPick = 0;
var m = Position.getInfo().position;
m = m.toDegrees();
startLat = m[0];
startLon = m[1];
//begin process to draw map and route
MapviewerView.GenerateBitmap();
}
else {
reset iterations to keep searching, i believe this is where my troubles with the speed are.
add = 0;
RoutePick = 0;
startLat = closestToDestY;
startLon = closestToDestX;
minDistanceToDest = 2147483647;
minDistanceToStart = 2147483647;
WatchUi.requestUpdate();
}
}
}
else if (add < (MapArr.size() - 1)) {
add = add + 1;
WatchUi.requestUpdate();
}
}
}
}
计算解决方案的速度将反映可用的计算能力(这在 Garmin 手表上并不多)以及用于计算路线的算法/代码的效率。如果不运行您的代码,您的方法看起来本质上是 O(n^2),当点数 n 很小时,它可能运行良好,但当 n 变大时,效率非常低。
我突然想到要实现一个简单的贪婪算法,考虑到 Connect IQ 平台的限制,这可能是最好的折衷方案。 Medium 上的这篇文章应该为您提供一个很好的概述,并且还包括所有引用(以便更多阅读)。
最终,您可能会发现,即使您最初要求离线解决方案,最好的解决方案也是使用对在线资源的 API 调用。在当今“互联网几乎无处不在”的生活中,可以选择在云中计算路由(以获得最佳解决方案)并仅在必要时在设备上进行计算,并接受该解决方案要么很快(但不是最好的解决方案)或缓慢(有更好的解决方案)。
另一种选择是从贪婪离线遍历开始,以最大限度地减少任何延迟和/或处理缺乏互联网的情况,但最终使用云作为最终解决方案。