7.1. Элементарные примеры

Я тут долго думал, стоит сначала объяснять общую идею или все-таки сначала пример разбирать. Буду сначала пример, так, наверное, понятнее.

7.1.1. Перебор всех \(2^k\) двоичных чисел из \(k\) разрядов

Примечание

Это, пожалуй, единственный пример, когда в некоторых случаях имеет смысл писать прямой перебор. Действительно, перебрать все \(k\)-значные двоичные числа можно легко: for i in range(1 << k): — и \(i\) пробежит все \(k\)-значные двоичные числа. Это бывает полезно, например, в динамике по подмножествам или динамике по профилю, но нередко бывает полезнее рекурсивный перебор, который мы и будем тут разбирать.

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

Пусть нам надо, например, вывести на экран все \(k\)-значные двоичные числа (их всего, очевидно, \(2^k\)). Напишем следующую программу

def check(a):
    print(*a)

def find(i):
    if i == k:
        check(a)
        return
    a[i] = 0
    find(i + 1)
    a[i] = 1
    find(i + 1)

k = int(input())
a = [None] * k
find(0)

и посмотрим, как она работает. Есть массив \(a\), в котором будет накапливаться наше двоичное число, по одной цифре в элементе массива.

Процедура \(check\) делает то, что надо сделать с очередным найденным числом: выводит его на экран. Если бы надо было делать что-то ещё, она бы делала что-то ещё; более подробно я напишу ниже.

Основная часть программы — процедура \(find\). Её «основная идея» — пусть у нас в массиве \(a\) первые \(i\) элементов уже заполнены некоторыми двоичными цифрами, т.е. сформировано некоторое начала \(k\)-битового числа. Таким образом, нам осталось перебрать все возможные окончания этого числа, т.е. все возможные комбинации на последних \(k-i\) цифрах. Вот функция \(find(i)\) именно это и будет делать.

Более строго, результатом вызова \(find(i)\) будет перебор всех возможных \(2^{k-i}\) «концов» числа, т.е. вызов процедуры \(check\) для всех \(2^{k-i}\) двоичных чисел с заданным началом. (У нас заполнены первые \(i\) элементов, т.е. осталось заполнить \(k-i\), потому и \(2^{k-i}\) вариантов; элементы массива нумеруются с нуля, поэтому \(i\) обозначает номер первой незаполненной позиции — позиции, откуда надо начинать заполнять массив \(a\).)

7.1.2. Почему это работает?

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

Посмотрим с конца.

Во-первых, как работает \(find(k)\). Видно, что она просто запускает \(check\) и выходит. Но именно это она и должна сделать в соответствии с «основной идеей». Действительно, вызов \(find(k)\) обозначает, что первые \(k\) элементов массива уже заполнены, т.е. заполнены все \(k\) элементов, т.е. уже сформировано очередное решение — осталось только вывести его на экран.

Рассмотрим теперь работу \(find(k-1)\). Она сделает следующее: поставит в \(a[k-1]\) цифру \(0\) и вызовет \(find(k)\), которая (как мы только что видели) выведет массив на экран. Потом она поставит в \(a[k-1]\) цифру \(1\) и опять вызовет \(find(k)\), которая опять просто выведет решение на экран.

Это полностью соответствует «основной идее». Действительно, первые \(k-1\) элементов массива уже должны быть заполнены, поэтому осталось только перебрать два варианта заполнения последней цифры и вывести оба на экран. Именно это она и делает.

Посмотрим теперь \(find(k-2)\). К её вызову первые \(k-2\) элемента массива уже должны быть заполнены, поэтому осталось перебрать все варианты заполнения оставшихся двух элементов. Что сделает \(find(k-2)\). Она поставит в \(a[k-2]\) ноль и вызовет \(find(k-1)\), которая, как мы видели, переберёт все возможные \(1\)-циферные окончания и выведет их на экран. Далее, когда \(find(k-1)\) отработает, произойдёт возврат в \(find(k-2)\), она поставит в \(a[k-2]\) единицу и опять запустит \(find(k-1)\), которая переберёт все возможные \(1\)-циферные окончания такого начала. Видно, что таким образом \(find(k-2)\) переберёт все возможные \(2\)-циферные окончания решения, сформированного перед её вызовом, т.е. отработает в соответствии с «основной идеей».

