时间戳

首页 > 解决方案 > 关于实现标签设置/校正/动态规划的问题

algorithm - 关于实现标签设置/校正/动态规划的问题

问题描述

对于那些熟悉这个算法的人。我的问题是，您如何编写通过动态编程获得有效子集的部分？我理解逻辑，但无法将其放入代码中，因为标签维度通常非常高，如何在不编写 10 个或 100 个嵌套“for”循环的情况下实现它？

对于那些不熟悉这个算法的人。我的问题是，如何找到具有非显性元组的最大子集。我们说元组 A 支配元组 B，如果元组 A 中的所有元素都小于元组 B 中的元素，B[0] < A[0] & B[1] < A[1] & B[2] < A[2] & ...... 像 B 这样的元组应该从集合中删除。

例如，考虑下面的元组集

(1, 7, 1, 5, 2), (6, 2, 3, 3, 2), (5, 5, 6, 9, 8), (2, 4, 9, 9, 7), (4 , 1, 2, 8, 7), (3, 0, 2, 0, 2), (5, 1, 1, 1, 3), ...

(3, 0, 2, 0, 2) 支配 (6, 2, 3, 3, 2), (5, 5, 6, 9, 8), (4, 1, 2, 8, 7)

如何在不编写 5 个嵌套 for 循环的情况下进行编程？如果我用递归写，那么会有很多重复的计算，但是如果我使用迭代，那么我需要一个5维数组来保存结果。

标签： algorithmdynamic-programming

解决方案

如果我理解正确，您担心的是您将拥有一个n维数组A，您需要在其中进行以下操作：

  • 您需要以这样一种方式迭代数组元素，即在您沿每个维度（A [ i 0 −1][ i 1 ][…][ i n −1 ]、A [ i 0 ][ i 1 −1][…][ i n −1 ]、…和A [ i 0 ][ i 1 ][…][ i n -1-1]）。
  • 当访问A [ i 0 ][ i 1 ][…][ i n -1 ] 时，您需要沿每个维度检查它的前任。

并且您担心这样做的唯一方法是为i 0、i 1、……和i n -1中的每一个设置单独的变量，并为每个变量设置一个 for 循环。

（在我看来，你的部分担忧似乎过分了——你提到“10 个或 100 个嵌套的 'for' 循环”，但无论如何你不能存储 2100个元素，这比地球上所有计算机中的所有数据都多——但是即使是五个嵌套的 for 循环也是混乱且容易出错的，当然你会被绑定到特定数量的维度。所以，不想这样做是合理的。）

您可以通过将“逻辑” n维数组表示为具有适当数量元素的“基础”一维数组来解决此问题，使用整数数组作为“逻辑”索引，并编写逻辑以在该数组之间进行映射和一个“基础”索引，它是一个整数。

例如，如果您的“逻辑”数组AA是 10×10×10×10×10，那么您可以创建一个长度为 10 5的单个“基础”数组，并且元素位于“逻辑”位置 [3,4,5 ,6,7] — 表示A [3][4][5][6][7] — 是A[34_567]. 这是一个从前者转换为后者的 Java 方法：

public int getUnderlyingIndex(
    final int[] index,
    final int[] dimensions
) {
    int result = 0;
    for (int dim = 0; dim < dimensions.length; ++dim) {
        result = result * dimensions[dim] + index[dim];
    }
    return result;
}

出于迭代目的，您需要一个函数来“增加”索引 - 例如，给定 [1,2,3,9,9] 它会将其更改为 [1,2,4,0,0] - 并让您知道你是否已经通过了数组的末尾。这是 Java 中的样子：

public boolean incrementIndexArray(
    final int[] index,
    final int[] dimensions
) {
    int dim = index.length - 1;
    while (true) {
        index[dim]++;
        if (index[dim] < dimensions[dim]) {
            return true; // iteration can continue
        }
        index[dim] = 0;
        --dim;
        if (dim < 0) {
            return false; // done iterating
        }
    }
}

为了检查元素的前身，您可以编写一个 for 循环。这是 Java 中的样子：

for (int dim = 0; dim < dimensions.length; ++dim) {
    if (index[dim] == 0) {
        // no predecessor along this dimension
        continue;
    }
    index[dim]--;
    final int predecessor =
        underlyingArray[getUnderlyingIndex(index)];
    index[dim]++;
    // ... do what you want with it ...
}

推荐阅读