Метод перебора

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

Рассмотрим несколько примеров применения метода перебора в решении различных задач.

Допустим, нам встретилась последовательность цифр 141526418, и мы знаем, что в ней зашифровано латинскими буквами некое слово. Какой самый простой способ зашифровать слово? Конечно же, использовать шифр замены A1Z26!

Число цифр нечётное, значит хотя бы одна буква закодирована всего одной цифрой. Но как отделить буквы первой десятки от последующих, кодируемых двумя цифрами? 14 - это AD или N? Вот тут-то нам и пригодится метод перебора. Переберём все комбинации из одной-двух цифр из диапазона [1-26].

В последовательности 141526418 можно выделить следующие удовлетворяющие нашим условиям комбинации: 1,2,4,5,6,8,14,15,18,26. Эти числа соответствуют буквам A,B,D,E,F,H,N,O,R,Z. Комбинации 41, 52 и 64 нам не подходят, так как в латинице всего 26 букв.

Перебирать будем так: сначала возьмём самую развёрнутую последовательность, где все буквы из первого десятка, а затем будем по очереди увеличивать используемые числа, то есть заменять последовательности 1-4 на 14, 1-5 на 15, 1-8 на 18, 2-6 на 26, перебирая все возможные комбинации в стиле двоичной системы.

Итого получили 16 вариантов. Единственное читаемое слово NOZDR (кому читаемое, а кому и нет ), получилось в самом конце. Оно и будет ответом. Вот если бы в самом начале была подсказка, что из последовательности 141526418 должно получиться 5 букв, то тогда задача решится однозначно. И перебор будет не нужен, потому что разбить на 5 букв последовательность 141526418 можно только одним единственным способом. Но такой подсказки не было, и метод перебора пригодился.

Правда, если бы мы начали наоборот – не с самой развёрнутой комбинации, а со свёрнутой, – то на первом же шаге и нашли ответ. Но, по закону Мерфи, или как его у нас называют, «закону подлости», нужная вещь всегда находится в последнем кармане.

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

Учитель на уроке математики задал ученикам такую задачу: «У матери три дочери. Произведение возрастов дочерей = 40, сумма возрастов равна числу учеников в классе. Каков возраст каждой из дочерей?» Ну, ученики по-быстрому посчитали, сколько их всего в классе, и стали решать задачу. Решали-решали… Не решается. Попросили у учителя подсказку. Учитель подумал и говорит: «А, точно! У младшенькой голубенькие глазки!». Ученики обрадовались, и решили задачу. А теперь вопрос вам: сколько же лет каждой из дочерей?

Если решать задачу в лоб (AxBxC=40, A+B+C=M, голубенькие глазки), то сразу наталкиваешься на кучу неизвестных и недостаток условий. 4 неизвестных, два уравнения и ещё голубенькие глазки!!! Как известно, сколько неизвестных, столько должно быть и независимых условий. У нас в задаче два нормальных условия и одно непонятное. Как же её решать?

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

Если бы учеников в классе было 42, 23, 15 или 11, то они бы сразу решили задачу, потому что это было бы единственное решение. Но у них возникло затруднение – их было 14, и они никак не могли выбрать, какой же из вариантов 1-5-8 или 2-2-10 подходит. Но когда учитель сказал про голубые глазки, им это помогло определиться. Голубые глазки были у младшенькой, то есть была самая младшая дочь, а в варианте 2-2-10 младшеньких две. Значит, нам подходит только четвёртый вариант 1-5-8.

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

(Интересно, куда смотрят ученики на картинке выше и что они там увидели?)

В ЕГЭ по информатике однажды встретилась такая задача:

Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22?

Ну первая мысль, конечно, выписать все числа от 1 до 26 в десятичной системе, перевести их в троичную и посмотреть, какие из них заканчиваются на 22. Как обычно, нужно делить число на 3, пока делится, а затем задом-наперёд выписывать остатки. И так для каждого из 26 чисел. Не, ну можно, конечно, не считать, а просто последовательно выписывать эти числа в троичной системе, по порядку же надо:

• `1_10 = 1_3`
• `2_10 = 2_3`
• `3_10 = 10_3`
• `4_10 = 11_3`
• `5_10 = 12_3`
• `6_10 = 20_3`
• `7_10 = 21_3`
• `8_10 = 22_3` ← подходит
• `9_10 = 100_3`
• `10_10 = 101_3`
• … и так ещё для 16 чисел

Но немного проще сделать по-другому. Какие числа в троичной системе заканчиваются на 22?

• `22_3, 122_3, 222_3, 1022_3…`

Причём мы знаем (должны знать), что тремя троичными цифрами 0,1,2 можно записать не больше `3^3=27` чисел, начиная с нуля. Значит, `1022_3` и последующие нам уже не подойдут, потому что в них больше трёх цифр. Переведём наши первые три числа в десятичную систему:

• `22_3=2*3+2=8_10`
• `122_3=1*3^2+2*3+2=17_10`
• `222_3=2*3^2+2*3+2=26_10`

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

Ответ: 8, 17, 26.

Так что перебор-перебором, но и при переборе важно включать мозги, чтобы по возможности уменьшать число перебираемых значений. А почему это важно (уменьшать число перебираемых вариантов), я напишу чуть ниже.

Это одна из самых известных головоломок в информатике и математике. Звучит она так: «Выберите подмножество предметов максимальной стоимости, чтобы их суммарный вес не превысил заданный лимит».

Представьте, что вы собираетесь в поход. У вас есть рюкзак, который выдерживает максимум 15 кг. Вы видите набор предметов, каждый со своим весом и своей ценностью (например, палатка, котелок, еда, аптечка). Вопрос: Какой набор предметов нужно положить в рюкзак, чтобы общая ценность (полезность) была максимальной, но общий вес не превысил 15 кг?

• Предмет А: вес 1 кг, ценность 5₽
• Предмет Б: вес 2 кг, ценность 20₽
• Предмет В: вес 4 кг, ценность 30₽
• Предмет Г: вес 12 кг, ценность 50₽

Решим задачу перебором всех вариантов. Для каждого варианта посчитаем его вес и ценность. Из 4-х вещей можно получить всего 2⁴=16 различных комбинаций, которые легко перебрать, применяя двоичную систему счисления. Пустую комбинацию отбрасываем (зачем нам пустой рюкзак?), остаётся 15:

Начинаем смотреть снизу, т.к. там самые ценные варианты. Нижние 4 нам не подходят, потому что больше 15 кг. Значит, «наш» вариант – это 11-й вариант (ГБА) ровно на 15 кг и стоимостью 75₽. Вроде бы легко решили. Можно было даже в уме решать, причём сразу снизу, и быстро бы нашли нужное решение. Но суть в том, что перебор всех вариантов в уме нормально работает только для небольшого числа предметов. А если предметов 10? а если 100?

Задача о рюкзаке относится к классу так называемых NP-полных задач. Это значит, что на сегодняшний день не существует быстрого алгоритма, который решал бы её для любого количества предметов за разумное (полиномиальное) время. Единственный гарантированный способ найти оптимальный набор — это перебрать все возможные комбинации предметов. К сожалению, время, за которое методом полного перебора можно найти все решения, растёт экспоненциально из-за того, что число возможных комбинаций растёт точно так же.

• Для 4 предметов — 16 комбинаций.
• Для 10 предметов — 1024 комбинации.
• Для 100 предметов — это 2¹⁰⁰ комбинаций. Это число больше, чем атомов во Вселенной. Такой перебор на самом мощном компьютере занял бы миллиарды лет.

Полиномиально – это значит, что время нахождения всех вариантов зависит от числа предметов в виде некоторого полинома (многочлена), график которого растёт не так быстро, как экспонента. Поэтому «полиномиальное время» является для алгоритмов синонимом понятий «легко поддающийся обработке», «выполнимый», «эффективный» или «быстрый».

Различают два вида задачи о рюкзаке:

• А) Дробная задача (не сложная). Вы можете взять часть предмета (например, полпачки сахара или кусок золота). Тогда решение простое: нужно брать самые «выгодные» по плотности предметы (цена за 1 кг) до заполнения рюкзака. Решается жадным алгоритмом за пару секунд.
• Б) Целочисленная (самая сложная). Предмет либо берется целиком, либо не берется вообще (палатку пополам не разрежешь). Именно тут и начинаются сложности.

Есть такая интересная система счисления – унарная (единичная). Если числа подавать в унарной системе, то задача внезапно становится легкой. Вот как это работает: Допустим, вес рюкзака 15 кг. В унарной системе мы просто создаем «шкалу» длиной в 15 палочек: |||||||||||||||. Алгоритм работает так: мы идём по предметам и для каждой клеточки (1 кг) решаем, класть ли этот предмет. Время работы алгоритма зависит от числа (15), а не от количества цифр в записи числа (в двоичной системе 15 — это 1111, всего 4 знака).

Если число 15 записано как 1111 (бинарно) — алгоритм работает экспоненциально (плохо). Если число 15 записано как ||||||||||||||| (унарно) — алгоритм работает полиномиально (хорошо). Но проблема в том, что число 1 000 000 в унарной системе займет 1 миллион символов. И хотя алгоритм будет работать быстро, но это будет очень неэффективно по памяти, т.к. она не бесконечна. И получается, что в общем виде эту задачу быстро и дёшево решить невозможно. Как говорится, из «точно, быстро и дёшево» выбирайте любые два. Поэтому программисты используют разные трюки, и находят не точное, но «почти оптимальное» для решения число другими более быстрыми и не требующими много памяти алгоритмами.