Теперь \(find(k-3)\). Ей надо перебрать все возможные \(3\)-циферные окончания. Она поставит ноль в \(a[k-3]\) и вызовет \(find(k-2)\), которая, как мы только что видели, действительно перебирает все \(2\)-циферные окончания. После этого поставит единицу в \(a[k-3]\) и опять вызовет \(find(k-2)\). Поскольку все \(3\)-циферные окончания — это либо ноль и \(2\)-циферное окончание, либо единица и \(2\)-циферное окончание, то вызов \(find(k-3)\) действительно перебирает все \(3\)-циферные окончания.

И так далее [на самом деле выше я просто тремя несколько различными способами описывал фактически одно и то же. Работа \(find(k-3)\) ничем принципиально не отличается от \(find(k-2)\) и т.п.].

Вообще, \(find(i)\) надо перебрать все окончания от \(i\)-ой цифры до конца массива. Но все такие окончания — это либо ноль и окончание от \(i+1\)-ой до конца, либо единица и окончание от \(i+1\)-ой до конца. В соответствии с этим \(find(i)\) и ставит в \(a[i]\) ноль и вызывает \(find(i+1)\), тем самым перебирая все окончания от \(i+1\)-ой цифры до конца, потом ставит в \(a[i]\) единицу и опять вызывает \(find(i+1)\).

Теперь ясно, что \(find(0)\) перебирает все \(k\)-значные окончания пустого числа (т.е. числа, в котором ноль цифр), т.е. действительно решает задачу.

../_images/table.png

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

Все двоичные числа можно представить в виде таблицы, приведённой выше: в первую очередь разделяем числа по первой цифре, во вторую очередь по второй и т.д. В соответствии с этим и работают процедуры \(find\). Можно себе представить ось времени направленную вертикально вниз, с верхней границей таблицы — моментом запуска \(find(0)\), нижней границей — концом запуска \(find(0)\). Самая левая вертикальная черта отражает работу \(find(0)\): она работает все время. Следующая вертикальная черта состоит из двух частей: они отражают работу \(find(1)\). Процедура \(find(1)\) будет запущена дважды (\(find(0)\) запустит её дважды), потому две черты. Каждый запуск \(find(1)\) запустит \(find(2)\) два раза — итого четыре запуска \(find(2)\), отражаемые четырьмя кусочками третьей вертикальной прямой. (все четыре копии будут работать одна за другой, а не одновременно, ведь вертикальная ось — это ось времени). Видно, что делает каждая процедура \(find\): она ставит в соответствующую ячейку массива \(a\) ноль, потом один (цифры справа от вертикальной черты, соответствующей запуску процедуры), и для каждой цифры запускает процедуру \(find\) «следующего уровня» (две вертикальные черты ещё правее). Видно и как будет в итоге меняться массив \(a\): вначале в нем все нули, потом, начиная с правых цифр, в нем меняются нули на единицы и т.д., в конце — все единицы.

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

7.1.3. Дерево решений

Все множество решений (в нашем случае решения — это все \(k\)-битовые двоичные числа) можно представить в виде дерева, делая сначала разделение решений по первому биту, потом по второму и т.д.:

../_images/tree.1.png

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

Я надеюсь, что в этом месте вполне понятно, как работает процедура \(find\).

7.1.4. О процедуре \(check\)

Обратите внимание, что на самом деле, как видно, нам совсем не важно, что делает процедура \(check\). Эта процедура делает то, что нужно в данной конкретной задаче сделать с найденным решением (в нашем случае — с найденным \(k\)-битным числом): надо его вывести на экран — выведем, надо в файл сохранить — сохраним, надо проверку какую-нибудь сделать — сделаем и т.д. Для написания собственно перебора не важно, что она будет делать; основная задача перебора — поставлять процедуре \(check\) одно за другим решения. Но именно процедура \(check\) будет делать то, зачем мы делали перебор: считать такие объекты, или проверять, подходит ли объект под условие, или искать объект минимальной стоимости…

7.1.5. Общая идеология поиска

