关于从 2D 阵列创建排名路径列表，我需要了解什么？

Question

假设我有一个设备及其统计数据矩阵。帽子、衬衫、裤子、靴子。每个内部数组的大小都可以不同，但总会有一定数量的内部数组 - 在本例中为 4.

var array = [
  [1,9,2,8,3],        // hat
  [2,8,3,6],          // shirt
  [1,3],              // pants
  [9,3,2,6,8,2,1,5,2] // boots
]

我想找到通过矩阵的最佳路径，然后以确定的下一条路径（因此路径总和）为 next-best 在第一个之后。在这个例子中，[9, 8, 3, 9] 最好，对吗？所以我们可以删除 [0] 中的 9 以达到 8 只给出 1.

我可以对所有可能的路线求和并从那里确定它，但是内部数组的大小可能比显示的大得多。

我花了一些时间思考它，并进行了研究。我唯一能看到的是匈牙利算法，但它现在超出了我的 maths/compsci 知识范围。在这种情况下，这是最适用的知识吗？它似乎迎合了路线的最低可能 'cost' 但我需要相反的路线。

我的想法，至少作为一个想法：

拉出每个内部数组中的最大数字，从中创建新数组。排名 [0].
将每个内部数组中的最高数字与次低数字进行比较。排序每个之间的差异。
从#2 中找到的差异最小的内部数组中删除最大的数字。
重复 #1 到 #3。

在上面的示例中，我期望的结果如下所示。

[9, 8, 3, 9]
[8, 8, 3, 9]
[8, 8, 3, 8]
[8, 6, 3, 8]
[8, 6, 3, 6]
[8, 6, 3, 5]

编辑：我想我扼杀了对这个问题的解释，让我稍微修正一下。

EDIT2：本质上是跨集合的最小损失，仅从一个内部数组中删除一项。

Answer 1

更新：我最初误解了你的问题。您随后澄清了问题，我在这里提供一个全新的解决方案。

我使用的策略是将所有 sub-arrays 中的所有元素展平到一个数组中，但这样做的方式要记住它们来自哪个原始 sub-array。然后我对展平的数组进行排序，首先按值降序排列，然后按 sub-array 数字升序排列。例如，排序后的展平数组的前 3 个元素将是 [[9,0]、[9,3]、[8,0]、...]，表示 sub-array 0 中的值 9，然后来自 sub-array 3 的值 9，然后来自 sub-array 0 的值 8，等等。然后我继续遍历列表，根据需要获取尽可能多的值，直到达到 n，但为任何 sub-arrays 我还没有选择一个值。

请注意，此解决方案适用于任意数量的 sub-arrays，每个元素具有任意数量的元素。

const array = [
  [1,9,2,8,3],        // hat
  [2,8,3,6],          // shirt
  [1,3],              // pants
  [9,3,2,6,8,2,1,5,2] // boots
];
for (let n = 0; n < 17; n += 1) {
  const valuesChosen = getTopNBest(array, n);
  console.log(`n = ${n}: ${JSON.stringify(valuesChosen)}`);
}

function getTopNBest(array, n) {
  const numTypes = array.length;
  const allElmtsRanked = [];
  array.forEach((sub, typeNum) => {
    sub.forEach(elmt => {allElmtsRanked.push([elmt, typeNum]);});
  });
  allElmtsRanked.sort((a,b) => b[0] - a[0] !== 0 ? b[0] - a[0] : a[1] - b[1]);
  const valuesChosen = array.map(() => null);
  let totalNumValuesExamined = 0;
  let numSecondaryValuesChosen = 0;
  let numUnrepresentedTypes = numTypes;
  let currPair, currValue, currTypeNum;
  while (numUnrepresentedTypes !== 0 || numSecondaryValuesChosen < n) {
    currPair = allElmtsRanked[totalNumValuesExamined];
    currValue = currPair[0];
    currTypeNum = currPair[1];
    totalNumValuesExamined += 1;
    if (valuesChosen[currTypeNum] === null) {
      valuesChosen[currTypeNum] = currValue;
      numUnrepresentedTypes -= 1;
    } else if (numSecondaryValuesChosen < n) {
      numSecondaryValuesChosen += 1;
      valuesChosen[currTypeNum] = currValue;
    }
  }
  return valuesChosen;
}

您随后问我为什么先按值排序然后按 sub-array 数字排序。比较以下两种情况：

var array = [
  [8],
  [9,9,9,9,9],
  [8],
  [8]
]

...与...

var array = [
  [9,8],
  [9,9],
  [9,8],
  [9,8]
]

如果您只是简单地展平这些并对展平的数组进行排序而不保留任何有关 sub-array 值来自哪个信息的信息，那么在这两种情况下您最终都会得到相同的排序展平数组，即

var sortedFlattenedArray = [9,9,9,9,9,8,8,8]

假设您想要 best/most 最佳途径。您现在在任何一种情况下都会得到 [9,9,9,9]，而在第一种情况下您确实想要 [8,9,8,8]。只有记住 sub-array/type 号码才能得到这个，例如：

var sortedFlattenedArray = [[9,1],[9,1],[9,1],[9,1],[9,1],[8,0],[8,2],[8,3]]

因此，当您不再需要任何类型的 sub-optimal 值但您仍在寻找可能的最高值时，实际策略允许您忽略已采样类型的 reasonably-high-but-sub-optimal 值对于特定类型。

这是另一种看待它的方式。这里的策略允许您对所有原始数组进行展平和排序，但要记住每个元素来自哪里。这反过来又允许你在选择路径时有选择性，说 "Ah, the next value is pretty high, which is good, but wait, it's for a hat (which you could only know by being able to read it's associated sub-array/type number) and I've already retrieved my quota of 'sub-optimal values', so I'll ignore this hat value. However, I'll keep moving through the sorted flattened array to find highest remaining value for a shirt (which, again, you could only discover by being able to read its associated sub-array/type number) for which I still haven't yet found any value."

关于从 2D 阵列创建排名路径列表，我需要了解什么？

What do I need to know about creating a list of ranked pathways from 2D array?

javascript

arrays

multidimensional-array

hungarian-algorithm