20. В чем идея метода динамического программирования для решения комбинаторных задач?

Метод динамического программирования (ДП)² был предложен известным математиком Р.Беллманом как очень общий подход к решению некоторых типов задач из разных областей дискретной и непрерывной математики, включая даже вариационное исчисление

Решение комбинаторной задачи методом ДП выглядит следующим образом:

• Вместо исходной задачи рассматривается более общая совокупность задач, различающихся размерностью и другими параметрами.

• На первом этапе решаются самые простые задачи из этой совокупности (с минимальной размерностью) и результаты их решения при разных значениях параметров собираются в таблицу.

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

• На последнем этапе находится решение исходной задачи, при этом используется таблица результатов предпоследнего этапа

21. Что такое уравнение Беллмана? Что является неизвестным в этом уравнении?

v(1,y) = entier(y/b₁)  c_i ;

v(k,y) = max(c_kx_k + v(k-1, y - b_kx_k)) для k > 1.

Максимум берется по всем значениям x_k таким, что 0  x_k  entier(y/b_k), а функция entier, кто не помнит, означает целую часть числа

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

Второе соотношение чуть посложнее. Мы можем положить в пустой рюкзак объема y любое число единиц k-того товара от 0 до entier(y/bk). Пусть это число равно xk, тогда стоимость k-того товара в рюкзаке будет равна ckxk, объем этого товара составит bkxk, а на все товары с номерами от 1 до k-1 останется y - bkxk единиц свободного объема. Какую максимальную стоимость можно получить от использования этого объема? По определению функции v, это есть не что иное, как v(k-1, y - bkxk)! Максимум по всем возможным значениям xk позволяет определить наиболее выгодное количество k-того товара.

Подобные функциональные уравнения, связывающие значения функции v для разных значений аргументов, очень характерны для метода ДП и называются уравнениями Беллмана. Искусство применения метода ДП к конкретным задачам заключается в построении уравнений Беллмана для данной задачи.

Когда уравнения получены, решение задачи сводится к табулированию функции v(k,y) при возрастающих значениях k

22. Что за величины заносятся в таблицу при решении задачи о рюкзаке по алгоритму Беллмана?

Теперь протабулируем функцию v(k,y) для данного примера. Кроме значений функции, будем запоминать те значения x_k, при которых достигается максимум в уравнении Беллмана

23. Какова оценка эффективности алгоритма Беллмана для задачи о рюкзаке?

Оценим, как зависит трудоемкость алгоритма Беллмана от основных параметров задачи: числа видов товаров n и объема рюкзака B. Число столбцов таблицы равно n, а число строк – B+1. Трудоемкость вычисления одного значения в таблице пропорциональна количеству членов, из которых выбирается максимум, а это количество пропорционально B. Таким образом, T(n,B) = O(nB²).

24. Как формулируется задача о минимальной триангуляции? В чем идея алгоритма ее решения?

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

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

25. Как формулируется задача о максимальной подпоследовательности? В чем идея алгоритма ее решения?

даны две строки, требуется найти подпоследовательность наибольшей длины, входящую в оба слова.

Вначале найдём длину наибольшей подпоследовательности. Допустим мы ищем решение для случая (n1, n2), где n1, n2— длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2) меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:

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

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

Очевидно, что время работы алгоритма будет O(n2).

Решение-динамическое программирование, где текущее значение ищется с помощью предыдущих, в данном случае нам нужно завести дву-мерный массив и n*m где 0 строка и 0 столбец заполняются 0, затем последовательно заполняем получившуюся матрицу по данному алгоритму(s[n] вроде н-тый символ строки), и в последних строке и столбце находим максимальное значение.

26. Что такое рекурсия с запоминанием? В каких случаях она может быть эффективнее, чем рекуррентное заполнение таблиц?

27. Что такое эвристический алгоритм? В каких случаях используются такие алгоритмы?

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

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

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

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

28. Что такое «жадный» алгоритм?

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

29. Почему алгоритмы последовательного улучшения плана желательно сочетать со случайным выбором плана?

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

Основным недостатком алгоритмов локальной оптимизации является то, что они совсем не обязательно приводят к глобально оптимальному плану задачи. В частности, для алгоритмов последовательного улучшения очень важен удачный выбор исходного плана. (Представьте себе альпиниста, который «локально оптимально» выбирает всегда путь, ведущий вверх. В конце концов он доберется до какой-нибудь вершины, но это может быть вершина маленького холмика, а не вершина самой высокой горы). Полезную роль может сыграть использование случайного выбора для построения исходного плана. Случайно выбранный план будет, скорее всего, сам по себе хуже, чем план, построенный по алгоритму последовательного выбора (хотя и не обязательно), но при многократном повторении комбинации «случайный выбор + последовательное улучшение» возрастает вероятность хотя бы раз оказаться «на склоне нужной горы» и придти к глобальному оптимуму