Итак, нам надо перебрать объекты из некоторого множества. Более конкретно — вызвать процедуру \(check\) для каждого объекта. Таким образом, основная задача перебора будет состоять в том, чтобы вызвать процедуру \(check\) для всех объектов из нашего множества.

Обычно объекты из множества можно задавать некоторым массивом, элементы которого принимают те или иные значения. В приведённом выше примере это был массив \(a\) — массив двоичных цифр; везде ниже я аналогичные массивы тоже буду обозначать \(a\). Обычно перебрать все подходящие значения одного конкретного элемента массива \(a\) легко; в приведённом выше примере каждый элемент массива \(a\) мог принимать два значения: ноль и один.

Тогда перебрать все объекты можно с помощью следующей процедуры:

def find(i):
    if выбраны все элементы, т.е. сформировано некоторое решение:
        check()
        return
    для каждого возможного значения a[i]:
        a[i] = это значение
        find(i + 1)

Комментарии:

  1. Проверка на то, что решение сформировано. В простейшем случае это будет просто if i == k, как выше, но могут быть и более сложные варианты (например, если число элементов не фиксировано).

  2. Цикл по возможным значениям \(a[i]\). Опять-таки, в каждом конкретном случае, конечно, свой. Как правило, это будет цикл \(for\), нередко с вложенным \(if\), например,

    for j in range(n):
        if (j может быть значением a[i]):
            a[i] = j
            find(i + 1)
    

    примеры будут ниже.

Эта процедура \(find\) работает аналогично приведённому выше примеру (и вообще, все процедуры \(find\) в переборе работают аналогично друг другу): считая, что начало из \(i-1\) элемента фиксировано, перебирает все возможные окончания. Она смотрит, какой может быть \(i\)-й элемент, перебирает все его значения, и для каждого запускает рекурсивно \(find(i+1)\), которая переберёт все окончания, считая первые \(i\) элементов фиксированными.

Процедура \(check\) делает то, что надо сделать с решением. В большинстве случаев это проверка, удовлетворяет ли найденное решение каким-либо требованиям (примеры см. ниже), поэтом так и названа. Как я уже много раз говорил, конкретный вид процедуры \(check\) нам не важен.

7.1.6. Перебор всех \(k\)-значных чисел в \(n\)-ичной системе счисления

(Всего таких чисел \(n^k\))

(Зачем я все время привожу, сколько таких объектов: просто для того, чтобы вы могли лишний раз проверить, что вы понимаете, о каких объектах идёт речь: посчитайте сами в уме количество таких объектов и сравните; никакой больше нагрузки это не несёт.)

def find(i):
    if i == k:
        check()
        return
    for j in range(n):
        a[i] = j
        find(i + 1)

Я надеюсь, что работа этой процедуры если и не очевидна после всего вышеизложенного, то за несколько секунд становится понятной. Единственное отличие от примера 1 — то, что надо перебирать не \(2\) цифры, а \(n\), и потому перебор делаем циклом.

7.1.7. Разложение числа \(N\) в степени двойки

Несколько притянутый за уши пример: по данному числу \(N\) определить, можно ли его представить в виде суммы \(k\) степеней двойки, не обязательно различных.

Примечание

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

Будем перебирать все возможные наборы из \(k\) степеней двойки; соответственно, в массив \(a\) будем записывать последовательно эти степени.

def check():
    if sum(a) == n:
        print(*a)

def find(i):
    if i == k:
        check()
        return
    for j in range(31):
        a[i] = 1 << j
        find(i + 1)

Во-первых, я ещё раз привожу текст процедуры \(check\), чтобы вы видели, что она будет делать здесь (а она проверяет, подходит ли нам такое решение, и, если да, то выводит его на экран).

Во-вторых, обратите внимание на перебор всех степеней двойки циклом по \(j\). Можно, конечно, этот перебор написать и по-другому, например так:

a[i] = 1
while a[i] < (1 << 30):
    find(i + 1)
    a[i] <<= 1

или типа того: не суть важно, как написать перебор, главное, правильно написать, не забыв ни одного варианта; в частности, обратите внимание, что этот вариант кода, по сравнению с приведённым в процедуре \(find\) выше, перебирает на одну степень двойки меньше.

Контрольный вопрос 7.1:

Видите, почему?

Я надеюсь, что в остальном идея работы процедуры понятна.

