Вопрос о реализации настройки / коррекции меток / программирования Dynami c

Question

Для тех из вас, кто знаком с этим алгоритмом. Мой вопрос: как вы кодируете часть получения эффективного подмножества с помощью Dynami c программирования? Я понимаю логику c, но просто не могу поместить ее в код, потому что размер метки обычно довольно высок, как вы реализуете ее без записи 10 или даже сотен вложенных циклов for?

Для тех из вас, кто не знаком с этим алгоритмом. Мой вопрос в том, как найти наибольшее подмножество с недоминантными кортежами. мы говорим, кортеж B доминант кортежа A, если все элементы внутри кортежа 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 вложенных циклов? Если я напишу это с помощью рекурсии, то будет много повторяющихся вычислений, но если я буду использовать итерации, то для сохранения результата мне понадобится 5-мерный массив.

Answer 1

Если я правильно понимаю, вы обеспокоены тем, что у вас будет n -мерный массив A , для которого вам понадобятся следующие операции:

• Вам нужно перебрать элементы массива так, чтобы вы не посещали A [ i ₀ ] [ i ₁ ] […] [ i _{n −1} ] до тех пор, пока вы не посетили его предшественника по каждому измерению ( A [ я ₀ -1] [ я ₁ ] [...] [ я _{n -1} ], A [ i ₀ ] [ i ₁ -1] […] [ i _{n -1} ],… и A [ i ₀ ] [ я ₁ ] [...] [ я _{п -1} -1]).
• При посещении A [ i ₀ ] [ i ₁ ] […] [ i _{n −1} ], вам нужно изучить его предшественника a Длинное каждое измерение.

и вы беспокоитесь, что единственный способ сделать это - иметь отдельные переменные для каждого из i ₀ , i ₁ ,… и i _{n −1} , и имеют для -l oop для каждого один.

(Часть вашего беспокойства кажется мне чрезмерной - вы упоминаете «10 или 100» вложенных «для» циклов », но вы все равно не можете хранить 2 ¹⁰⁰ элементов, это больше, чем все данные на всех компьютерах на Земле - но даже пять вложенных циклов for являются грязными и подвержены ошибкам, и, конечно, тогда вы привязаны к определенному количеству измерений c. Поэтому разумно не делать этого.)

Вы можете решить эту проблему, представив свой «логический» n -мерный массив как «базовый» one -мерный массив с соответствующим количеством элементов, использующий массив целых чисел в качестве «логического» индекса и записывающий logi c для отображения между этим массивом и «базовым» индексом, представляющим собой одно целое число.

Например, если ваш «логический» массив A равен 10 × 10 × 10 × 10 × 10, то вы можете создать один «базовый» массив A длиной 10 ⁵ и элемент в «логической» позиции [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-l oop. Вот как это может выглядеть в 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 ...
}