калинин.ru / программирование / алгоритмы /

<< 11.11.00 >>

Полный перебор

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

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

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

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

Что бы не быть голословным, приведу пример обычной задачи на перебор. Задача предлагалась на олимпиаде ВМК в 1998 году (задача C, "парламент"):

	Цитата
	Совсем недавно в Одном Островном Государстве разразился правительственный кризис, в результате которого все правительство во главе с премьер-министром было отправлено в отставку. По Конституции государства, новый премьер-министр назначается президентом, но должен пройти процедуру утверждения своей кандидатуры в парламенте. Зная оппозиционные настроения парламента по отношению к новой кандидатуре премьер-министра, президент решил обратиться за помощью к некоему финансовому магнату, имеющему близкие связи с кандидатом в премьеры и заинтересованному в утверждении. Финансовый магнат выделяет некоторую сумму X тугриков (6 тугриков примерно равны 1 доллару США), которая должна быть истрачена на убеждение депутатов в необходимости утверждения кандидата. Парламент государства состоит из N (0 < N < 1000) депутатов, которые всегда ходят на все заседания и голосуют всегда либо за, либо против (воздержавшихся и не голосовавших не бывает). О каждом депутате i парламента известно априорное отношение этого депутата к кандидатуре премьер-министра, выражаемое в вероятности p0i (0 <= p0i <= 1), с которой данный депутат проголосует за кандидатуру. Однако если на убеждение депутата потратить Ki тугриков, депутат обычно обещает поддержать кандидата, но, поскольку голосование тайное, в действительности депутат голосует за с вероятностью p1i (0 <= p1i <= 1). По предыдущему опыту общения президента с парламентом известно, что если президенту удается заручиться предварительной поддержкой 70% голосов депутатов, нужное решение всегда проходит. С другой стороны, президент желал бы сэкономить как можно больше денег, ибо его финансовое положение несколько пошатнулось в результате кризиса на азиатских рынках. Поэтому он готов заплатить 10% от сэкономленной суммы за наилучший вариант убеждения депутатов и за сохранение конфеденциальности. Экспертная группа при президенте готова произвести необходимые расчеты, но при условии, что она в любом случае получит как минимум M тугриков (и как максимум -- 10% от сэкономленной суммы). Если выделенная магнатом сумма будет меньше M, то группа отказывается даже производить расчет. Если сумма будет больше M, но окажется недостаточной для обеспечения прохождения кандидатуры (с учетом оплаты работы группы), группа расчитает, на какой максимальный процент голосов в поддержку может расчитывать президент. Весь остаток суммы X, не потраченный на депутатов и группу экспертов, остается в распряжении президента.

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

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

Решением задачи, по сути, будет являться набор индексов депутатов, которым надо будет заплатить. Для каждого из депутатов есть только два варианта: либо ему платят, либо нет; соответственно множество возможных решений есть набор упорядоченных N-ок, на i-ой позиции в которых находится флаг "платить/не платить" для i-го депутата. Нетрудно видеть, что эти "упорядоченные N-ки" являются N-разрядными числами, представленными в двоичной системе счисления. Соответственно, множество возможных решений будет содержать в себе все возможные варианты таких чисел, т.е. элементом этого множества будет являться число от 000..0₂ до 111..1₂. Соответственно, очень просто сделать перебор элементов множества в естественном порядке "по возрастанию", прибавляя 1 к текущему числу, начиная с 0 и кончая 2^N-1.

Выглядит это примерно следующим образом:

struct deputat
{
    float p0;
    float p1;
    int K;
};

deputat* d;
bool*    state;
int N, X, M;

		Лирическое отступление:
		Массив элементов типа bool на самом деле не является хорошим решением для хранения "флагов" потому что размер переменной bool как минимум 1 байт (т.е., 8 бит), что несколько расточительно. Вообще говоря, никто не мешает уменьшить размер массива в 8 раз и для проверки или установки флагов в массиве использовать операции индексации внутри массива вместе с битовыми операциями над целыми числами. К слову сказать, в STL уже существуют необходимые шаблонные классы для этого. Например, std::vector<bool> является битовым массивом, а не массивом элементов типа bool, так как реализован в виде специализации основного шаблона std::vector<T>. Кроме того, существует шаблон std::bitset, реализующий конечное счетное множество элементов на битовом массиве.