Задача 7.2:

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

7.1.8. Перебор всех сочетаний из \(n\) по \(k\) (т.е. всех \(C_n^k\))

Хочется, аналогично тому, что мы делали раньше, в массив \(a\) записывать выбранные элементы. Но тут возникнут две проблемы: во-первых, надо, чтобы все элементы были различными, во-вторых, надо, чтобы сочетания не повторялись из-за изменения порядка элементов (ведь \(\{1,3\}\) и \(\{3,1\}\) — это одно и то же сочетание).

Задача 7.3:

Можно, конечно, это проверять в процедуре \(check\). Т.е. процедура \(find\) будет фактически работать по предыдущему примеру, а процедура \(check\) будет отбирать то, что нужно. Напишите такую программу. Обратите внимание на то, чтобы не брать одно и то же сочетание несколько раз.

Но на самом деле обе проблемы решаются одной идеей: будем требовать, чтобы в массиве \(a\) элементы шли строго по возрастанию (поймите, почему это решает обе проблемы!). Тогда получаем следующую процедуру \(find\) (считаем, что элементы, из которых мы собираем сочетание, занумерованы от \(0\) до \(n-1\)):

def find(i):
    if i == k:
        check()
        return
    for j in range(n):
        if i == 0 or j > a[i - 1]:
            a[i] = j
            find(i + 1)

Обратите внимание на нетривиальный \(for\). Проверка гарантирует, что все элементы будут идти по возрастанию. На самом деле, очевидно, что весь \(for\) можно заменить на

for j in range(a[i - 1] + 1, n):

(только надо аккуратно обойтись со случаем \(i=0\)).

Кроме того, заметьте, что теперь не все ветви перебора заканчиваются формированием решения. Действительно, если, например, \(k=3\), а мы на первом же уровне перебора (т.е. в \(find(0)\)) возьмём \(a[0]=n-1\), то видно, что на втором уровне (т.е. в \(find(1)\)) нам будет нечего делать. Аналогично, если \(k=3\), а на первом уровне берём \(a[0]=n-2\), то на втором придётся взять \(a[1]=n-1\) и на третьем делать нечего.

Задача 7.4:

а) Напишите эту программу. Обратите внимание на подготовку вызова \(find(0)\); проверьте, что перебираются действительно все сочетания (например, выводя их в файл и проверяя при маленьких \(n\) и \(k\)).

б) Добавьте в программу код, который выводит (на экран или в файл) «лог» работы рекурсии (например, выводя при присвоении \(a[i]=j\) на экран строку a[i]=j (с конкретными значениями i и j, т.е. print("a[", i, "]=", j)), сдвинутую на \(i\) пробелов от левого края строки: вам этот вывод покажет, что на самом деле делает программа и пояснит предыдущий абзац); этот «лог» лучше выводить вперемешку с найденными решениями, чтобы видеть, какая ветка рекурсии чем закончилась. (Вообще, такой «лог» — очень полезная вещь при отладке программ с перебором.) Подумайте над тем, как исправить то, что описано в предыдущем абзаце, т.е. как сделать так, чтобы каждая ветка рекурсии заканчивалась нахождением решения.

Замечу ещё, что в этой задаче можно написать процедуру \(find\) немного по-другому. А именно, будем ей теперь передавать два параметра, \(i\) и \(x\). Смысл параметра \(i\) тот же, что и раньше, а \(x\) обозначает, начиная с какого числа надо перебирать очередной элемент:

def find(i, x):
    if i == k:
        check()
        return
    for j in range(x, n):
        a[i] = j
        find(i + 1, j + 1)

На самом деле тут \(x\) будет всегда равен \(a[i-1]+1\), просто, может быть, такую процедуру проще понять, ну и проще разобрать случай i==0 (поймите, как!).

Смысл процедуры \(find\) теперь такой: перебрать все возможные окончания нашего сочетания, в которых все элементы не меньше, чем \(x\).

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

7.1.9. Перебор всех \(n!\) перестановок из \(n\) чисел (от \(0\) до \(n-1\))

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

