Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Перебор возможных решений




Во многих задачах из различных областей знания ставятся вопросы-задания типа: “Сколько существует способов …”, “Подсчитайте количество элементов …”, “Перечислите все возможные варианты …”, “Есть ли способ …”, “Существует ли объект…” и т. п. Ответы на них, как правило, требуют исчерпывающего поиска в некотором множестве M всех возможных вариантов, среди которых находятся решения конкретной задачи. Существуют два общих метода организации исчерпывающего поиска: перебор с возвратом (backtracking) и его естественное логическое дополнение - метод решета.

Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать как можно раньше и как можно больше заведомо неподходящих вариантов M. Незначительные модификации метода перебора с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ (branch and bound), поиск в глубину (depth first search), метод проб и ошибок и т. д. Перебор с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания. Он находит применение при решении различных комбинаторных задач в области искусственного интеллекта.

При использовании метода решета вместо конструктивного построения решений задачи из множества возможных вариантов M исключаются все элементы, не являющиеся решениями. Методы решета нашли широкое применение в теоретико-числовых задачах.

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

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

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

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

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

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

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

Общий метод решения приведенных задач состоит в последовательном покомпонентном наращивании вектора v слева направо, начиная с v 0, и последующих испытаниях его ограничениями 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]. Задачи этого класса эквивалентны друг другу в том смысле, что все они разрешимы недетерминированными алгоритмами полиномиальной сложности. Далее, для них известно, что либо все они разрешимы, либо ни одна из них не разрешима детерминированными алгоритмами полиномиальной сложности. Иными словами, если хотя бы для одной из этих задач не существует детерминированного алгоритма, имеющего в худшем случае полиномиальную трудоемкость, то такие алгоритмы не должны существовать и для остальных задач этого класса. Наоборот, если хотя бы для одной из этих задач удалось найти детерминированный алгоритм, имеющий в худшем случае полиномиальную трудоемкость, то подобные алгоритмы существовали бы и для остальных задач этого класса и, более того, их можно было бы построить.

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

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

Простой и наглядный алгоритм перебора с возвратом реализуется в следующей хорошо известной задаче Гаусса о расстановке ферзей на шахматной доске. Нам удобно формулировать (и решать) эту задачу сразу для доски размером n ´ n (n =1, 2, …). Будем считать, что её строки и столбцы пронумерованы соответственно сверху вниз и слева направо цифрами от 0 до n -1 (см. рис.1 при n =8).

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

Решение. В соответствии с описанной ранее общей схемой 2 алгоритма перебора с возвратом предложенную задачу можно было бы решать по приведенному ниже алгоритму “Все расстановки”. По нему ферзи расставляются последовательно на вертикалях с номерами от нуля и далее. В процессе выполнения предписания возможны снятия ферзей с доски (возвраты).

Рис. 1. Схема использования вспомогательных массивов в задаче 1

Алгоритм “Все расстановки”

1. Полагаем D = Æ, j = 0 (D - множество решений, j - текущий столбец для очередного ферзя).

2. Пытаемся в столбце j продвинуть вниз по вертикали или новый (если столбец j пустой), или уже имеющийся там ферзь на ближайшую допустимую строку. Если это сделать не удалось, то переходим к пункту 4.

3. j j +1. Если j < n -1, то переходим к пункту 2. В противном случае j = n -1, то есть все вертикали уже заняты. Найденное частичное решение запоминаем в множестве D и переходим к пункту 2.

4. j j -1, то есть снимаем ферзь со столбца j и переходим к предыдущему столбцу. Если j ³ 0, то выполняем пункт 2. Иначе вычисления прекращаем. Решения задачи находятся в множестве D, которое, вообще говоря, может быть и пустым.

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

Введем в рассмотрение четыре вспомогательных вектора: pos, ho, dd и du c длинами n, n, 2× n -1 и 2× n -1 соответственно. Использовать их будем следующим образом (см. рис.1):

hoi = 1, если на горизонтали с номером i (i = 0, 1, …, n -1) имеется ферзь, и hoi = 0 - в противном случае;
dus = 1, если на диагонали с номером s (s = 0, 1, …, 2× n -2), идущей слева направо и снизу вверх, имеется ферзь, и dus = 0 - в противном случае;
dds = 1, если на диагонали с номером s (s = 1, 2, …, 2× n -1), идущей слева направо и сверху вниз, имеется ферзь, и dds +1 = 0 - в противном случае;
posj = i, если в позиции (i, j) (i, j = 0, 1, …, n -1) стоит ферзь.

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

В позицию (i, j) можно поставить ферзь, если hoi + dui + j + j + ddn + i - j + i - j = 0.
Поставить ферзь в позицию (i, j) равносильно присваиваниям: hoi := 1, dui + j := 1, ddn + i - j := 1.
Убрать ферзь из позиции (i, j) равносильно присваиваниям: hoi := 0, dui + j := 0, ddn + i - j := 0.

С учетом сказанного достаточно компактный рекурсивный вариант алгоритма решения задачи 1 можно было бы задать следующими двумя функциями:

Дадим краткое описание функций queen () и qu ().

Головная функция queen (n) организует обращение к рекурсивной функции qu (), передавая ей в качестве фактических параметров:

