Перебор и его сокращение.

Обычно когда необходимо рассмотреть способы сокращения перебора, авторы всегда разбирают задачу расстановки 8 ферзей на шахматной доске. Поскольку эту задачу больше 200 лет тому назад решил еще Леонард Эйлер, то вряд ли сейчас есть, хоть какая-то возможность ошибиться, при описании решения этой проблемы. Но в связи с тем, что техника не стоит на месте и прямой перебор 40320 (=8!) вариантов, а именно столько вариантов расстановки ферзей надо рассмотреть, чтобы решить задачу, не является чем то из ряда вон выходящим и осуществляется, даже не на самом современном компьютере, меньше чем за минуту, то и сокращение такого перебора прямо скажем не слишком впечатляет. Поэтому мы будем рассматривать сокращения перебора, используя в качестве модели другую задачу, а именно задачу о рюкзаке. Допустим, что нам дан массив A состоящий из N положительных целых чисел и дано целое положительное число Sum. Нам необходимо найти такие подпоследовательности элементов массива, сумма которых в точности равна Sum.

Решение простым перебором тривиально, и основывается на тех же соображениях, что и доказательство известного факта: количество всех подмножеств множества A состоящего из N элементов равно 2^N. Сопоставим каждой подпоследовательности двоичное разложение целого числа из отрезка 0... 2^N-1. Двоичное разложение представим в виде массива P, при этом P[k]=1, если k-ый элемент исходного массива входит в подпоследовательность и P[k]=0 в обратном случае. Переход от одной последовательности к другой осуществляем прибавлением 1 к числу, задаваемому массивом P. Мне неизвестно способа «быстрого» решения задачи, т.е. такого способа, время работы которого не будет расти как O(2^N). И тот способ сокращения перебора, который я предлагаю, на некоторых последовательностях может не дать уменьшения времени работы.

Договоримся о способе представления результатов. Количество найденных последовательностей будем хранить в переменной l, сами последовательности в массиве строк Results. При этом k-ый элемент массива Results содержит разделенные запятыми номера элементов исходного массива A, входящих в k-ую последовательность. Я использую функцию IntToStr для представления целого числа в виде строчной переменной. Надеюсь, что Вы не слишком запутались, в крайнем случае, посмотрев на блок-схему алгоритма, все должно стать на свои места.

Итак, сам алгоритм простого перебора будет выглядеть так:

В случае достаточно больших N (например N=50) дождаться, когда алгоритм закончит работу практически невозможно.

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

Будем считать, что наш массив упорядочен по не убыванию, если это не так, упорядочим его. Будем набирать последовательности, начиная с наибольших элементов. Вначале найдем номер k₀ такой, что A[k₀+1] &gt Sum (а следовательно, в силу упорядоченности массива и A[k₀+j] &gt Sum, для всех j=1...n-k₀), но A[k₀] &lt Sum. Помещаем элемент k₀ в нашу подпоследовательность, теперь нам надо решить ту же задачу, для элементов массива A с номерами 1...N₁=k₀-1 и значения Sum₁=Sum-A[k₀]. Получили рекурсию, выход из которой, будем осуществлять, в случае, если либо Sum_j=0, тогда найдена последовательность, удовлетворяющая условиям задачи, либо если k_j=0, тогда надо вернуться на шаг назад и изменить значение k_j-1 на k_j-1-1.

Чтобы запустить процедуру Recurs, определяем l=0 (количество найденных последовательностей) s=’’, и вызываем Recurs(Sum,s,N). В принципе, уже эта процедура показывает неплохое время работы, за счет того, что мы отбрасываем из рассмотрения заведомо неудачные последовательности.

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

Можно продолжить усовершенствовать алгоритм, я этого делать не буду, поскольку считаю выполненной цель написания данной статьи, я показал, как сократить перебор, но Вам дам одну подсказку: Допустим сумма всех элементов массива A меньше, чем величина Sum. Имеет ли тогда задача решения? А если например, создать массив SumA, k-ый элемент которого равен сумме A[1]+...+A[k], поможет ли это сократить перебор. Мысль не плохая, но я вижу как минимум одно препятствие в ее реализации, а Вы? Препятствием будет служить тот факт, что для некоторого k, SumA[k] может стать настолько большим, что для его представления не хватит разрядности.

В качестве заключения укажу класс последовательностей (массивов A), для которых задача имеет хорошее решение. Допустим, A является сверхрастущим, т.е. A[k] &gt A[1]+...+A[k-1], тогда можно представить алгоритм (попробуйте), который найдет все последовательности с суммой элементов равной Sum, за время O(n).