Поэтому применим другой приём, который весьма полезен бывает во многих задачах на перебор. А именно, введём второй глобальный массив, массив \(was\), в котором будем фиксировать, использовали ли мы каждое число. Т.е. очередным элементом в перестановку будем ставить только те числа, которые ещё не были использованы. (Естественно, в массиве \(a\) будем хранить получающуюся перестановку).

was = [False] * n

def find(i):
    if i == n:
        check()
        return
    for j in range(n):
        if not was[j]:
            a[i] = j
            was[j] = True
            find(i + 1)
            was[j] = False

Во-первых, тут у нас количество элементов в объекте, которое раньше было \(k\), теперь равно \(n\) — общему количеству элементов, поэтому такое условие выхода из рекурсии.

Во-вторых, как собственно работает процедура \(find(i)\). Она перебирает, какой элемент надо поставить на \(i\)-е место. Этот элемент не должен быть использован ранее (т.е. не должен уже стоять в массиве \(a\)), потому и проверка if not was[j]:. Далее, она ставит этот элемент в массив \(a\), помечает, что он теперь использован и запускает \(find(i+1)\) для перебора всех «хвостов» текущей перестановки. При этом переборе элемент \(j\) использован уже не будет, т.к. в \(was[j]\) помечено, что он уже взят. Надеюсь, что работа процедуры понятна.

Задача 7.5:

Напишите программу перебора всех \(A_n^k\) — всех размещений из \(n\) по \(k\) (в них, в отличии от \(C_n^k\), порядок важен).

7.1.9.1. Откат состояния

А теперь обратите особое внимание на строчку

was[j] = False

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

Важно

Процедура \(find\) должна всегда возвращать назад все изменения, которые она производит (за небольшими исключениями, когда вы чётко осознаете, почему некоторое изменение можно не возвращать назад), причём лучше всего возвращать назад изменения сразу после вызова \(find(i+1)\).

Здесь процедура \(find\) пометила, что элемент \(j\) использован. Строка

was[j] = False

отыгрывает назад это изменение, что вполне логично, т.к. процедура \(find(i+1)\) переберёт все окончания, у которых на \(i\)-м месте стоит \(j\), и после этого мы будем перебирать другие варианты, в которых элемент \(j\) больше (пока) не используется. Очевидно, что, если бы этой строки не было, это привело бы к глобальным ошибкам в работе программы. Если вам это не очевидно, то тщательно продумайте этот момент; это важно и на самом деле это показывает, насколько хорошо вы понимаете работу перебора. Если никак не можете понять, в чем дело, вспомните аргументацию раздела «Почему это работает?», и промоделируйте аналогично работу в этом случае. Или напишите программу с «логом» работы и посмотрите, что пойдет не так.

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

def find(i):
    o_was = was[:]  # сохраняем старый массив
    if i == n:
        check()
        return
    for j in range(n):
        if was[j] == 0:
            a[i] = j
            was[j] = 1
            find(i + 1)
            was = o_was[:]  # восстанавливаем его

n = ...
a = [None] * n
was = [False] * n
find(0)

Один из минусов этого подхода — то, что довольно активно расходуется память в стеке, но зато не надо тщательно следить за всеми изменениями, которые делает \(find\), и не надо думать, какой же командой надо откатить изменения (здесь это было очевидно, но могут быть более сложные случаи).

Обратите внимание вот ещё на что: кажется, что эту же процедуру можно написать по-другому, так, чтобы она восстанавливала массив \(was\) до работы:

def find(i):
    o_was = was[:]
    if i == n:
        check()
        return
    for j in range(n):
        was = o_was[:]
        if was[j] == 0:
            a[i] = j
            was[j] = 1
            find(i + 1)

Но не очевидно, что этот вариант будет работать, т.к. последнее изменение не будет «откачено», и после окончания процедуры \(find\) массив was будет не таким, каким он был раньше (на самом деле его тут же исправит восстановление массива на уровень выше, но как минимум не очевидно, что это будет работать, надо думать). Поэтому старайтесь восстанавливать все изменения как можно раньше.

Кстати, ещё обратите внимание: все программы, которые мы до сих пор писали, изменяют массив \(a\) и не откатывают изменения. Поймите, почему это не страшно.

7.1.10. Совсем общая концепция перебора

