javascript - 存储地址列表中可能的旅行路径

Question

我有一个可以从 A-Z 称呼的地址列表。我使用 Google Maps api 对这些进行地理编码，然后找到它们之间的行程时间以获得 26x26 矩阵。我想提出一个函数，它接受地址列表、矩阵、目标节点(我将其称为 @)和时间限制，并返回从 A 到 @ 到任何可以实现的所有可能行进路径的列表。多个不同的、不重复的目的地，并在到达时间限制之前返回 A。

我认为递归函数可能是实现此目的的最佳方法，但我只在理论上了解了它们，不知道它是否有效。

到目前为止我的想法是这样的:

var duration = 0;
var path = [];

function getPath(addList, matrix, targetNode, currentNode, timeLimit){
    if(duration+matrix[matrix.indexOf(currentNode), matrix.indexOf(A)]>=timeLimit{
        path[path.length-1] = A;
        // (1) add path to the list of possible paths
    }
    else{
        var tempList = addList;
        tempList.splice(tempList.indexOf(currentNode), 1);
        for(int i = 0; i < tempList.length; i++){
            // (2) increase duration by matrix[matrix.indexOf(currentNode), matrix.indexOf(tempList[i])];
            getPath(tempList, matrix, targetNode, tempList[i], timeLimit);
        }
    }
}

我认为如果我能弄清楚:

(1) 当我进入递归时，我应该如何存储路径 (A,@,...,A)？我不能使用单个变量，因为每个函数都会改变它。我正在考虑使用诸如 xml 文件之类的东西作为树，但这似乎有点过分了。

(2)在类似的问题中，我将如何继续增加每个可能路径的持续时间？

最后一点，这只会给我从 A 到 @ 到其他节点并返回到 A 的最长路径。我也想包括较短的路径作为选项。例如，如果我的路径是 {A, @, B, C, D, A} 那么我还想包含以下路径 {A, @, A}, {A, @, B, A} 和 {A 、@、B、C、A}。如果我停在那里，递归性会提前停止，所以我认为一旦 getPath 函数完全解决，就应该将其作为后续处理。

任何指示、想法、帮助或评论将不胜感激!提前致谢!

更新:我只是想使用 JSON 对象来处理我的问题。它可能看起来像:

var jsonPaths = [
    {
        index: 1,
        path: [A,@,A],
        duration: 187
    },
    { .... },
    { .... }
];

我可以推送它并在每次函数调用时引用它。

Answer 1

您可以通过创建一个数组，其中包含到目标的所有路径，其距离小于最大允许距离减去到目标的最短路径的距离。

我会分两步完成此操作:

首先，遍历并计算从每个节点到目标的最短路径。将每条最短路径及其距离保存在节点上。

计算完所有最短路径后，您就可以开始创建可能的部分路径数组和可能的路径数组。要成为可能的部分路径，路径的总距离加上路径中最后一个节点到目标的最短路径的距离小于最大路径长度。可能的路径是从 a 到 @ 且小于最大路径长度的路径。

您可以迭代可能的部分路径数组，在每一步中删除第一个可能的部分路径，并且对于从当前节点可以到达的所有节点，检查将该节点添加到当前路径是否是可能的部分路径小路。如果是这样，请将其添加到您可能的部分路径数组中。 “您可以前往的节点”意味着您尚未访问过但已连接到当前节点的节点。

现在，看起来您已将所有节点连接到所有其他节点。这可能会产生问题，因为它为您提供了从 a 到 @ 的最多 4.0329146e+26(也称为 26!)可能的路径。一般来说，对于这些类型的问题，您将节点限制为只能连接到附近的节点，以避免出现大量的扩展问题，但您仍然可能会生成大量路径。所有可能的路径都可能是一个很大的数字。

我建议不要递归，因为你正在生成一个包含很多内容的列表。只需创建一系列可能性，然后不断从中删除内容/向其中添加内容，直到它为空为止。

编辑:由于所有节点都连接到所有其他节点，因此从任何可能的潜在路径，您可以通过添加目标节点来创建路径。就寻找路径而言，这简化了事情。

要找到可能的路径，请考虑任何可能的路径是另一条可能的路径加上一个节点。如果您知道 ABC 是一条可能的路径，则可以检查 ABCD、ABCE、ABCF 等，以及将 ABC@ 添加到半路径数组中。

同样，如果 ABD 不是一条可能的路径，则您无需考虑从该路径开始的任何其他内容。要得出从 A 到 @ 的所有路径，您可以从数组 [A] 开始。

你的函数看起来像这样:

var partialPaths = [A],
    nodes = [/*this contains all of your nodes*/],
    paths = [],
    maxDistance = totalDistance - distance([A@]), 
      //max distance of any path between A and @
    currentPath;

while(partialPaths.length > 0){
    currentPath = partialPaths.pop();

    paths.push(currentPath.concat([@]); //Adds the current path plus @

    nodes.forEach(function(node){
        if(distance(currentPath + node + @) < maxDistance &&
          (node not in current path){
            partialPaths.push(currentPath + node);
        }
    });
}

在此之后，您将拥有从 A 到 @ 的所有路径的数组。只需将每条路径与长度小于总长度减去最大长度的所有路径组合即可获得所有往返路径。