Получение фактических шагов решения, которое было получено с использованием динамического программирования

Question

Если динамическое программирование используется для получения оптимального решения проблемы.Как вы восстанавливаете фактические шаги, которые приводят к этому решению?

Например, в задаче о ранце 0-1 вы используете повторение

Использованиемы можем получить максимальное значение, которое может присутствовать в рюкзаке.Как вы находите настоящие предметы.

Может ли это быть обобщено для любого решения динамического программирования.Например,Чтобы найти действительные числа, которые являются частью самой длинной увеличивающейся подпоследовательности, решение которой было получено с помощью динамического программирования.

Answer 1

Может ли это быть обобщено для любого решения динамического программирования.

Нет, вы не можете в целом найти реальное решение, проверив окончательные значения в таблице DP.

Если алгоритм просто ищет какое-то оптимальное значение, он, как правило, отбрасывает информацию о способе каждого значения, вычисленного.

В DP-решении ячейка в строке R может, например, зависеть от максимального значения в строке R-1 . Если алгоритм не запишет, какая ячейка была выбрана, будет невозможно восстановить фактическое решение на основе полученной таблицы.

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

Answer 2

Хитрость заключается в том, чтобы хранить дополнительную информацию, которая позволит вам восстановить выбор, сделанный на каждом шаге, при заполнении таблицы динамического программирования. Иногда сама таблица содержит такую ​​информацию. Например, в задаче о ранце 0/1 вы можете узнать, какие предметы используются для достижения оптимального решения (обратите внимание, что нужна только таблица):

# 0/1 knapsack. O(nC) time, O(nC) space,
# also returns the index of the items to pick
# V: values, W: weights, C: capacity

def integral_knapsack_items(V, W, C):
    table = integral_knapsack_table(V, W, C)
    i, j, items = len(W), C, []
    while i != 0 and j != 0:
        if table[i][j] != table[i-1][j]:
            items.append(i-1)
            i, j = i-1, j-W[i-1]
        else:
            i -= 1
    return (table[-1][-1], items)

def integral_knapsack_table(V, W, C):
    m, n = len(W)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for i in xrange(1, m):
        for j in xrange(1, n):
            if W[i-1] > j:
                table[i][j] = table[i-1][j]
            else:
                table[i][j] = max(table[i-1][j],
                                  V[i-1] + table[i-1][j-W[i-1]])
    return table

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

Answer 3

Вам просто нужно пересмотреть свои шаги в DP.В случае ранца 0-1, допустим, исходная функция DP была решить , а функция реконструировать даст вам реальное решение (я пишу код на C ++):

int solve(int pos, int capacity)
{
    if(pos == no_of_objects) return 0;
    if(memo[pos][capacity] != -1) return memo[pos][capacity];

    int r1 = solve(pos + 1, capacity); //dont take
    int r2 = 0;
    if(weight[pos] <= capacity)
    {
        r2 = solve(pos + 1, capacity - weight[pos]) + profit[pos]; //take
    }
    return memo[pos][capacity] = max(r1, r2);
}

void reconstruct(int pos, int capacity)
{
    if(pos == no_of_objects) return; //you have completed reconstruction

    int r1 = memo[pos + 1][capacity]; //dont take
    int r2 = 0;
    if(weight[pos] <= capacity)
        r2 = memo[pos + 1][capacity - weight[pos]] + profit[pos]; //take

    if(r1 > r2) 
    {
        reconstruct(pos + 1, capacity);
    }
    else
    {
        cout << "Take object " << pos << endl;
        reconstruct(pos + 1, capacity - weight[pos]) + profit[pos]; 
    }
}

После выполнения реконструкция , он напечатает все те объекты, которые дают вам оптимальное решение.Как видите, самое большее no_of_objects будет выполнено в функции реконструкция .Точно так же вы можете жадно восстановить решение любого DP.

Answer 4

Большинство алгоритмов динамического программирования используют Memoization и Backtracking.Мемоизация - это своего рода справочная таблица, в которой алгоритм хранит информацию о состоянии на каждом шаге.Как только алгоритмы заканчивают работу, он использует возврат для перехода от последнего состояния алгоритма к предыдущему.На кнапсаке это можно было получить, сохранив "откуда я пришел?"значение.Как вычислили M [i, w]?Либо из m [i-1.w], либо из m [i-1, w-wi] + vi.Ищите Memoization и Backtracking, чтобы получить больше примеров.