n - размер доски;
ho, du, dd, pos - начальные значения вспомогательных векторов (с нулевыми компонентами);
j = 0 - начальное значение номера столбца текущей позиции (i, j) ферзя;
ot - вспомогательный вектор (с нулевыми компонентами), к которому последовательно будут присоединяться найденные решения.

Возвращает функция queen () матрицу ot, столбцы которой, кроме нулевого, содержат решения задачи. Если (i 0, i 1,..., in -1)T- один из таких столбцов, то решением являются позиции ферзей: (i 0, 0), (i 1, 1),..., (in -1, n -1).

Функция qu () в рекурсивном варианте реализует алгоритм “Все расстановки”. Нелишне отметить, что рекурсия здесь осуществляется по не совсем стандартной схеме. В каждом рекурсивном вызове глубины j делается попытка поместить ферзь в некоторую позицию i столбца j (i, j = 0, 1, …, n -1), а сам вызов соответствует переходу от работы с текущим столбцом к работе со следующим столбцом. При этом в начале вычислений и при переходах к любому последующему рекурсивному вызову параметр i меняется от нуля и далее с шагом, равным единице, пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. При переходах к любому предыдущему рекурсивному вызову параметр i продолжает изменяться от своего текущего на данном уровне значения с шагом, равным единице, также пытаясь принять значение наименьшего номера поля, допустимого для установки ферзя. Если в текущем столбце ферзь установить уже не удается, то создавшуюся ситуацию (позицию) назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему столбцу и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии мы должны считать совокупность всех тупиков. Заметим, что в данном случае элементы базы заранее до вычислений неизвестны.

После установки ферзя в одну из строк i последнего столбца j = n -1 формируется одно из решений задачи. Вычисления прекращаются, когда мы попадаем в тупик при работе со столбцом 0. Полученные решения задачи, если они есть, возвращаются в виде столбцов матрицы ot, начиная от первого и далее.

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

Задача E (n, m, w). На доске размера n ´ m (m = n, n -1,…0) требуется установить m ферзей так, чтобы они не били друг друга. При этом имеются некоторые клетки доски, на которые ферзь заведомо ставить нельзя. Множество этих “запретных” клеток обозначим через w.

Исходная задача есть E (n, n, Æ). Проведем её декомпозицию. Представим доску в виде двух частей: нулевого столбца (A) и оставшейся части (B). Соответственно этому разбиению будем решать задачи E (n, 1, Æ) и E (n, n -1, w). Каждое из n возможных решений i (ферзь установлен в строке i = 0, 1, …, n -1) первой задачи однозначно определяет множество w = w (i) запретных клеток для второй задачи. При этом в w (i) попадают те клетки B, которые в “объединенной” доске бьет ферзь, установленный в строке i доски A. Пусть i зафиксировано и найдено множество d (i) решений второй задачи E (n, n -1, w (i)) для доски B. Тогда расположение ферзя в строке i доски A и любое из полученных решений x Î d (i) на B в совокупности дают различные решения ot (i) исходной задачи E (n, n, Æ). Для получения всех решений этой задачи остается лишь взять объединение по i множеств ot (i): ot = È ot (i).

Контрольные примеры:

1. b:= queen (8), x:= b <1>, y:= b <11>,

x T = [0 4 7 5 2 6 1 3], y T = [1 6 4 7 0 3 5 2];

2. c:= queen (3), cols (c) = 1, то есть решений нет!

Замечание. В функции qu () можно вообще отказаться от использования цикла, организовав рекурсию как по i, так и по j. В этом случае qu () и queen () могли бы выглядеть так:

Обратите внимание на то, как реализована в qu () рекурсия. Во-первых, её глубина равна n 2 - при каждом рекурсивном вызове по j (j = 0, 1, …, n -1) происходит n рекурсивных вызовов по i (i = 0, 1, …, n -1). Поскольку при каждом рекурсивном вызове с фиксированными значениями i и j осуществляется попытка установить ферзь на поле (i, j), то и сами вызовы здесь удобно не нумеровать от 0 до n 2-1, а обозначать упорядоченными парами индексов (i, j).

Другой вариант для функции qu () получится, если поменять местами порядок рекурсивных обращений по i и по j. В этом случае отпадает надобность в снятии меток (предпоследняя строка qu ()). Функция queen () при этом останется прежней. Но решения будут возвращаться в порядке, обратном тому, который был раньше:

Впрочем, для возвращения решений по этому варианту qu () в прежнем порядке достаточно при проведении рекурсии по параметру i менять его не от 0 до n -1, а от n -1 до 0. При этом при обращениях к qu () на месте параметра i в программы необходимо внести такие изменения (в тексте они выделены):

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

Решение. Предложенную задачу можно решать по приведенным в задаче 1 функциям, упростив их следующим образом. Вместо запоминания найденных решений будем подсчитывать в переменной ot их количество. В этом случае становится ненужным и вспомогательный вектор pos для формирования очередного решения. Эта модификация функций qu () и queen () приводит нас соответственно к функциям qun () и queennum ():

Рекурсия в qun () организована точно так же, как и в функции qu ().




Поделиться с друзьями:


Дата добавления: 2015-05-06; Просмотров: 1803; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.043 сек.