Метод полного перебора пример

Метод полного перебора пример

Дисклеймер: для понимания этой статьи требуются начальные знания теории графов, в частности знание поиска в глубину, поиска в ширину и алгоритма Беллмана — Форда.

Введение

Наверняка вы сталкивались с задачами, которые приходилось решать перебором. А если вы занимались олимпиадным программированием, то точно видели NP-полные задачи, которые никто не умеет решать за полиномиальное время. Такими задачами, например, является поиск пути максимальной длины без самопересечений в графе и многим известная игра — судоку, обобщенная на размер . Полный перебор крайне долгий, ведь время его работы растёт экспоненциально относительно размера входных данных. Например, время поиска максимального пути в графе из 15 вершин наивным перебором становится заметным, а при 20 — очень долгим.

В этом посте я расскажу как можно оптимизировать большинство переборов, чтобы они стали работать на порядки быстрее.

Поподробнее про перебор

Пример

Рассмотрим наивное решение задачи о нахождении пути максимальной длины без самопересечений в графе G.

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

Если посмотреть в это решение чуть глубже, то можно увидеть, что по-настоящему был запущен классический поиск в глубину, но на другом графе — графе состояний S. В этом графе вершины задаются маской вершин графа G, принадлежащих текущему пути, и номером последней вершины. Рёбра задаются наличием ребра в графе G между последними вершинами путей и равенством остальной маски.

Большинство переборов можно представить в виде поиска по графу состояний.

А что мы собственно ищем

Переборы бывают трёх типов:

1) Проверка существования.
2) Максимизация/Минимизация на не взвешенном графе.
3) Максимизация/Минимизация на взвешенном графе.

Для решения наивным методом первых двух задач используется поиск в глубину или поиск в ширину, а для третьей — алгоритм Беллмана — Форда по графу состояний S.

А теперь сами оптимизации.

Оптимизация №1: мемоизация, или ленивость

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

Если граф состояний S мал, то нам повезло — можно сделать булевский массив, иначе мемоизацию лучше всего реализовать хеш-таблицей.

Обычно реализовать это не сложно. Нужно добавить 2 строчки: в начале проверять, что нас здесь ещё не было, а в конце записывать, что мы здесь были.

Оптимизация №2: отсечение по ответу

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

Хорошим примером для этой оптимизации является поиск пути максимальной длины без самопересечений в графе G. Эта задача NP-полная.

Допустим, мы находимся в каком-то состоянии s графа S. Если нам, как ни крути, не удастся улучшить результат, то стоит вернуться. Теперь надо научиться это проверять. Например, можно посчитать количество достижимых вершин графа G из последней вершины пути состояния s и прибавить длину уже полученного пути, то полученное число будет верхней границей максимального ответа, достижимого из s. Значит, если оно меньше текущего результата, то можно не запускать перебор из этого состояния.

Если абстрагироваться от конкретной задачи, то надо подобрать такую функцию , чтобы было оценкой ответа достижимого из s, где — это текущий ответ состояния s.

Если функция будет достаточно хорошо отражать реальность, то эта оптимизация может ускорить работу алгоритма на порядки.

Отсечение по ответу, пожалуй, самая важная оптимизация, потому что её используют многие другие оптимизации и методы.

Оптимизация №3: жадность

Жадность — это когда мы хватаем всё самое, на первый взгляд, хорошее. То есть идём по ребру, которое нам показалось перспективней остальных. Проблема в том, что ответ, который находит жадность, необязательно самый хороший, но чем лучше наша оценка, тем лучше результат. За функцию оценки можно взять из отсечения по ответу.

А теперь по порядку.

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

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

Читайте также:  Вьюсоник мониторы официальный сайт

Пара слов про взвешенные графы

Обычно алгоритм Беллмана — Форда пишут примерно так:

А можно его написать немного по-другому: как поиск в ширину, но при проверке на то, посетили ли мы раньше это состояние, сравнивать текущий и мемоизированный, и, если мемоизированный лучше, то отрубать эту ветку перебора.

Чем «плох» поиск в глубину и поиск в ширину

Немного картинок:

Красным выделены множества посещённых состояний графа S после некоторого времени работы поиска в глубину и в ширину соответственно.

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

