Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.
КДПВ: задача о ранце на живом примере
Предыстория
Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.
Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2n (количество сочетаний, умноженное на длину суммы).
Прошло 5 лет. Я успел закончить школу и поступить в университет, но эта задача по-прежнему была со мной. Один раз, листая книгу «Алгоритмические трюки для программистов» (Hacker's Delight / Henry S. Warren Jr.), я наткнулся на описание кода Грея: это последовательность двоичных чисел, каждое из которых отличается от предыдущего только одним битом. «Стоп!» — подумал я — «Это означает… Да! Это означает, что в той самой задаче на каждом шаге перебора можно не считать сумму целиком, а лишь добавлять или вычитать одно число». И я тут же углубился в изучение темы.
Построение кода Грея
Код Грея можно построить для числа любой разрядности. Для одного разряда он очевиден:
0
1
Чтобы добавить второй разряд, можно к этой последовательности дописать такую же задом наперёд
0
1
1
0
и ко второй половине дописать единицы:
00
01
11
10
Аналогично для трёх разрядов:
000
001
011
010
110
111
101
100
Такой код, полученный отражением кода меньшей разрядности, называется рефлексным (отражённым) кодом Грея. Бывают и другие последовательности, но на практике обычно используется именно эта.
Этот код назван в честь Фрэнка Грея, который изобрёл ламповый АЦП, выдававший цифровой сигнал именно в этом коде. При небольших изменениях уровня входного сигнала цифровой выход мог измениться только в одном бите, и этим исключались резкие скачки из-за неодновременного переключения битов.
Иллюстрация патента Фрэнка Грея
Самое наглядное применение кода Грея — в датчиках угла поворота. Датчик, аналогичный тем, что был в старых механических мышах, но определяющий не относительное смещение, а абсолютное значение угла. Для этого на каждый датчик нужно несколько оптопар и несколько щелевых решёток. Причём каждое следующее положение датчика должно отличаться от предыдущего только состоянием одного бита, иначе на границах возможно несинхронное переключение битов, и следственно — резкие скачки в показаниях прибора. Здесь видна любопытная особенность кода Грея: последнее число также отличается от первого одним битом, поэтому его можно «закольцевать».
Датчик абсолютного угла поворота. Оптические щели расположены в соответствии с кодом Грея
Применение в задаче о ранце
Но вернёмся к задаче о ранце. Стандартная формула даёт нам код Грея по номеру:
G = i ^ (i >> 1)
По ней мы можем только посчитать сумму все нужных элементов. А мы собирались на каждой итерации добавлять или вычитать одно значение, верно? Значит, нам нужно получить номера изменяемых битов. Для многоразрядных чисел эти номера будут такими:
0
1
0
2
0
1
0
3
0
1
0
2
0
1
0
4
…
Ничего не напоминает? Это номер бита, который мы устанавливаем в единицу, когда просто перечисляем обычные двоичные числа. Или иначе — номер младшей единицы в двоичном числе. Эта операция называется find first set и в большинстве процессоров существует в виде отдельной инструкции. Visual C++ предоставляет эту инструкцию в виде функции _BitScanForward.
Итак, теперь мы готовы написать программу, решающую задачу о ранце через код Грея. Сформулируем задачу так:
В файле input.txt в первой строке указана вместимость рюкзака, а в остальных строках — размеры вещей. В консоль нужно вывести максимальную загрузку рюкзака и размеры выбранных вещей. Проверку корректности ввода и пр. — нафиг.
Мы будем хранить битовую маску использованных вещей, и по мере необходимости добавлять или убирать одну из них. Чтобы обойтись int-ами, ограничим количество вещей (и используемых бит) тридцатью одной.
#include <iostream>
#include <fstream>
#include <bitset>
#include <intrin.h>
using namespace std;
void main()
{
int target; // размер ранца
int nItems = 0; // количество предметов
int weight[31]; // веса предметов
ifstream inFile("input.txt");
inFile >> target;
while(inFile >> weight[nItems])
nItems++;
inFile.close();
const unsigned int nIterations = 1 << nItems; // количество комбинаций, 2^n
int sum = 0; // текущий вес вещей
int bestSum = 0; // лучший вес (максимальный без перегрузки)
bitset<31> mask; // текущая комбинация выбранных вещей
bitset<31> bestMask; // лучшая комбинация выбранных вещей
for (unsigned int i = 1; i < nIterations; i++)
{
unsigned long position; // какой по счёту бит инвертируем
_BitScanForward(&position, i);
mask[position] = !mask[position];
if (mask[position]) // кладём в рюкзак или убираем эту вещь
sum += weight[position];
else
sum -= weight[position];
if (sum > target) // перегруз
continue;
if (sum > bestSum) // Отличный вариант! Надо запомнить...
{
bestSum = sum;
bestMask = mask;
}
}
cout << "Best approximation: " << bestSum << endl;
cout << "Used weights:" << endl;
for (int i = 0; i < 31; i++)
if (bestMask[i])
cout << weight[i] << endl;
cin.get();
}
Прощу прощения за возможные шероховатости; к сожалению, C++ уже давно не мой профильный язык.
Работает действительно быстрее, чем сборка с нуля всех сумм, разница заметна уже при 20 числах, а при 30-и я так и не дождался выполнения наивного алгоритма, в то время как новый вариант выполняется за 7 секунд. Впрочем, учитывая экспоненциальную сложность, это совсем не мало: для 50 чисел использовать этот алгоритм уже нет смысла. К сожалению, любой точный алгоритм будет работать не быстрее, чем за 2n; быстрее возможно только приблизительное решение.
Наверное, именно поэтому я обречён до конца жизни нести свой ранец, пытаясь ускорить эту программу. Я уже однажды переписывал цикл на ассемблере, получив небольшой прирост в скорости, а сейчас даже подумываю сделать многопоточную версию программы. Вам же остаётся лишь мне посочувствовать. :)
Автор: Fedorkov
