Сводка по изучению алгоритма динамического программирования

Разница между динамическим программированием и жадным и разделяй и властвуй

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

Алгоритм разделяй и властвуйБуквальная интерпретация - «разделяй и властвуй», что означает разделение сложной проблемы на две или более идентичных или похожих подзадач до тех пор, пока конечная подзадача не может быть просто решена напрямую, а решение исходной проблемы представляет собой комбинацию решений подзадач.

Алгоритм динамического программирования (Dynamic Programming, DP)Решайте сложные проблемы, разбивая исходную проблему на относительно простые подзадачи. Часто многие подзадачи очень похожи, по этой причине динамическое программирование пытается решить каждую подзадачу только один раз, тем самым уменьшая объем вычислений: как только решение данной подзадачи решено, оно запоминается, чтобы в следующий раз нужна та же подзадача. Проверяйте таблицу непосредственно при решении.

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

Проблема интервального планирования

Как показано на рисунке ниже, каждый длинный квадрат представляет задание, всегда имеется несколько заданий a, b... h, абсцисса — время, а начальная и конечная точки квадрата — время начала и окончания выполнения. работу соответственно.
Когда рабочие часы двух работ не перекрываются, то есть два квадрата не перекрываются, это означает, что две работы совместимы (compatible).
Когда каждому заданию присваивается значение 1, оно называетсяUnweighted Interval Schedulingпроблема; когда каждой работе присваивается разный положительный вес, это называетсяWeighted Interval Schedulingпроблема.
В конечном итоге проблема состоит в том, чтобы найти подмножество работ, все работы в набореМаксимальная сумма весовиВсе задания в коллекции совместимы.

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

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

Определить P(j)

1. Сначала отсортируйте всю работу по времени окончания;

2. Определить p(j) как наибольшую метку задания перед заданием j, которое совместимо с j. Анализируя время начала и время окончания каждого задания, можно легко вычислить p(j);

3. Например, как показано на рисунке ниже, p(8)=5, поскольку работы 7 и 6 несовместимы с 8, работы с 1 по 5 совместимы с 8, а 5 имеет наибольший индекс, поэтому p (8)= 5. Аналогично, p(7)=3, p(2)=0.

Анализировать рекурсивные отношения

1. Определить opt(j) как наилучшее решение, которое можно выбрать в j заданиях, т. е. opt(j) — наибольшая сумма весов;

2. Для j-й работы возможны два случая:

case 1: Работа j включается в оптимальное решение, затем рекурсивно на один шаг вперед оптимальное решение, которое можно выбрать до j, равно opt(p(j)), то есть

case 2: задание j не находится в оптимальном решении, то выбор набора решений из заданий j аналогичен выбору набора решений из заданий j-1, т. е.

3. Когда j=0, результат отображения равен 0, что является граничным условием.

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

Код

1. Рекурсивный метод

Рекурсия увеличивает сложность пространства и, как правило, не рекомендуется.

2,подход «снизу вверх

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

Проблема с рюкзаком

Постановка задачи о рюкзаке

Как показано на рисунке ниже, в рюкзаке Knapsack есть несколько предметов.

Каждый предмет имеет свой вес, соответствующий значению

Общий вес рюкзака ограничен W

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

Например, на рисунке ниже распространенная жадная идея состоит в том, чтобы выбирать предметы с более высокой стоимостью, насколько может поместиться рюкзак. Затем, когда вместимость рюкзака равна W=11, сначала выберите предмет 5, затем предмет 2, и, наконец, можно положить только предмет 1, и общее значение составит 28+6+1=35. На самом деле оптимальное решение — выбрать item3 и item4, а значение равно 18+22=40. Это показывает, что жадный алгоритм может быть не лучшим решением задачи о рюкзаке. Учитывая использование алгоритма динамического программирования для решения проблемы, сначала необходимо вывести рекурсивное отношение.

Получите рекурсивное отношение

Аналогично задаче взвешенного интервального планирования, определитеopt(i, w) представляет собой максимальное значение и сумму, которые могут быть получены, когда есть i предметов, а оставшаяся вместимость рюкзака равна w.

Рассматривая i-й элемент, возможны два случая: выбранный и не выбранный:

case 1: Если выбран i-й элемент, то

case 2: Если i-й пункт не выбран, то

Граничное условие: когда i=0, очевидно, opt(i,w)=0.

Решить снизу вверх

Итерационный процесс алгоритма выглядит следующим образом:

Анализ времени выполнения алгоритма

Стоит отметить, что алгоритм не является полиномиальным по размеру входных данных, хотя O(nW) очень похоже на полиномиальное решение.Задача о рюкзаке на самом деле является NP-полной задачей..

Для простоты понимания его можно записать в таком виде:

W — это просто число в компьютере, хранящееся в пространстве длины logW, что очень мало. Но в реальной работе при изменении W требуется вычислить nW раз, что очень много (относительно logW). Например, когда W равно 5 кг, принимая кг за базовую единицу, необходимо вычислить O(5n) раз, когда W равно 5t, он по-прежнему принимает кг в качестве единицы и должен вычислить O(5000n) раз, а изменение W в компьютере Сумма относительно невелика.

Sequence Alignment

Define edit distance

Даны две последовательности x1,x2...xi и y1,y2,...,yj. Чтобы сопоставить эти две последовательности, сделайте сходство достаточно большим. Прежде всего, необходимо определить количество, которое представляет стоимость - Расстояние редактирования, Только за счет оптимизации это количество является наименьшим, что эквивалентно максимальному совпадению этих двух последовательностей.

