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

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

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

Допустим, нам встретилась последовательность цифр 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, перебирая все возможные комбинации.

1. 1-4-1-5-2-6-4-1-8 = ADAEBFDAH
2. 1-4-1-5-2-6-4-18 = ADAEBFDR
3. 1-4-1-5-26-4-1-8 = ADAEZDAH
4. 1-4-1-5-26-4-18 = ADAEZDR
5. 1-4-15-2-6-4-1-8 = ADOBFDAH
6. 1-4-15-2-6-4-18 = ADOBFDR
7. 1-4-15-26-4-1-8 = ADOZDAH
8. 1-4-15-26-4-18 = ADOZDR
9. 14-1-5-2-6-4-1-8 = NAEBFDAH
10. 14-1-5-2-6-4-18 = NAEBFDR
11. 14-1-5-26-4-1-8 = NAEZDAH
12. 14-1-5-26-4-18 = NAEZDR
13. 14-15-2-6-4-1-8 = NOBFDAH
14. 14-15-2-6-4-18 = NOBFDR
15. 14-15-26-4-1-8 = NOZDAH
16. 14-15-26-4-18 = NOZDR

Итого получили 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.

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

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

У нас всего три пришельца, обозначим их: А – альфацентаврианин, 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 лет компьютерного времени – это много. Мой компьютер имеет производительность ~100Гфлопс, то есть ему бы понадобилось `35/100*365,25 ~= 128 ` суток непрерывных расчётов. Но если алгоритм позволяет распараллелиться, и решение одной и той же задачи можно разделить между несколькими (например, 10000-ми) компьютерами с такой же производительностью, то 35 лет может «свернуться» до `(35/100*365,25*24*60)/10000 ~= 18,5 ` минут. Вопрос – где взять эти 10000 компьютеров, кроме как у Гугла?

В общем, учитесь программировать!