Задача оптимизации

Question

Я слишком плотный, чтобы решить следующую задачу оптимизации:

Существует двумерный массив, скажем, символы в зависимости от времени, например

A 1114334221111 
B 9952111111111
C 1113439111131
D 1255432245662

Существует также список символов, например:

CABDC

Вы должны выбирать значения из массива в порядке символов, но вы можете повторять символ столько раз, сколько захотите. Вы должны выбрать хотя бы одно значение для каждого символа, и вы должны пройти весь список. Например, одна возможность может быть:

  CCCAAAAAABDDC
  1114334221661 = 35

Есть ли алгоритм для выбора списка символов, сумма которых равна максимальному значению? На первый взгляд это похоже на алгоритм обратного отслеживания, но он может выродиться в экспоненциальное время.

Answer 1

Подход, который я, вероятно, выбрал бы, будет выглядеть так:

Создайте массив ("X") из (N+1)xM элементов, где N = "ширина" вашего 2D-массива и M = количество символов в вашем списке.

Установите X[0][i] = 0 для всех значений i (в диапазоне M). Это связано с тем, что максимально возможная сумма первых 0 выбранных элементов равна 0. Мы также можем заполнить X[a][b] как 0 для любого b>=a, поскольку эти позиции являются теми, к которым мы не смогли бы добраться (у нас не было бы выбрал достаточно символов, чтобы быть в этом символе еще). Точно так же мы можем установить «треугольник» значений в конце массива также на 0, так как для достижения одного из этих индексов нам нужно было бы выбрать слишком много повторений более ранних символов, чтобы иметь возможность выбрать хотя бы один элемент для более поздних символов.

Теперь установите X[1][i] равным максимально возможной сумме первых 1 выбранных элементов, если текущий выбранный символ является символом i в последовательности. Это довольно просто вычислить - это просто соответствующее значение для этого символа из массива.

Теперь установите X[2][i] равным максимально возможной сумме первых 2 выбранных элементов, если текущий выбранный символ является символом i в последовательности. Это также довольно тривиально, хотя и не так просто, как было [1] - в конце концов, теперь это соответствующее значение символа плюс максимум либо X[1][i-1], либо X[1][i] - потому что мы могли либо начните текущий символ с этой позиции, либо уже начали с более ранней позиции.

Продолжайте алгоритм для каждого X[k] (установка X[k][i] равна максимальному из X[k-1][i-1] или X[k-1][i], плюс соответствующее значение символа для текущего i), пока k не достигнет N , Максимальное значение в вашем столбце X[k] - ваш максимальный результат.

Поскольку в целом вам нужно только смотреть на каждый элемент массива постоянное число раз, общий алгоритм запускается за O(MN) времени.

(Обратите внимание, что технически вам не нужен весь массив NxM в памяти все время, только предыдущий столбец и текущий столбец. Это проще объяснить в терминах полного массива. Таким образом, оптимизированная версия этого алгоритм использует O(M) памяти.)

Пример массива результатов из вашего примера:

       0  1  2  3  4  5  6  7  8  9  10 11 12 13
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
0 - C | 0| 1| 2| 3| 6|10|13|22|23|24| 0| 0| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1 - A | 0| 0| 2| 3| 7|10|13|17|24|26|27| 0| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
2 - B | 0| 0| 0| 7| 9|10|11|14|18|25|26|28| 0| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
3 - D | 0| 0| 0| 0|12|16|19|21|23|27|32|38|44| 0|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
4 - C | 0| 0| 0| 0| 0|16|19|28|29|30|31|33|36|45|
      +--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Если вы сохраняете (в каждой позиции массива), какой предыдущий символ использовался как часть общей суммы этой позиции, то легко просто прочитать обратно путь, который ведет от нижнего правого угла к верхнему левому углу, чтобы выяснить, что такое максимальная последовательность Кроме того, вы можете просто проследить назад, посмотрев, какое из двух значений - левое или левое - больше вашей текущей позиции. В этом случае максимальная последовательность CABDDDDDDDDDC.

Answer 2

вы можете сделать это проблемой кратчайшего пути, но в отличие от того, что сказал Fragsworth, вам не нужно менять алгоритм, просто как вы представляете данные:

каждый узел на вашем графике - это отдельная ячейка в вашем двумерном массиве, и вы соединяете узлы в соответствии со своим списком с весом, установленным в 10 - cellValue. вы не подключаете узлы, которые не следуют правилам (вы не подключите b [4] к a [5], потому что его нет в списке "order")

Примеры:

c [0] подключиться к c [1] с весом 9 (значение 10 - c [1], равное 1) => это опция для выбора "C"

c [0] подключиться к [1] ​​с весом 9 (10 - значение [1], равное 1) => это опция для выбора «A»

b [2] подключиться к b [3] с весом 8 (значение 10 - b [3], равное 2) => это опция для выбора «B»

b [2] подключиться к d [3] с весом 5 (значение 10 - d [3], равное 5) => это опция для выбора «D»

единственная проблема, с которой вы столкнулись, - это полностью избавиться от опции, которую вы выбрали «CCCCC ...», что противопоставляется путем указания второй «C» в вашем списке «CABDC» как (C2) и только подключите его к узлам D (или другим узлам C2) в вашем примере.

Теперь вы запускаете любой стандартный алгоритм кратчайшего пути (без необходимости его изменения), начиная с c [0] и заканчивая c2 [n], поскольку веса противоположны значению, кратчайший путь, который вы получите, будет сумма максимальных значений.

Answer 3

Это выглядит как небольшое изменение кратчайшего пути . Считайте, что каждый элемент вашего массива является узлом в орграфе. Вы должны иметь возможность изменить любой из стандартных алгоритмов кратчайшего пути, чтобы добавить порядок символов.

Answer 4

Существует ли алгоритм для выбора списка символов, сумма которого максимально равна?

Это должно быть легко, так как вы сказали, что можете повторять символ сколько угодно раз. и вы не сделали никаких ограничений на количество символов или необходимость использования каждого символа.

( Я подозреваю, что это, вероятно, слишком просто, и вы просто не описали всю проблему, но в любом случае вот решение )

for i through the length of array in time
    symbol, value = get_max_value(array[i]) # iterates through every symbol to find max at the given time
    print symbol, value

Answer 5

Вы можете использовать жадный алгоритм с некоторыми ограничениями. Вам всегда придется выбирать между текущим или следующим символом. Если эквивалент для текущего символа больше, чем следующий (и вы сможете поместить все оставшиеся символы позже), используйте текущий символ. Если следующий номер символа больше, выберите следующий. Если они одинаковые, вам потребуется дополнительная логика, чтобы решить.