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

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

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

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

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

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

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

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

Максимумы функции и количество товаров, при которых оно достигается.

24. Как получить оптимальный план при решении задачи о рюкзаке по алгоритму Беллмана?

Мы должны найти максимальную стоимость в строке у=B. X_i при максимальной стоимости умножить на объем данного товара k. Полученное число вычесть из текущего объема рюкзака. И перейти к новому у. Это действие выполнять до тех пор, пока v не равно 0.

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

T(n,B) = O(nB²). числа видов товаров n и объема рюкзака B.

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

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

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

1. Во множество исходных точек помещаются концы всех структурных отрезков.

2. Генерируются отрезки, соединяющие все пары точек, отрезки сортируются по длине.

3. В триангуляцию вставляются все отрезки структурных линий.

4. В триангуляцию последовательно отбираются отрезки из множества отсортированных по длине отрезков (от более коротких к более длинным). Если отрезок пересекается с каким-нибудь из уже вставленных, то он отбрасывается, иначе вставляется в триангуляцию. Шаг 4 повторяется, пока не кончатся отрезки или число вставленных не достигнет 3⋅(n−6).

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

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

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

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

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

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

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

Очень часто приходится жертвовать точностью определения экстремума ради сокращения времени его определения.

30. Что такое приближенные (субоптимальные) алгоритмы и чем они отличаются от эвристических?

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

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

Это алгоритм локально пошаговой оптимизации.

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

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

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

33. В чем идея генетических алгоритмов?

Упрощенно механика работы генетического алгоритма выглядит так:

— инициируем исходную популяцию — выбирая случайным образом подмножество возможных значений (популяцию хромосом);

дальше собственно сам генетический алгоритм:

— рассчитываем для каждой хромосомы из популяции значение функции приспособленности (которая задана таким образом, что бы характеризовать параметр по которому проводится поиск оптимального решения);

— выбираем хромосомы, которые будут участвовать в скрещивании (чем больше значение функции приспособленности хромосомы тем больше у нее вероятность принять участие в скрещивании)

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

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