Если мы решаем задачу минимизации, то действия поиска в ширину выглядят логично, но, к сожалению, он вряд ли получит какой-то ответ для отсечения.

Механизмы выбора области поиска

Жадность

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

Все помнят, что есть число 1 и есть число N, но многие забывают, что есть ещё и числа между ними. Жадность — это выбор одного ребра, а поиск в глубину — выбор N рёбер. Давайте напишем жадный поиск в глубину, который будет переходить по первым k рёбер.

Если использовать этот метод, то перебор будет обходить намного большие поддеревья графа S.

Проблема в том, что если взять слишком маленькое k, то ответ может оказаться неправильным, а если слишком большое, то времени может не хватить. Решение довольно простое: надо выбрать все возможные k. То есть написать внешний цикл, перебирающий k от 1 до бесконечности, пока время не кончилось, а в теле цикла запускать поиск решения.

Здесь стоит понять, что так как количество просмотренных состояний графа S растёт экспоненциально относительно роста k, то перебор этой переменной от 1 до k-1 не будет увеличивать асимптотическую сложность. В худшем случае время работы увеличится не более чем в константу раз, а на практике значительно уменьшится из-за отсечения по хорошему ответу.

Iterative deepening

Этот метод как бы заставляет поиск в глубину выполнять не те задачи, которые он обычно выполняет.

Суть метода заключается в том, чтобы создать глобальную переменную — максимальная глубина, на которую должен спускаться поиск в глубину. Так же как и с k запускаем внешний цикл по этой глубине.

Теперь поиск в глубину больше напоминает поиск в ширину, но с той разницей, что он сразу получает какой-то ответ для отсечения.

Ограничение размера очереди поиска в ширину

Это тоже жадность, но теперь для поиска в ширину. Из названия понятно, что мы будем ограничивать очередь. Для этого опять заведём глобальную переменную — размер очереди и переберём её от 2 до бесконечности. Но перебирать будем не по +1, а умножать на константу, например, на 2.

В какой-то момент размер очереди превысит выбранный максимальный размер и придётся кого-то выбросить за борт. Чтобы выбрать, надо отсортировать по какому-то признаку. Будем использовать, как всегда, функцию для сравнения состояний.

Что из всего этого теперь писать

Для наилучшего результата надо написать почти всё и почти сразу.

Вначале запускаем поиск в глубину на некоторое время с мемоизацией, отсечением по ответу, сортировкой рёбер, и перебором k, но без Iterative deepening.
Далее запускаем поиск в ширину с отсечением по ответу и ограничением размера очереди.

Поиск в глубину нужен, чтобы найти неплохой ответ для отсечения в поиске в ширину, а поиск в ширину нужен, чтобы найти уже наилучший ответ. Эта сборная солянка неплохо показывает себя во многих задачах на перебор.

Теперь немного практики

Поиск максимального пути без самопересечений в графе

Случайный граф: 18 вершин, 54 ребра.
Время работы:
Нет оптимизаций

4 сек.
Мемоизация, отсечение по ответу

Случайный граф: 30 вершин, 90 рёбер.
Нет оптимизаций > 1 часа (не дождался).
Мемоизация, отсечение по ответу

0.5 с.
Мемоизация, отсечение по ответу, жадность

Данная статья открывает цикл работ, посвященных не особенностям какого-то отдельного языка программирования (например Паскаля), а общим ИДЕЯМ и МЕТОДАМ разработки алгоритмов. Тем не менее, опираться мы все равно будем на теория, числа, оптимальные алгоритмы, вычислительная, определение, который вы уже знаете. Первоначальный вариант любого алгоритма мы будем записывать на псевдокоде — языке, который занимает промежуточное положение между нашим обычным языком и языками программирования. Он не имеет каких-то жестких правил и требований, т.к. предназначен прежде всего для человека, а не компьютера. Это позволит нам избавиться от излишней детализации алгоритма на раннем этапе разработки и сразу выразить его основную идею. Превратить этот псевдокод в программу на Паскале задача совсем несложная — как это делать вы быстро поймете.

Читайте также:  Мини пк на windows нового поколения

