Вышеупомянутая процедура подразумевает «жадный» (greedy) подход: на каждом этапе алгоритма мы выбираем ход, лучший в данный момент в локальном смысле. Но чтобы найти более оптимальное решение в глобальном смысле, нужно на каждом этапе рассматривать не только лучший в данный момент ход, но и второй по оптимальности и т. д. Такой подход требует намного большего количества вычислений, чем «жадный». Например, если исключить из рассмотрения первый – самый лучший – стек и начать коллекцию со второго или даже третьего стека, в некоторых случаях можно получить коллекцию, более приближенную к оптимальной. Это возможно тогда, когда коробки из первого стека присутствуют во многих стеках в верхней части отсортированного списка, и нам придется исключить их, так что в коллекции останутся стеки с более высокими порядковыми номерами, хуже качеством и меньшей численности. Предположим, в высотном диапазоне всего 200 стеков, и если начать с первого, то получится следующая коллекция: 1, 11, 32, 53, 89, 142, 190. Если же начать со второго, то коллекция будет такой: 2, 3, 8, 14, 26, 33, 52, 85, 101, 141, 162, 173. Эта коллекция содержит больше стеков в среднем лучшего качества: среднее качество стеков примерно обратно пропорционально усредненному номеру стеков в коллекции. Если же начать с третьего стека, то получится еще одна коллекция, отличная от предыдущих.
У коллекции, начавшейся с первого стека, больше шансов оказаться лучшей из возможных (на практике коллекции, начинающиеся с первого стека, выигрывали у последующих более чем в половине случаев), у начавшейся со второго – значительно меньше, с третьего – еще меньше. Перебирая все возможные коллекции, получим слишком много вариантов. Лучшие варианты статистически сосредоточены в начале такой процедуры отбора.
В процессе мне нужно было выработать критерий оптимальности, и он далеко не прост. Допустим, мы сравниваем две коллекции стеков. Одна – с общей площадью оснований в 84 % от площади основания палеты и 5 % пустого пространства (95 % объемной эффективности) по всем стекам. Другая коллекция – с общей площадью оснований в 96 % от площади палеты, но с объемной эффективностью 82 % в среднем по всем стекам. Какая из них лучше? Окончательного ответа нельзя дать до того, как эти стеки будут упакованы на двумерной плоскости внутри основания палеты. Скорее всего, не все стеки второй коллекции поместятся на этом пространстве, то есть эффективная общая площадь будет не 96 %, а меньше, скажем, 85 %. В этом случае первая коллекция (если все ее стеки будут упакованы в слой) образует слой лучшего качества. Но если очень повезет и все стеки второй коллекции поместятся в указанное пространство, тогда вторая коллекция будет, скорее всего, предпочтительнее первой – между стеками будут очень узкие щели, хоть и в среднем больше пустого пространства внутри самих стеков.
Предсказать заранее качество коллекции из начального списка всех возможных стеков разной высоты совсем не просто. Один диапазон высот мог дать несколько хороших коллекций, а другой, с изначальным числом стеков, не меньшим, чем в первом, – всего лишь одну хилую коллекцию с плохим покрытием площади палеты.
Я стал проверять, какие коллекции стеков получаются из реалистичного набора коробок, типичного для оптового заказа из супермаркета. Вначале у меня не было никакой уверенности, что результат будет удовлетворительным, а именно что полученных стеков в узком диапазоне высот хватит, чтобы хорошо покрыть площадь палеты.
Я прогонял через алгоритм типичные наборы коробок в заказах склада в Ньюбурге, и… результат превзошел даже самые мои оптимистические ожидания. Я написал на Матлабе функцию, которая визуализировала полученные стеки. Каждый из них представлялся в виде нескольких прямоугольников, чья длина и ширина соответствовала размерам коробок, с общим центром (как стеки и должны выглядеть сверху), с обозначением высоты каждого стека и с указанием того, какие коробки из набора были использованы в данной коллекции. В диапазоне высот с разницей до 12 мм из самых полных ячеек гистограммы часто получалось 12–15 или даже больше стеков с общей площадью, значительно превышающей площадь основания палеты. Большинство стеков имели достаточно хорошую форму (основания коробок в них были похожи друг на друга). Оказалось, что почти всегда можно будет построить хорошо заполненный плоский слой из стеков! И это уже была фантастика!