1. Комбинаторные задачи: основные понятия.

Комбинаторными задачами называются такие задачи, которые можно свести к следующей общей постановке. Имеются N переменных x₁, x₂,... x_N, принимающие значения из конечных множеств U₁, U₂, ... U_N. Каждый набор значений X = (x1, x2, ... xN) будем называть планом данной задачи. Задана также некоторая функция G(X,P), принимающая булевские значения (здесь P – параметры задачи. Всякий план X, для которого при данномP функция G(X,P) = True, называется допустимым планом данной задачи. Далее возможны различные постановки задачи, а именно:

A) Найти какой-нибудь допустимый план, если таковой существует (задача поиска).

B) Найти все допустимые планы данной задачи (задача перечисления).

C) Найти допустимый план, минимизирующий заданную функцию F(X,P) (задача оптимизации).

2. Методы перебора для комбинаторных задач.

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

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

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

3. Способы сокращения перебора при решении комбинаторных задач

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

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

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

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

4. Метод ветвей и границ: общие принципы

 Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

Процедура нахождения оценок заключается в поиске верхних и нижних границ.

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

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

5. Метод ветвей и границ: решение задачи о коммивояжере

Идея метода. Пусть   – множество всех допустимых замкнутых маршрутов задачи о коммивояжере с n городами.

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

На каждом шаге выбирается подмножество с наименьшей оценкой и производится его разбиение на два подмножества.

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

6. Метод a-b отсечений

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

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

Альфа-бета отсечение является оптимизацией.

7. Метод динамического программирования: общие принципы

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

• Разбиение задачи на подзадачи меньшего размера.

• Нахождение оптимального решения подзадач рекурсивно

• Использование полученного решения подзадач для конструирования решения исходной задачи.

8. Метод динамического программирования: задача о рюкзаке

Наилучшие частичные наборы хранятся в хэш-таблице, т. е. для каждого веса храниться максимальная стоимость.

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

В конце остается только выбрать самый дорогой из них.

Сложность этого алгоритма — O(nB), где В – размер рюкзака.

9. Метод динамического программирования: задачи о минимальной триангуляции и о максимальной общей подпоследовательности.

Задача о минимальной триангуляции:

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

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

Задача о максимальной общей последовательности:

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

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

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

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

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

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