Основные идеи первого задания — ПЕРЕБОР, РЕКУРСИЯ, ПЕРЕБОР С ОТХОДОМ HАЗАД. Этими понятиями должен хорошо владеть каждый программист. Кроме того, переборные задачи составляют значительную долю всех школьных олимпиад по информатике.


1. Порождение и перебор комбинаторных объектов

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов — последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

    — во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

— во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1 1.1. Последовательности

Hапечатать все последовательности длины N из чисел 1,2. M.

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:

Теперь можно написать общую процедуру Next:

Если такого i найти не удается, то следующей последовательности нет — мы добрались до последней (M,M. M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

1.2. Перестановки

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

Всего таких перестановок будет N!=N*(N-1)*. *2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i] . >X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1]. X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1. N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

Теперь можно написать программу:

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1 1.4. Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) — число всех k-элементных подмножеств n-элементного множества — можно найти, заполняя таблицу значений функции С по формулам:

C(n,0) = C(n,n) = 1 (n>=1) C(n,k) = C(n-1,k-1) + C(n-1,k) (n>1, 0 =0, k>=0) число разбие- ний N на целые положительные слагаемые, не превосходящие k (при этом R(0,k) считаем равным 1 для всех k>=0). Очевидно, что число R(N,N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).

Число R(N,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i
2. Рекурсия

Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:

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

Примечание сайта: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium — III+. Из-за времени выполнения. О том, как этого избежать, можно прочитать в статье Динамическое программирование.

2.1. Факториал

Еще раз напомним рекурсивный алгоритм вычисления факториала:


2.2. Ханойская башня

Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.

Читайте также:  Gtx 650 1gb драйвера для виндовс 7

Hапишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:

Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:

Если вы владеете основами компьютерной графики, можете попробовать "нарисовать" каждый ход на экране.

Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения — свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова — иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, "безрекурсивное" решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.


2.3. Последовательности (рекурсивный алгоритм)

Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1. M, у которых фиксировано начало X[1],X[2]. X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность — это она сама. При k
2.4. Перестановки (рекурсивный алгоритм)

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1. N, у которых фиксировано начало X[1],X[2]. X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение — саму перестановку. При k Основная программа:

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!

Как вы уже поняли, перебор комбинаторных объектов — задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 — число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7. рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1]. X[k] уже не нужно — следует вернуться к X[k] и изменить его значение ("отойти назад" — отсюда название метода).

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

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1]. X[k] (k

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

Сложность заключается в том, что с увеличением количества исходных данных (при переходе от к ) быстро увеличивается необходимое число проверок. Метод полного перебора применим в тех случаях, когда искомое решение принадлежит некоторой конечной области и может быть найдена простая функция quality (Y) для проверки правильности (или качества) выбранного решения. Тогда задача Р вычисления функции заменяется многократным решением задачи R вычисления функции quality (столько раз, сколько элементов имеется в области решений). Причем в общем случае просмотреть нужно всю область, и порядок, в котором просматриваются элементы, не важен.

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

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

Часто не удается разбить задачу на небольшое число подзадач, объединенное решение которых позволяет получить решение искомых задач. Можно попытаться разделить задачу на столько задач, сколько необходимо, затем каждую на еще более мелкие и т.д. Иногда проще создать таблицу решения всех подзадач, независимо от того нужна она или нет. Заполнение таблиц – решение подзадач для получения решения определенной задачи – в теории алгоритмов получило название динамического программирования. Формы алгоритмов динамического программирования могут быть разными, общими могут быть лишь заполненные таблицы и порядок заполнения ее элементов.

Ссылка на основную публикацию
Мегафон опции за рубежом
Всем абонентам мобильной связи известно, что оплата услуг в роуминге достаточно высокая. Кроме того, нужно платить за входящие звонки. И...
Люстра с пультом управления светодиодная инструкция
Идея установить и подключить люстру с пультом замечательна тем, что хозяева квартиры получают возможность управлять освещением, не привязываясь к выключателю....
Ля рош позе скидки
12 актуальных предложений март 2020 Сэкономьте 10% с промокодом при покупке более 3000 рублей Приобретите в интернет-магазине La Roche Posay...
Мегафон отправить деньги с телефона на телефон
Каждый клиент компании Мегафон при необходимости может со своего счёта пополнить баланс близкого, который также пользуется услугами данного оператора. Для...
Adblock detector