Комбинаторные алгоритмы
ЛЕКЦИЯ № 10
При поиске оптимального варианта из некоторого допустимого набора часто приходится перебирать все возможные альтернативы. Во многих задачах перебираемые варианты являются членами сочетаний, размещений и других комбинаторных конфигураций. Поэтому большое значение имеют алгоритмы генерации элементов соответствующих конечных множеств.
Главная сложность составления таких ”генераторов” состоит в необходимости сделать их структуру независимой от размерности порождаемых ими множеств, которая может очень сильно варьироваться в различных задачах. Например, алгоритм генерации r-размещений с повторениями очень легко реализовать с помощью r вложенных циклов:
for j1 := 1 to n do
for j2 := 1 to n do
…………………..
for jR := 1 to n do writeln (j1, j2, … jR);
Ясно, что всякий раз при изменении значения r такую программу пришлось бы переделывать, добавляя или удаляя циклы, и на самом деле алгоритм генерации должен быть другим.
Другой особенностью предлагаемых алгоритмов является то, что в них вместо комбинаций самих объектов генерируются комбинации из их номеров. Очевидно, что такие расстановки легко преобразовать в манипуляции, например, с названиями объектов, введя в программу массив из строк символов соответствующей размерности.
Многие из комбинаторных конфигураций удобно генерировать с помощью алгоритма поиска с возвратом.
Общая схема рекурсивного поиска с возвратом. Пусть дано n упорядоченных множеств В1, В2,… Вn. Требуется найти набор векторов вида Х = (х1, х2,… хn), где xiÎВi, удовлетворяющих некоторым дополнительным условиям. Иными словами Х Î В1´В2 ´… ´Вn.
В алгоритме поиска с возвратом каждый вектор Х строится покомпонентно слева направо. Предположим, что уже найдены первые k – 1 компонент х1, х2,… хk–1. Тогда их значения определяют некий набор условий, ограничивающих выбор k-й компоненты некоторым множеством Sk Í Вk. Если Sk не пусто, мы вправе выбрать в качестве хk первый по порядку элемент из Sk, присоединить его к уже выбранным компонентам, и перейти к выбору хk+1 и так далее. Однако, если набор условий таков, что Sk пусто, то мы возвращаемся к выбору k–1-й компоненты. При этом мы отбрасываем хk–1 и выбираем в качестве новой k–1-й составляющей вектора Х тот элемент из Sk–1, который непосредственно следует за только что отброшенным хk–1.
Предположим теперь, что в процессе поиска новых компонент мы дошли до конца, т.е. выбрали хn. Теперь надо как-то использовать полученный вектор Х, в соответствие с условием задачи. Например, если в задаче требуется найти лучший из векторов, то нам следует сравнить построенный вектор Х с решением, которое до данного момента считалось оптимальным и если Х окажется лучше, то надо обновить текущее оптимальное решение, вернуться на шаг назад и продолжить поиски новых решений.
Этот процесс продолжается, пока не будут рассмотрены все возможные вектора решений.
Данная схема легко реализуется посредством рекурсивной процедуры.
procedure Solve ( k );
{ k – номер подбираемой координаты (номер глубины рекурсии) }
{ Х – вектор текущего решения }
begin if á Х – решение ñ then á Использовать Х ñ