Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2021-03-17 | 103 |
5.00
из
|
Заказать работу |
|
|
Описываемая в данном разделе техника перебора лежит за пределами того, что используется в олимпиадных задачах. Она используется при решении серьёзных промышленных задач, в которых объём перебора очень велик и важно максимально ускорить решение задачи. Последние сорок лет на исследование перебора с распостранением ограничений были потрачены усилия многих учёных.
Итак, техника перебора с распостранением ограничений слишком сложна для олимпиад. Однако мы подошли к ней слишком близко, чтобы избежать соблазна и не рассмотреть её. Тем более, что описание перебора с распостранением ограничений на русском языке найти очень трудно (единственный источник, изданный массовым тиражом – [1]).
Распостранение ограничений
Вернёмся к задаче о ферзях при n= 3. После расстановке первого ферзя на первом поле пространство перебора можно сократить не только до показаного на рисунке 3, а до одного элемента: x 2=3, x 3=2. Действительно, если x 1 = 1, то x 2 ¹ 1, x 2 ¹ 2, x 3 ¹ 1, x 3 ¹ 3.
Как реализовать полностью такое сокращение пространства перебора при выборе очередного ферзя? Для этого надо представлять пространство перебора в памяти. Таким представлением могут быть массивы различных положений для каждого ферзя (как показано на рис. 4,5,6). Вместе такие массивы как бы ``образуют доску''. Если ферзя можно поставить на данное поле, то в соответствующем элементе массива должен быть записан 0.
При каждом выборе ферзя можно ``удалять'' с ``доски'' те ``поля'', на которые нельзя поставить ферзей, т.е. записывать в соответсвующий элемент не 0.
При этом надо помнить, что при возврате мы все изменения элементов должны восстановить. Как это сделать? Как узнать какие именно изменения были сделаны после того уровня перебора, к которому мы возвращаемся? Возможное решение – исправлять 0 на номер шага! Тогда, если мы возвращаемся к шагу с номером m, то должны восстановить (превратить в 0) все те ``поля'', значения которых больше или равны m.
|
Такое изменение алгоритма оказывается не столь существенным, как можно было ожидать. Действительно, порядок перебора (а, значит, и его объем) остаётся по существу тем же самым. Удешевляется (точнее, делается на более раннем этапе) лишь проверка возможности очередного выбора.
Однако такое изменение позволяет реализовать ещё одно улучшение алгоритма, которое мы описываем в следующем подразделе.
Изменение порядка перебора
Рассмотрим снова пространство перебора для задачи об n ферзях. Пусть перебор ещё не закончен и пространство перебора сузилось до множества из декартова произведения множеств Ym+ 1 ,...,Yn. Понятно, что порядок перебора элементов в этом множестве мы можем выбирать произвольно. Иначе говоря, мы можем делить это пространство на слои по любой из координат. Это означает, что не обязательно перебирать сначала очередного ферзя, а потом остальных – порядок ферзей может быть произвольным.
Рассмотрим первые шаги перебора для n= 8. Первый ферзь будет поставлен на первое поле, второй – на третье, третий – на пятое (см. рисунок 7).
Если мы будем перебирать положения для четвёртого ферзя, то нам придётся перебрать по крайней мере три варианта. Однако мы видим, что для шестого ферзя осталось только одно положение. Если вместо расстановки четвёртого ферзя поставить шестого, пространство перебора ещё более сузится (см. рисунок 5). Теперь всего один вариант для восьмого ферзя, потом – для четвёртого и для пятого. Для седьмого ферзя не остаётся ни одного варианта. (см. рисунок 8). Таким образом, мы можем отвергнуть все варианты расстановок (те, которые могут получиться после расстановки первых трёх ферзей как на рисунке 1) практически без перебора. Это благодаря тому, что мы поменяли порядок расстановки ферзей.
|
Можно сформулировать общий принцип оптимального выбора порядка перебора. Из пространства перебора Xk ´...´ Xl как правило лучше выбирать координату i, такую, что Xi имеет самый малый размер (количество элементов). Понятно, почему это так в случае, если этот размер равен 0 – это означает, что уже не осталось вариантов – перебор зашёл в тупик – естественно, нам лучше это заметить как можно раньше. Понятно, почему это так, если размер Xi равен 1. Объясним, почему этот принцип остаётся справедливым и при большем размере.
Чем меньше вариантов выбора очередного ферзя мы рассматриваем, тем большие группы вариантов попадают в каждый такой вариант. А значит, сокращение пространства перебора будет происходить для большей группы за один раз. Это означает в конечном счёте меньший объём перебора.
Запишем алгоритм, реализующий этот принцип. Для хранения номеров ещё не расставенных ферзей и для записи того, какой ферзь перебирается на очередном шаге используется массивна_шаге. Переменная m содержит номер шага, переменная qm – номер перебираемого ферзя. Процедуры сократить_пространство_перебора и восстановить_пространство_перебора должны быть изменены. Кроме изменения пространства перебора они должны еще пересчитывать количество возможных положений для каждого ферзя, которое хранится в массиве кол_вариантов.
procedure просмотр_вперёд(m: integer); var i, qm: integer; if m > n then <найдено решение> else begin { выбирается ферзь с наименьшим количеством вариантов } minq:= n+1; for i:= m to n do if кол_вариантов[на_шаге[i]] < minq then begin l:= i; qm:= на_шаге[l]; minq:= кол_вариантов[qm]; end; на_шаге[l]:= на_шаге[m]; на_шаге[m]:= qm; for i:= 1 to n do if пространство[qm,i] = 0 then begin ферзь[qm]:= i; сократить_пространство_перебора(qm,i,m); просмотр_вперёд(m+1); восстановить_пространство_перебора(qm,i,m); end; end;Технология такого варианта перебора называется ``просмотром вперёд'' (forward checking).
|
В заключение небольшая таблица, показывающая время решения (в сотых долях секунды) задачи об n ферзях для алгоритма перебора с возвратом и перебора с распостранением ограничений и просмотром вперёд.
n | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
перебор с возвратом | 6 | 33 | 154 | 851 | 5174 | 33010 | 420397 |
распостранение ограничений | 3 | 16 | 60 | 280 | 1368 | 7272 | 41507 |
Задачи
Задача 8. В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются верёвочками так, чтобы выполнялись следующие условия:
Написать программу, которая связывает пары гвоздей верёвочками как описано выше.
Технические требования: Входными данными являются число гвоздей и их координаты, выходными – минимальная суммарная длина и пары соединений гвоздей.
Замечание. Задача решается без перебора.
Задача 9. Квадрат размером 5´ 5 вдоль линий сетки разбили на несколько фигурок. Написать программу, которая определяет, можно ли переложить часть фигурок так, чтобы снова образовался квадрат размером 5´ 5. При перекладывании не разрешается поворачивать и переворачивать фигурки.
Технические требования: Входные данные – символьная матрица размером 5´ 5. Каждая буква в матрице означает идентификатор фигурки, содержащей соответствующую клетку. Идентификаторами являются большие буквы латинского алфавита. Программа должна выдать другой способ составления квадрата размером 5´ 5, либо сообщение, что это невозможно.
Замечание. Это стандартная переборная задача. Решается с помощью перебора с возвратом (можно использовать распостранение ограничений).
Задача 10. В океане расположен архипелаг из N островов, каждый из которых имеет форму многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.
|
Технические требования: Входными данными являются число островов в архипелаге (N) и N описаний островов. Каждый остров задаётся числом вершин и их координатами в порядке обхода по часовой стрелке. Программа должна вывести два числа – количество мостов и их суммарную длину.
Замечание. Задача решается без перебора.
Задача 11 Разбиение. Массив натуральных чисел A (A 1 ,...,An) разбить на два непересекающиеся массива B и C (то есть каждый элемент массива A должен попасть точно в один из двух массивов: B или C), так, чтобы сумма чисел в B равнялась сумме чисел в C.
Технические требования: Входными данными являются количество чисел (n) и последовательность из n чисел. Программа должна вывести два массива чисел B и C.
Замечание. Задача схожа с задачей о рюкзаке и решается перебором с возвратом. Можно использовать распостранение ограничений. Перед перебором имеет смысл упорядочить массив A по невозрастанию.
Тексты программ на Паскале
{ Программа решения задачи об n ферзях перебором с возвратом } program BacktrackQueens; var n: integer; { размер доски } queen: array[1..100] of integer; { массив положений ферзей } { Процедура печати решения } procedure WriteSolution; var i: integer; begin for i:= 1 to n do Write(queen[i],' '); WriteLn end; { Функция проверки совместимости m -го ферзя с предыдущими } function Check(m: integer): boolean; var i: integer; begin for i:= 1 to m-1 do if (queen[i] = queen[m]) { совпадают горизонтали } Or (i+queen[i] = m+queen[m]) { нисходящие диагонали } Or (i-queen[i] = m-queen[m]) { восходящие диагонали } then begin Check:= False; Exit; end; Check:= True; end; { Процедура, осуществляющая перебор } procedure Backtrack(m: integer); var i: integer; begin if m > n then { найдено решение } WriteSolution else for i:= 1 to n do begin queen[m]:= i; if Check(m) { m-ый ферзь не бьёт предыдущих } then Backtrack(m+1); end; end; begin Write('Размер доски? '); Read(n); Backtrack(1) end. { Программа решения задачи об n ферзях перебором с распостранением ограничений и просмотром вперёд } program PropagateQueens; var n: integer; { размер доски } queen: array[1..160] of integer; { массив положений ферзей } space: array[1..160,1..160] of integer;{пространство перебора} step: array[1..160] of integer; { порядок выбора ферзей } cases: array[1..160] of integer; { количество вариантов } { Процедура печати решения } procedure WriteSolution; var i: integer; begin for i:= 1 to n do Write(queen[i],' '); WriteLn end; { Процедура сокращения пространства перебора } procedure Prune(qm,queen,m: integer); var i, nq: integer; procedure ExcludeField(queen: integer); begin if (queen >= 1) and (queen <= n) then if space[nq,queen]:= 0 then begin Dec(cases[nq]); space[nq,queen]:= m; end; end; begin for i:= m+1 to n do begin nq:= step[i]; ExcludeField(queen); { на той же горизонтали } ExcludeField(queen+nq-qm); { на той же диагонали } ExcludeField(queen-nq+qm); end; end; { Процедура восстановления пространства перебора } procedure Restore(qm,queen,m: integer); var i, nq: integer; procedure IncludeField(queen: integer); begin if (queen >= 1) and (queen <= n) then if space[nq,queen] = m then begin Inc(cases[nq]); space[nq,queen] = 0; end; end; begin for i:= m+1 to n do begin nq:= step[i]; IncludeField(queen); { на той же горизонтали } IncludeField(queen+nq-qm); { на той же диагонали } IncludeField(queen-nq+qm); end; end; var minq, l: integer; procedure Propagate(m: integer); var i, qm: integer; begin if m > n then WriteSolution else begin { Выбирается ферзь с наименьшим количеством вариантов } minq:= n+1; for i:= m to n do if cases[step[i]] <= minq then begin l:= i; qm:= step[l]; minq:= cases[qm]; end; step[l]:= step[m]; step[m]:= qm; for i:= 1 to n do if space[qm,i] = 0 then begin queen[qm]:= i; Prune(qm,i,m); Propagate(m+1); Restore(qm,i,m); end; end; end; var i, j: integer; begin Write('Размер доски? '); Read(n); for i:= 1 to n do begin for j:= 1 to n do space[i,j]:= 0; step[i]:= i; cases[i]:= n; end; Propagate(1) end.
|
|
|
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!