Вычислительная схема перебора с возвратом
Home Up Next

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

Пусть M0, M1, ..., Mn-1 - n конечных линейно упорядоченных множеств и G - совокупность ограничений (условий), ставящих в соответствие векторам вида v = (v0, v1, ..., vk)T (vj Î Mj j = 0, 1, ... k; k£n-1), булево значение G(v) Î {истина, ложь}. Векторы v = (v0, v1, ..., vk)T, для которых G(v) = истина, назовем частичными решениями. Пусть, далее, существует конкретное правило P, в соответствии с которым некоторые из частичных решений могут объявляться полными решениями. Тогда возможна постановка следующих поисковых задач:

Найти все полные решения или установить отсутствие таковых.

Найти хотя бы одно полное решение или установить его отсутствие.

Наиболее часто подобные задачи формулируются и решаются при следующем задании правила P на частичных решениях [13, c.321-322; 46, c.66-75]:

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

Ниже на некотором паскалеподобном псевдокоде приведены три схемы решения задач методом перебора с возвратом: нерекурсивный вариант поиска всех решений (схема 1), рекурсивный вариант поиска всех решений (схема 2), рекурсивный вариант поиска одного решения (схема 3).

По схеме 1 находятся все решения задачи, если они есть, и работа завершается при j=0. Её рекурсивный вариант, представленный на схеме 2, существенно более прост и очевиден.

Схема 1. Нерекурсивный вариант схемы перебора с возвратом для нахождения всех решений

Генерирование всех решений по схеме 2, если они есть, организуется вызовом backtracking(0). Нахождение одного решения по схеме 3, если оно есть, проводится вызовом: backtracking(0,’решение не найдено’). Обратите внимание, что в схемах 2 и 3 возврат не появляется в явном виде, будучи естественной частью реализации механизма рекурсии.

Схема 2. Рекурсивный вариант схемы перебора с возвратом для нахождения всех решений

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

В последующих разделах рассматриваются конкретные задачи, решаемые методом перебора с возвратом. Заметим, что в общем случае этот метод приводит к алгоритмам с экспоненциальной временной сложностью, а применяется он в основном к классу так называемых Np-полных задач (задача коммивояжера, задача о рюкзаке и т. д.) [49, c.439-463; 26, с.346-347]. Задачи этого класса эквивалентны друг другу в том смысле, что все они разрешимы недетерминированными алгоритмами полиномиальной сложности. Далее, для них известно, что либо все они разрешимы, либо ни одна из них не разрешима детерминированными алгоритмами полиномиальной сложности. Иными словами, если хотя бы для одной из этих задач не существует детерминированного алгоритма, имеющего в худшем случае полиномиальную трудоемкость, то такие алгоритмы не должны существовать и для остальных задач этого класса. Наоборот, если хотя бы для одной из этих задач удалось найти детерминированный алгоритм, имеющий в худшем случае полиномиальную трудоемкость, то подобные алгоритмы существовали бы и для остальных задач этого класса и, более того, их можно было бы построить.

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

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

Home Содержание Схемы ООД Доска объявлений Поиск