Комбинаторные алгоритмы

ЛЕКЦИЯ № 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, удовлетворяющих некоторым дополнительным условиям. Иными словами Х Î В12 '… 'В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 á Использовать Х ñ




Ответить

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать HTML- теги и атрибуты:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

76 − = 73