Определение расстояния редактирования показано ниже.

Среди них, если совпадение пустое, установить расстояние дельта, иначе расстояние между буквами p и q записывается как альфа(p,q), если p=q, то альфа=0;

Тогда общая стоимость сопоставления двух последовательностей равна:

Создать рекурсивную связь

Пусть opt(i,j) — минимальная стоимость сопоставления последовательностей x1,x2...xi и y1,y2,...,yj. Когда i, j не все равны 0, соответственно есть три случая, а именно xi-gap, yj-gap, xi-yj, соответственно вычислите стоимость различных совпадающих случаев, плюс результат предыдущего шага, вы можете установить повторение отношение показано ниже.

Реализация алгоритма

Алгоритмическая сложность

И временная, и пространственная сложность составляют O(mn).

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

хор вопрос

определение проблемы

В ряду стоят n учеников, у каждого ученика есть значение способности, Ниуниу хочет выбрать k учеников по порядку из этих n учеников,Требуется, чтобы разница между номерами позиций двух соседних студентов не превышала d, который максимизирует произведение значений способностей студентов k. Можете ли вы вернуть наибольший продукт?

введите описание

Каждый вход содержит 1 тестовый пример. Первая строка данных каждого теста содержит целое число n (1 ай (-50 . Следующая строка содержит два целых числа, k и d (1

выходное описание

Одна строка вывода представляет самый большой продукт.

анализ проблемы

Первый ключевой момент этого вопроса: «требуется, чтобы разница между номерами позиций двух соседних студентов не превышала d», если в соответствии с традиционным мышлением DP определение opt(i,k) означает выбор k среди первых i студенты Максимальный продукт студентов, чтобы установить рекуррентное соотношение:

Тогда требование «разность номеров позиций двух соседних студентов не превосходит d» не может быть достигнуто. Следовательно, необходимо определить вспомогательную величину, содержащую информацию о местоположении текущего ученика.

Задайте f(i,k), чтобы выбрать k учеников из первых i учеников, иТребуется для i-го студентаКогда , произведение значения способностей выбранного учащегося, которое содержит информацию о местоположении текущего учащегося, рекуррентное отношение f может быть выражено как

Среди них значение j меньше i, максимальное значение i-1, разница между i и j не превышает D, f(j, k-1) означает, что среди первых j студентов выбрать k-1 студентов , и Требуется j-й студент. f(i,k) выбирает i-го студента, f(j,k-1) выбирает j-го студента, и разница между i и j не превышает D, так что требования вопроса могут быть выполнены.

Вспомогательная величина f(i,k) не является окончательным результатом, который мы хотим получить. Конечный результат opt(i,k) представляет собой максимальное произведение k студентов, выбранных среди первых i студентов, поэтому opt(i,k) может быть получена Связь с f(i,k):

Второй ключевой момент этой проблемы заключается в том, что значение способности ученика находится в диапазоне от -50 до +50, а значение способности каждого выбранного ученика положительное или отрицательное, поэтому необходимы две f для записи максимального и минимального значений, определения fmax и fmin , на каждой итерации f:

Когда k=K, i=N, окончательное требование таково:

Когда граничное условие k=1, f(i,k=1)=v(i)

Код

/*********************************************************************
*
* Ran Chen <wychencr@163.com>
*
* Dynamic programming algorithm
*
*********************************************************************/

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
    int N, D, K;  // 总共N个学生
    vector <int> value;

    while (cin >> N)
    {
    
        for (int i = 0; i < N; ++i)
        {
            int v;
            cin >> v;
            value.push_back(v);
        }

        break;
    }

    cin >> K;  // 选择K个学生
    cin >> D;  // 相邻被选择学生的序号差值

    // fmax/fmin[i, k]表示在选择第i个数的情况下的最大/小乘积
    vector <vector <long long>> fmax(N+1, vector <long long> (K+1));
    vector <vector <long long>> fmin(N+1, vector <long long> (K+1));

    // 边界条件k=1
    for (int i = 1; i <= N; ++i)
    {
        fmax[i][1] = value[i - 1];
        fmin[i][1] = value[i - 1];
    }

    // 自底向上dp, k>=1
    for (int k = 2; k <= K; ++k)
    {
        // i >= k
        for (int i = k; i <= N; ++i)
        {
            // 0 <= j <= i-1 && i - j <= D && j >= k-1
            long long *max_j = new long long; *max_j = LLONG_MIN;
            long long *min_j = new long long; *min_j = LLONG_MAX;
    
            // f(i, k) = max_j {f(j, k-1) * value(i)}
            int j = max(i - D, max(k - 1, 1));
            for ( ; j <= i - 1; ++j)
            {
                *max_j = max(*max_j, max(fmax[j][k - 1] * value[i - 1], fmin[j][k - 1] * value[i - 1]));                
                *min_j = min(*min_j, min(fmax[j][k - 1] * value[i - 1], fmin[j][k - 1] * value[i - 1]));            
            }

            fmax[i][k] = *max_j;
            fmin[i][k] = *min_j;
            
            delete max_j; 
            delete min_j;
        }
    }

    // opt(N, K) = max_i {f(i, K)}, K <= i <= N
    long long *temp = new long long;
    *temp = fmax[K][K];
    for (int i = K+1; i <= N; ++i)
    {
        *temp = max(*temp, fmax[i][K]);
    }
    cout << *temp;
    delete temp;

    system("pause");
    return 0;
}

скопировать код