В переменных N, X, M и массиве d размера N содержится информация, которая задается на входе. В массиве state (в смысле, что этот указатель после чтения данных будет указывать на область памяти, в которой содержится N элементов bool) содержится текущий элемент из множества возможных решений. Если state[i] содержит в себе true, то на i-го депутата тратятся деньги и наоборот.

double Q;
int Td, Te, Tp;

Эти переменные имеют смысл в рассматриваемой задаче и в них будут находится текущие "лучшие" значения требуемых параметров.

Теперь опишем подпрограмму, которая будет по текущему элементу перебираемого множества строить следующий элемент.

bool next()
{
  int i = N-1;

  for(; i >= 0; i--)
    if(state[i])
      state[i] = false;
    else
      {
        state[i] = true;
        break;
      }

  return(i < 0 && !state[0]);
}

Подпрограмма очень простая и всего навсего реализует прибавление 1 к числу, записанному в двоичной системе счисления. Возвращаемое значение --- true, если произошло переполнение при сложении. Эта ситуация возникает тогда, когда добавляют единицу к N-разрядному числу 111..1₂ (не хватает разрядов для записи результата), т.е., фактически, означает конец перебора. В начале программы, понятно, массив state инициализируется значениями false.

Кроме того, понадобится подпрограмма "проверки качества" текущего решения (по отношению к уже отобранному).

void check()
{
  double Q = 0.;
  int Td = 0, Te, Tp;
    
   /*
    * Вычисляем значения локальных
    * переменных Q, Td, Te и Tp исходя
    * из state.
    */

   // ...

   /*
    * Если значения локальных переменных
    * Q, Td, Te и Tp "лучше", чем значения
    * глобальных переменных ::Q, ::Td, ::Te
    * и ::Tp, то заменяем значения глобальных
    * переменных локальными.
    */

    if( ... )
      {
        ::Te = Te;
        ::Td = Td;
        ::Tp = Tp;
        ::Q = Q;
      }
}

Сами вычисления нас сейчас не особенно интересуют, потому что это --- ненужные тонкости. Дополняет общую картину еще один цикл, который обе эти функции связывает воедино:

for(;;)
  {
     check();
     if(next()) break;
  }

Собственно, это все: после завершения работы этого цикла в глобальных переменных Q и т.д. будут находится искомые значения. А теперь о грустном. Внутренность внешнего цикла исполнится ровно 2^N раз, т.е. именно столько раз будут вызваны внутренние функции. На каждый вызов тратится машинное время... в общем, то что я эти две части внутреннего цикла оформил в виде подпрограмм, еще не значит, что надо так же делать в реальной жизни: очень часто замена подпрограммы на непосредственное включение кода в точки вызова (через inline или #define) приводило к ускорению работы "в целом" в несколько раз.

Теперь уж о совсем грустном... если для некоторого N работа программы, построенной при помощи полного перебора еще хоть как-то удовлетворяет, то для N+1, скорее всего, скорость работы перестанет быть удовлетворительной. Это логично: потому что при включении еще одного депутата в парламент, количество вычислений удвоится! Что терпимо для относительно маленьких N, но совершенно не подходит для больших N.

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

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

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

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

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

Более подробно эти методы я рассмотрю позже, а если кто-то заинтересовался, то ссылки на книги можно найти внизу этой заметки.

Резюме

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

PS

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

Версия для печати

Ссылки по теме:

/comment/books/11_07_00.shtml    Программирование: теоремы и задачи.

Н. Вирт    Алгоритмы + Структуры данных = Программы.

Рядом в разделе: Рекурсия, часть II (11.09.00)    Собственно, в своей я рассказал немного не о том, о чем хотел. Поэтому сегодня придется дополнять ;) Кроме того, что рекурсия...   >>>> Рекурсия (04.09.00)    Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто...   >>>>

Рядом по дате: Высокий штиль (12.11.00)    У О. Генри есть забавный рассказ под названием "Теория и практика", в котором редактор журнала и бедный писатель спорят друг с...   >>>> acm.gui.uva.es, задачник по программированию (07.11.00)    Наконец-то я вспомнил о действительно полезном ресурсе, который стоит описать. Вообще, полезность или бесполезность чего-либо, конечно же, нельзя оценить "огульно", надо...   >>>>

Содержание:

Заглавная страница Мой блог Мое резюме Дайджест Программирование    C&C++ Сети Unix Алгоритмы Оптимизация Соревнования Отвлеченно XML TeX Просто так

Студенческое Туризм   Байки Фотографии Комментарии    Книги Web-ресурсы Фильмы Интернет Программное обеспечение Жизнь Благодарности Форум Хронология