Не думайте, что задача про рюкзак из серии занимательной математики. Её решение является основой для:

• Раскроя материалов: Как максимально выгодно нарезать листы металла или ткани, чтобы получить детали и осталось меньше отходов.
• Загрузки контейнеров/самолетов: Как разместить груз разного веса и объёма, чтобы заработать максимум денег.
• Криптографии (исторически): В 1970-х годах на основе этой задачи даже пытались строить шифры (система Меркла-Хеллмана). Правда, их потом взломали, но идея была красивой: злоумышленник не может подобрать набор предметов, дающих нужный вес, если предметов много.
• Финансового портфеля: Как распределить бюджет между разными акциями (купить целиком пакет или нет), чтобы максимизировать прибыль при ограниченном капитале.

В общем, к чему я написал столько буков? Если число предметов небольшое, то будет небольшим и число комбинаций, а значит метод перебора будет оптимальным и по скорости и по памяти, поэтому забывать про него при решении задач не стоит :)

Методом перебора можно решать не только комбинаторные и математические задачи, но и логические. Например, вот такая задача с картинки ниже:

У нас всего три пришельца, обозначим их: А – альфацентаврианин, B – барнардец, С – сириусянин.

А ещё у нас есть три высказывания представителей прессы: «А – со щупальцами», «B – лысый», «С – на ногах».

Число возможных перестановок из A, B и C = 3! = 6. Вот они: ABC, ACB, BAC, BCA, CAB, CBA. Перестановка ABC означает, что слева альфацентаврианин, в середине – барнардец, а справа – сириусянин.

Составим таблицу, по вертикали отложим все наши возможные перестановки, а по горизонтали – высказывания. На пересечении будем по очереди проверять для каждой перестановки истинность высказываний и указывать, истинно это утверждение (+) или ложно (-).

Проанализиуем все 6 комбинаций, и увидим, что одно из трёх высказываний истинно только для комбинации BAC. Значит, слева у нас зелёный барнардианец, в центре кучерявый альфацентаврианец, а справа – фиолетовый осьминог-сириусянин.

Обычно большое число возможных вариантов останавливает применение метода перебора при решении задач «на бумаге». В приведённых выше задачах нам просто повезло, что вариантов было не так много. А если бы их было сто или сто тысяч?

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

Тем не менее, зачастую написание программы перебора всех вариантов – это единственный способ точного и полного решения задачи. Например, поиск числа Бога – минимального числа поворотов, за которое можно собрать кубик Рубика из любого положения – был осуществлён именно перебором всех возможных 43 252 003 274 489 856 000 комбинаций Кубика.

Как решались все 43 252 003 274 489 856 000 позиций Куба? Конечно же, сначала были сделаны некоторые действия, уменьшающие общее число переборов:

1. все позиции были разделены на 2 217 093 120 наборов по 19 508 428 800 «похожих» позиций в каждом
2. число наборов, которые надо было решить, сократили до 55 882 296, используя симметрию и покрытие множеств
3. искались не оптимальные решения, только решения длины 20 или меньше (полный перебор на самом деле делался не всегда)
4. была написана программа, которая решала одну задачу примерно за 20 секунд

Выходит, обсчитывалось всего 55 882 296 вариантов, тем не менее на это было затрачено 35 лет компьютерного времени компании Гугл. Конечно, реально никто не ждал 35 лет, пока компьютер что-то посчитает. Это просто такая единица измерения. Как расстояние между звёздами измеряется в световых годах, так и время, потраченное на расчёты, считается в CPU-годах.

• 1 световой год – это расстояние, которое свет, летящий со скоростью 299 792 458 м/с, преодолеет за один год
• 1 год процессорного времени – это число операций, которые выполнит компьютер с производительностью 1 гигафлопс (то есть миллиард операций с плавающей точкой в секунду) за один год

Если попробовать посчитать, сколько это – 1 CPU-год, то получится ~ 365,25 дней в году * 24 часа в сутках * 60 минут в часе * 60 секунд в минуте * 1 000 000 000 операций в секунду = 31 557 600 000 000 000 операций.

В общем, 35 лет компьютерного времени – это много. Мой компьютер имеет производительность ~50 Гфлопс (это в теории, на самом деле меньше), и ему бы понадобилось `(35:50)*365,25 ~= 255 ` суток непрерывных расчётов. Но если алгоритм позволяет распараллелиться, и решение одной и той же задачи можно разделить между несколькими (например, 10000-ми) компьютерами с такой же производительностью, то 35 лет может «свернуться» до `(35:50*365,25*24*60):10000 ~= 36,8 ` минут. Вопрос – где взять эти 10000 компьютеров, кроме как у Гугла?

В общем, учитесь программировать – тогда вам покорятся не только метод перебора, но и множество других интересных алгоритмов! И может быть даже не придётся арендовать кучу дорогого компьютерного времени у дата-центров.