Все задачи до сих пор у нас в основном крутились вокруг некоторого массива \(a\), который мы последовательно заполняли. Действительно, очень многие задачи, решаемые рекурсивным перебором, можно представить именно так — как задачу перебора возможных заполнений некоторого массива \(a\).

Но перебор, на самом деле, намного более мощная идея. Пусть у нас есть задача, в которой нам надо перебрать набор решений, а каждое решение образуется некоторой последовательностью «элементарных» шагов. То есть пусть мы можем говорить о каких-то «состояниях», «позициях» в этой задаче, из каждого состояния/позиции есть набор «ходов» в другие позиции, и нам надо найти последовательность ходов, приводящую к требуемой «конечной» позиции (или посчитать, сколько таких последовательностей есть, или найти оптимальную из них и т.д.) При этом будем считать, что у нас нет зацикливаний: мы не можем из одной позиции сделать несколько ходов и вернуться в нее же.

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

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

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

Но в «косынке» из каждой позиции у нас может быть несколько ходов. Поэтому процедура find будет работать так: по данной позиции она будет перебирать все возможные ходы и рекурсивно запускаться для поиска дальнейшего решения.

def find():
    if ходов нет:
        check()
        return
    for все возможные ходы:
        сделать ход
        find()
        откатить ход назад (!)

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

(Отмечу, что «оптимальность» хода можно было бы определить и сложнее, например, попытаться как-то учесть возможность противнику ошибиться. Но мы так усложнять не будем.)

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

def find(player):  # player = -1 -- нолики, player = 1 -- крестики
    # проверить, не окончена ли игра (т.е. выиграл ли уже кто-то и не заполнено ли поле)
    if игра окончена:
        if крестики выиграли:
            return 1
        elif нолики выиграли:
            return -1
        else
            return 0 # ничья
    # переменная optimal хранит номер выигрывающего игрока (-1, 0 или 1)
    # изначально худший для нас вариант -- выигрывает противник
    optimal = -player  # -player как раз дает противника
    for i in range(3):
        for j in range(3):
            if клетка (i, j) свободна:
                сходим в клетку (i, j)
                winner = find(-player)  # рекурсивно переберем дальнейшие варианты
                                        # и узнаем, кто выигрывает
                if player == 1:
                    # для крестиков мы хотим
                    # номер выигрывающего игрока как можно больше
                    # т.е. крестики лучше ничьей, а ничья лучше ноликов
                    if winner > optimal:
                        optimal = winner
                else:
                    # player == -1 -- нолики
                    # для ноликов мы хотим
                    # номер выигрывающего игрока как можно меньше
                    # т.е. нолики лучше ничьей, а ничья лучше крестиков
                    if winner < optimal:
                        optimal = winner
                отменим ход в (i, j)  # откатимся!!
    # теперь optimal --- выигрывающий игрок при самом лучшем нашем ходе
    return optimal

Задача 7.6:

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

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

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

Еще пример такой задачи:

Задача 7.7:

(Задача «резисторы») Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью \(C\) мкФ. В распоряжении Пети есть набор из \(n\) конденсаторов, емкости которых равны \(c_1\), \(c_2\), …, \(c_n\), соответственно. Петя помнит, как вычисляется емкость параллельного соединения двух конденсаторов (\(C_{new} = C_1 + C_2\)) и последовательного соединения двух конденсаторов (\(C_{new} = C1\cdot C2/(C1+C2)\)). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы.

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

7.1.11. Дополнительные задачи

Я надеюсь, что вы решите одну-две задачи и хотя бы серьёзно (хотя бы день) подумаете над остальными (или решите их), прежде чем переходить к части Отсечения. Часть из (нормальных переборных) решений этих задач используют идеи, про которые я буду рассказывать в части Отсечения, но будет неплохо, если вы додумаетесь до них сами :), или как минимум если напишете что-то хоть и корявое, но работающее.

Точнее, сначала убедитесь, что материал части текущего раздела (Элементарные примеры) у вас «осел» в голове, и что вы этот раздел понимаете (а для этого прорешайте задачи из основного текста раздела), потом решайте задачи. Если не решите (подумав над задачами хотя бы некоторое время, день-два), смотрите подсказки. Попробуйте учесть их и подумать над задачами ещё. Потом разберите решения. Может быть, последние три задачи вам покажутся нетривиальными — ну хотя бы попробуйте их решать…

