计算通过三个数组的最短路径

Question

我有三个数组，或者可能是n个。现在我们先考虑三个数组。

它们的值如下：

Array1=[143, 181];
Array2=[41, 153, 241];
Array3=[22, 67, 131, 190];

我想找到这三个数组中差距最小的元素，就像在这个例子中，143、153和131的差距最小。

- Renu Thakur

---

这三个数组都是元素的位置，因此我想要计算它们之间的最短路径，需要进行差分运算。 - Renu Thakur

你到目前为止尝试了什么？请注意，StackOverflow 在这里是来帮助你编写代码，而不是为你编写代码的。 - Burki

针对这个问题还是之前的问题？ - Renu Thakur

@Burki 这不是一个简单的问题。即使不修剪分支，使用N个数组计算最短路径也有一定难度，不是所有开发人员都知道如何编写这个功能。 - Denys Séguret

@DenysSéguret 我完全同意。但这并不意味着 OP 不展示自己的努力就应该被接受。 - Burki

Answer 1

假设您没有大量的数组，这里提供一种解决方案，即计算（和存储）所有路径：

// First let's use a sensible structure
var arrays = [Array1, Array2, Array3];

// Then, let's compute all possible paths
var paths = arrays[0].map(function(v){ return [v] });
for (var i = 1; i<arrays.length; i++) {
   var arr = arrays[i];
   for (var j=paths.length; j--; ) {
      var newPaths = arr.map(function(v){
        return paths[j].concat(v);
      })
      newPaths.unshift(j,1);
      [].splice.apply(paths, newPaths);
   }
}

// Now, let's just take the shortest one
var shortestDistance = Infinity,
    shortestPath = null;
paths.forEach(function(path){
  var distance = 0;
  for (var i=1; i<path.length; i++) {
    distance += Math.abs(path[i]-path[i-1]);
  }
  if (distance<shortestDistance) {
    shortestDistance = distance;
    shortestPath = path;
  }
});

// Finally, let's log the result
console.log(shortestDistance, shortestPath);

它记录日志

32
[143, 153, 131]

- Denys Séguret

---

谢谢。太棒了。正常工作。现在我会尝试解决我的之前的问题。 - Renu Thakur

Answer 2

也许我理解了您的需求。

您需要探索一棵树，其中每个数组都是每个节点的所有后代列表，就像这样：

          * (root)
       /      \
   143          181
  / | \        / | \
41 153 241   41 153 241
/|\/|\ /|\   /|\/|\ /|\
........ descendants from 3rd array

你可以通过祖先节点路径到达叶子节点来计算叶子权重的差异。

然后，您希望找到所有叶子节点的最小权重。

如果您以递归方式实现它并保留变量minSoFar和节点的副本以保持树中任何叶子上找到的最小值，则这不太困难。

一旦这个抽象数据结构在概念上清楚了，那么实现就很直接和简单了。

编辑：此实现具有较小的内存占用（仅调用堆栈）并且应该具有与非递归版本相同数量级的性能。 在此页面上显示的递归和非递归实现中，由抽象数据结构决定复杂性。 由于内存占用较小，因此应该可以计算相当深的结构（许多数组），尽管计算时间呈指数增长。

function recursiveMinDiff(arrays)
{
  var minSoFar, minNodes;

  function computeMinDiff(values)
  {
    var i, vs, total;

    vs = values.slice();
    vs.sort(function (a,b) {      // ascending order
      return a - b;
    });

    total = 0;
    for (i = 0; i < vs.length - 1; i++)
    {
      total += vs[i + 1] - vs[i]; // always non-negative
    }

    return total;
  }

  function mindiff(arrays, stack)
  {
    var i, diff, level;

    level = stack.length;
    if (level === arrays.length)  // this is a leaf
    {
      diff = computeMinDiff(stack);
      if (diff < minSoFar)
      {
        minSoFar = diff;          // side-effect on min*
        minNodes = stack.slice(); // clone array
      }
      return;
    }

    for (i = 0; i < arrays[level].length; i++)
    {
      stack.push(arrays[level][i]);
      mindiff(arrays, stack);
      stack.pop();
    }
  }

  minSoFar = Number.MAX_VALUE;
  minNodes = [];
  mindiff(arrays, []);

  return minNodes;
}

- pid

---

是的，那就是我想要的。但我从@denys的解决方案中得到了最短路径，现在我使用数学函数获取最小值和最大值。 - Renu Thakur

没关系，这对我来说更像是一次练习 :) 我先用PHP写了，然后意识到你需要JS。我会把这个留在这里，让那些想要理解两种实现方式的人看看。 - pid