Рассмотрим множество предметов, показанных на рис. 3.2.5. Их пять: два из них имеют размер 3 и три - размер 2. Какое требуется минимальное число ящиков размера 4, чтобы поместить в них все предметы? Ответ показан на рис. 3.2.6, где заштрихованные участки обозначают пустые места в ящиках.

Рис. 3.2.6. Минимальное число ящиков размера 4, требуемое для размещения предметов размерами 2, 2, 2, 3 и 3.

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

HI (ггервое попавшееся размещение для заданного списка. First Fit, FF). Пусть L - некоторый порядок предметов. Первый предмет из L кладем в ящик В. Второй предмет из L кладем в Bi, если он туда помещается. В противном случае кладем его в следующий ящик В. Вообще очередной предмет из L кладем в ящик Bi, куда этот предмет поместится, причем индекс i ящика наименьший среди всех возможных. Если предмет не помещается ни в один из k частично заполненных ящиков кладем его в ящик Bj+j. Этот основной шаг повторяется, пока список L не будет исчерпан.

Н2 (первое попавшееся размещение с убыванием. First Fit Decreasing, FFD). Этот алгоритм отличается от алгоритма FF тем, что список L упорядочен от больших предметов к меньшим.

НЗ (лучшее размещение для заданного списка. Best Fit, BF). Пусть L - заданный порядок заданий. Основной шаг тот же, что и в FF, но очередной предмет кладется в тот ящик, где остается наименьшее неиспользованное пространство. Таким образом, если очередной предмет имеет размер 3 и есть четыре частично заполненных ящика размера 6, в которых осталось 2, 3, 4 и 5 единиц незаполненного пространства, тогда предмет кладется во второй ящик, и тот становится полностью заполненным.

Н4 (лучшее размещение с убыванием. Best Fit Decreasing, BED). Этот алгоритм такой же, как и BF, но L упорядочен от больших предметов к меньшим.

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

Ь ящиков

N0 = 9

1-2е

1-2е

Рис. 3.2.7. Пример, в котором эвристический алгоритм первого попавшегося размещения с убыванием дает наихудшее возможное соотношение: Л д/ЛоП/Э.

следующим образом. Пусть Л/о - минимальное число необходимых ящиков, полученное при помощи точного алгоритма. Если iVpFD обозначает приближенное решение, найденное алгоритмом FFD, тогда для любого е>0 и достаточно большого iVo

tFFD

Nn 9

Таким образом, алгоритм FFD дает решение, которое не может быть хуже оптимального более чем на 23%. Это гарантированная оценка; для любой конкретной задачи ошибка может быть намного меньше.

Нелегко построить пример, на котором эвристический алгоритм FFD работает наихудшим возможным образом. Прежде чем читать дальше, попытайтесь немного поэкспериментировать. Представим один такой «плохой случай». Пусть 8>0 - произвольно выбранное, но маленькое положительное действительное число. Предположим,

что все ящики размера 1 и что нужно упаковать следующие предметы:

6 предметов размера у+е.

6 предметов размера -j+e

12 предметов размера 2е,

6 предметов размера -+2е.

На рис. 3.2.7, а показана оптимальная упаковка, использующая iVo= =9 ящиков. Очевидно, что эта упаковка оптимальна, так как все 9 ящиков полностью заполнены. Если для решения этой задачи применить эвристический алгоритм FED пункта Н2, получим упаковку, показанную на рис. 3.2.7, б, использующую A/ffd=11 ящиков.

Задачи упаковки могут быть удивительно обманчивы. Например, если нужно упаковать в ящики размера 1000 предметы размеров L=(760, 395, 395, 379, 379, 241, 200, 105, 105, 40), то эвристический алгоритм Н2 потребует для этого Лрро=3 ящика. Это на самом деле оптимальное решение (проверьте это). Давайте уменьшим все размеры на одну единицу, что приводит к списку L=(759, 394, 394, 378, 378, 240, 199, 104, 104, 39). Теперь эвристический алгоритм FED дает iVFFD=4. Это, очевидно, не оптимальное и совершенно неожиданное решение. Почему этот пример не нарушает результата 11/9?

Обратим внимание на другую аномалию. Применяя эвристический алгоритм HI, упакуем L=(7, 9, 7, 1, 6, 2, 4, 3) в ящики размера 13. Находим, что Лрр=3, как показано на рис. 3.2.8, а; очевидно, что этот результат оптимальный. Уберем предмет размера 1, что приводит к списку L= (7, 9, 7, 6, 2, 4, 3). Теперь, как показано на рис. 3.2.8, б, ЛРР=4.

Другие примеры аномалий у эвристических алгоритмов для задач составления расписаний даны у Грэхэма [41].

Упражнения 3.2

L3.2.1. Алгоритм GTS2 {реализация). Напишите программу для алгоритма GTS2. Проведите экспериментальный анализ среднего результата.

3.2.2. Алгоритм GTS2. Алгоритм GTS2 использует несколько городов в качестве «начального» города.. Что, если коммивояжер имеет единственный начальный город, скажем тот, в котором он живет. Означает ли это, что он не может использовать тур, полученный алгоритмом?

*3.2.3. Эвристический алгоритм для задачи коммивояжера (разработка). Предположим, что в симметричной задаче коммивояжера мы нашли тур (не обязательно оптимальный). Выбираем произвольно в этом туре два несмежных ребра, допустим (i, j) и (k, I). Предполагая, что данные четыре города встречаются в порядке i, j, k, I (меж-ДУ / и й находятся другие города), мы можем преобразовать текущий тур в новый, исключая ребра (i, /) и {k, I) и заменяя их ребрами (i, k) и (/, t). Заметим, что в новом туре некоторые ребра, может быть, придется проходить в обратном направлении.

Примените это преобразование для построения эвристического алгоритма в задаче коммивояжера. г