Задача 7.8:

Напишите программу перебора всех последовательностей длины \(n\), состоящих из нулей и единиц, в которых не встречается \(k\) нулей подряд. (Например, при \(k=2\) и \(n=3\) это будут последовательности 010, 011, 101, 110 и 111). Основной задачей программы будет посчитать, сколько таких последовательностей всего, но имеет смысл выводить их на экран (или в файл) для проверки.

а) Напишите эту программу, модифицировав пример 1, т.е перебирая все последовательности из 0 и 1 длины \(n\), и проверяя, что последовательность «правильная», только в процедуре \(check\).

б) Напишите программу, которая будет перебирать только такие последовательности, т.е. чтобы каждая ветка перебора заканчивалась нахождением решения, и в процедуре \(check\) проверки не были бы нужны.

в) (дополнительный пункт, не имеющий отношения к перебору) Если вы раньше не сталкивались с такой задачей, то попробуйте найти несложную закономерность ответов при фиксированном \(k\) (т.е. сначала посмотрите на ответы на задачу при \(k=2\) и найдите в них закономерность, потом поищите закономерность при \(k=3\), потом при \(k=4\) и т.д.) Кстати, не забудьте, что тестить имеет смысл и очевидный случай \(k=1\) :)

Задача 7.9:

Паросочетание в произвольном графе. Рассмотрим граф с \(2N\) (т.е. чётным) количеством вершин. Паросочетанием в нем назовём набор из \(N\) рёбер, у которых все концы различны (т.е. каждая вершина соединена ровно с одной другой: разбиение вершин на пары). [В олимпиадном программировании обычно рассматривается только паросочетание в двудольном графе, т.к. там есть простой эффективный алгоритм. Но у нас граф будет произвольным и мы будем решать задачу перебором]. [Т.е. смысл этой задачи на самом деле — чтобы вы умели перебирать все разбиения на пары]

а) Напишите программу, которая будет перебирать все разбиения вершин на пары и проверять, является ли такое разбиение паросочетанием (т.е. все ли нужные ребра присутствуют в нашем графе).

б) Считая, что граф полный и взвешенный, напишите программу, которая найдёт паросочетание наименьшего веса.

Задача 7.10:

Напишите программу перебора всех разложений числа \(N\) на натуральные слагаемые.

Вариант 1: ровно на \(k\) слагаемых

а) считая, что слагаемые могут повторяться и что порядок слагаемых важен (т.е. что \(2+1\) и \(1+2\) — это разные решения);

б) считая, что порядок слагаемых не важен, т.е. выводя только одно разложение из разложений \(2+1\) и \(1+2\), при этом допуская одинаковые слагаемые;

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

Вариант 2: на сколько угодно слагаемых в тех же трёх подвариантах (а, б и в)

Написав программы, прежде чем тестировать их, ответьте в уме на такой вопрос: ваша (уже написанная!) программа в варианте «а» будет при \(n=3\) выводить решения \(1+2\) и \(2+1\). А при \(n=2\) она будет выводить \(1+1\) один раз или два раза (во второй раз как будто переставив единички)?

Задача 7.11:

Задача «Числа». Дана последовательность из \(N\) чисел. За одно действие разрешается удалить любое число (кроме крайних), заплатив за это штраф, равный произведению этого числа на сумму двух его соседей. Требуется удалить все числа (кроме двух крайних) с минимальным суммарным штрафом.

У этой задачи есть (не самое тривиальное) динамическое решение, но напишите переборное решение. Тут надо перебрать все варианты удаления чисел и выбирать из них тот, который даст минимальный штраф.

Задача 7.12:

(Какая-то довольно искусственная задача, но хорошо подходит для иллюстрации одной из идей далее). Посчитать количество последовательностей из \(m\) нулей и \(n\) единиц, удовлетворяющих следующих условиям. Первое условие: никакие две единицы не должны стоять рядом. Таким образом единицы делят последовательность на несколько групп из подряд идущих нулей. Второе условие: количество нулей в последовательных группах должно неубывать, и при этом в соседних группах должно отличаться не более чем на 1. Эта задача имеет динамическое решение, но напишите перебор.