Software & Systems

Впервые жадный алгоритм (greedy algorithm) – алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, был описан в работе по комбинаторной оптимизации [1]. Поток исследований, последовавших за этой публикацией, обобщен в работах [2, 3]. Основным направлением исследования являлось выявление задач, в которых оптимальное решение получалось жадными алго- ритмами. Приводилось обоснование оптимальности жадных алгоритмов для их решения. В одной из последних фундаментальных книг рассматриваются приложения жадных алгоритмов для получения оптимальных решений [4]. В частности, рассматриваются такие задачи, как планирование заданий и построение кодов Хаффмана в теории кодирования.

Пример парадоксального решения транспортной задачи

Поводом для данного исследования послужил пример парадокса, возникающего при решении одной транспортной задачи малой размерности [5].

Постановка транспортной задачи заключается в следующем. Имеются два пункта (A1, A2) производства продукции и два пункта (B1, B2) потребления этой продукции. Объемы производства (предложения) продукции в пунктах Ai равны ai (i = 1, 2). Объемы потребле- ния (спроса) продукции в пунктах Bj равны bj (j = 1, 2). Заданы удельные затраты на перевозку единицы продукции cij (i = 1, 2, j = 1, 2) по маршруту из пункта Ai в пункт Bj.

Обозначим xij (i = 1, 2, j = 1, 2) объем продукции, перевозимой из пункта Ai в пункт Bj.

Требуется спланировать объемы перевозок по заданным маршрутам из пунктов A1 и A2 в пункты B1 и B2 так, чтобы суммарные затраты на все перевозки были минимальными, то есть требуется найти такие объемы перевозок, которые обеспечивают минимум функции:                  (1)

Здесь Х – таблица (матрица), составленная из величин объемов перевозок по заданным маршрутам,.

При этом требуется, чтобы объемы перевозок удовлетворяли условиям

                        (2)

(xij ³ 0, i, j = 1, 2).

Первые два равенства означают, что вся продукция из пунктов A1 и A2 вывезена. Два равенства, записан- ные во второй строке, означают, что в пункты B1 и B2 завезена продукция в требуемом объеме. Интерпретация условий неотрицательности на объемы перевозок очевидна.

Чтобы удовлетворить весь спрос, необходимо и достаточно, чтобы суммарный спрос был равен суммарному предложению, то есть должны выполняться условия баланса:

a1 + a2 = b1 + b2.                                                       (3)

Обсудим решение транспортной задачи жадным алгоритмом – методом минимальной стоимости (ММС), которое многим покажется естественным или интуитивно очевидным. Опишем это решение по шагам для исходных данных из [5]:

Шаг 1. Найдем маршрут минимальной стоимости, то есть соответствующий минимальному элементу матрицы С, а именно: mincij = c21 = 8; i = 2, j = 1.

Тогда из пункта A2 в пункт B1 планируем перевозку: x21 : = min{a2, b1} = min{7, 4} = 4.

Пересчитываем величины спроса на продукцию и остатков продукции:

b1 : = b1 – 4 = 4– 4 = 0, a2 : = a2 – 4 = 7– 4 = 3.

Поскольку в пункт B1 продукция завезена полностью, из пункта A1 в пункт B1 уже ничего везти не надо. Поэтому полагаем x11: = 0.

Итак, в матрице перевозок Х остаются незаполненными элементы второго столбца x12, x22; .

Шаг 2. Как и на первом шаге, в матрице С найдем минимальный элемент, соответствующий этим перевозкам, то есть min{c12, c22} = min{16, 10} = 10 = c22; i = 2, j = 2.

Это означает, что из пункта A2 в пункт B2 планируем перевозку по тому же правилу:

x22 : = min{a2, b2} = min{3, 7} = 3.

Пересчитываем величины спроса на продукцию и остатков продукции:

b2 : = b2 – 3 = 8 – 3 = 5, a2 : = a2 – 4 = 3 – 3 = 0.

В матрицу перевозок Х записываем найденную перевозку x22 = 3. Остается незаполненным элемент x12; .

Шаг 3. Минимальный элемент матрицы С, соответствующий незаполненному элементу матрицы Х, есть элемент c12. Элемент x12 заполняем по тому же правилу: x12: = min{a1, b2} = min{5, 5} = 5.

Пересчитываем величины спроса на продукцию и остатков продукции:

b2 : = b2 – 5 = 5– 5 = 0, a1 : = a1 – 5 = 5 – 5 = 0.

Как видим, вся продукция из пунктов A1 и A2 вывезена в тех объемах, в которых она там произведена. В пункты B1 и B2 завезено столько продукции, сколько требовалось. Это свойство следует из равенства сум- марного спроса и суммарного предложения (3).

Получили план перевозок, который обозначим как .

Вычислим суммарные затраты на запланированные объемы перевозок: f(XММС) = с11×x11 + с12×x12 + + с21×x21 + с22×x22 = 12×0 + 16×5 + 8×4 + 10×3 = 142.

Описанный метод получения плана перевозок называется ММС.

Проверим оптимальность решения задачи. Продемонстрируем, как легко и наглядно получается наилучший план перевозок с использованием математического пакета Mathcad. Приведем решение рассмотренной транспортной задачи в Mathcad (табл. 1).

 Таблица 1

Программа Mathcad. Решение транспортной задачи

Table 1

Mathcad. The solution of a transportation problem

Обратим внимание, что значение суммарных затрат на перевозку грузов по плану, построенному пакетом Mathcad, получилось меньше, чем при решении ММС, а именно: f(XММС) = 142 > 134 = f(Xopt).

Кроме того, в оптимальном плане перевозок перевозка по маршруту минимальной стоимости не осу- ществляется (с21 = 8, но ).

Проверим, действительно ли решение, полученное компьютером, оптимальное. Для вычислителей, использующих компьютер для решения каких-либо задач, возникает вопрос о достоверности ответа.

Для этого часто используются необходимые и достаточные условия оптимальности. Условия оптимальности для транспортной задачи с m пунктами производства продукции и n пунктами потребления продукции приведены ниже.

Теорема [6]. Для оптимальности плана перевозок  в транспортной задаче необходимо и достаточно, чтобы существовали числа ui и vj (), называемые потенциалами, такие, чтобы выполнялись условия:

а) для  выполняются равенства ui + vj = cij;

б) для остальных  выполняются неравенства ui + vj £ cij.

Проверим, является ли найденный план XММС оптимальным. В данном случае m = 2, n = 2.

Заметим, что неизвестных четыре (u1, u2, v1, v2), а положительных перевозок в плане Xopt три (x11 = 4, x12 = 1, x22 = 7). То есть условия а) задают систему трех линейных уравнений (по количеству положительных перевозок) с четырьмя неизвестными. Общее решение такой системы линейных уравнений зависит от одной переменной, значения которой можно назначать произвольно.

Составим систему линейных уравнений а) для полученного плана Xopt, выданного компьютером:

Положив в 1-м и 2-м уравнениях u1 = 0, получаем потенциалы v1 = 12, v2 = 16. Из третьего уравнения следует u2 = 10 – v2 = 10 – 16 = – 6. 

Проверим условие б) для нулевой перевозки x21 = 0. Оказывается, что u2 + v1 = – 6 + 12 = 6 < c21 = 8. Это означает, что данный план перевозок Xopt является оптимальным в рассматриваемой транспортной задаче, то есть минимизирует суммарную стоимость перевозок.

Итак, выяснили, что ММС не дает оптимального решения транспортной задачи сразу. Этот метод используется лишь для получения начального плана перевозок, который затем по шагам преобразуется в оптимальный план специальными вычислительными методами, например, методом потенциалов [7].

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

Таким образом, очевидно, что имеются такие транспортной задачи, оптимальное решение которых не дает маршрут минимальной стоимости. В рассмотренном примере такой маршрут один – x21.

Применение жадных алгоритмов в задаче о кратчайшем пути

Рассмотрим пример (рис. 1). Пусть имеются 10 городов. Номера городов на схеме указаны в кружках. Стрелки означают дороги (пути возможных переходов из города в город), а числа над/под стрелками – длины соответствующих дорог (расстояния между городами). Требуется найти кратчайший путь из города 1 в город 10.

Попытаемся решить эту задачу жадным алгоритмом – методом ближайшего города (МБГ) (рис. 2). Маршрут № 1, полученный этим методом, на рисунке обозначен жирными стрелками.

Длина пройденного пути  = 2 + 4 + 3 + 4 = 13.

Эту же задачу можно решить, например, методом динамического программирования Р. Беллмана [8].

Оптимальные последовательности прохождения городов (маршруты 2, 3, 4 соответственно) представлены на рисунке 3.

Справа от оптимальных траекторий выписаны оптимальные значения F*2, F*3, F*4 суммарных пройденных расстояний по соответствующим маршрутам.

Итак, с помощью жадного алгоритма МБГ не удалось сразу получить оптимальный маршрут для перехода из города 1 в город 10 (13 =  > F* = 11).

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

Рассмотрим задачу о поиске кратчайшего пути из точки А в точку В по сети дорог, соединяющих конечное множество заданных точек.

Контрпример 1. Даны точки А, В, С, M, соединенные дорогами, которые обозначены сплошными линиями (рис. 4). Пунктирный отрезок АВ не входит в заданную сеть дорог. Требуется найти кратчайший путь из точки А в точку В. Действуя жадным алгоритмом, из точки А переходим в ближайшую точку С и проигрываем, так как, несмотря на то, что АС < AM, выполняется неравенство АС + СM + MВ > АM + MВ.

Жадных решателей не спасает и алгоритм расчета на два хода вперед.

Контрпример 2. Заданы точки А, В, С, D1, D2, М, соединенные дорогами, которые обозначены сплошными линиями (рис. 5). Пунктирный отрезок АВ не входит в заданную сеть дорог. Требуется найти кратчайший путь из точки А в точку В по существующей сети дорог. Рассмотрим сеть дорог, такую, что

AD1 + D1D2 < AC + СM,                                         (4)

но AD1 + D1D2 + D2M + MB > AC + СM + MB.         (5)

Жадный решатель, находящийся в точке А, вычисляет сумму расстояний на два хода вперед. Убеждается, что выполняется неравенство (4), осуществляет переход из точки А в точку D2 и, очевидно, проигры- вает по сумме пройденного расстояния из точки А в точку В (см. неравенство (5)).

Жадных решателей не спасает и алгоритм расчета на n (n > 2) ходов вперед.

Контрпример 3. Заданы точки А, D1, D2, …, Dn–1, Dn, М, В, C1, C2, …, Cn–1, соединенные дорогами (рис. 6). Дороги обозначены сплошными линиями, пунктирами – дороги из точки D2 в Dn–1 и из точки C2 в Cn–1. Пунктирный отрезок АВ не входит в заданную сеть дорог. Требуется найти кратчайший путь из точки А в точку В по существующей сети дорог. По аналогии с предыдущими примерами построим такую сеть дорог, что выполняются два неравенства:

AD1 + D1D2 + … + Dn–1 Dn <

< AC1 + С1C2 + … + Сn–1M,                                    (6)

но AD1 + D1D2 + … + Dn–1Dn + DnM + MB >

> AC1 + С1C2 + … + Сn–1M + MB.                          (7)

И в этом случае жадный решатель, находящийся в точке А, вычисляет сумму расстояний на п ходов вперед, убеждается, что выполняется неравенство (6), и осуществляет переход из точки А в точку Dп и, очевидно, проигрывает по сумме пройденного расстояния из точки А в точку В (см. неравенство (7)).

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

Использование жадного алгоритма в задаче коммивояжера

Постановка задачи коммивояжера. Имеются n городов (точек). Задана матрица расстояний между городами C[n´n] = (cij), где cij – расстояние между городами i и j (i, j = ). Выехав из одного города, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в исходный город, то есть маршрут должен быть замкнутым. Такие маршруты называются гамильтоновыми циклами.

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

Суммарное пройденное расстояние по гамильтонову циклу и требование его минимизации можно записать в виде

.             (8)

Минимум ищется по всем перестановкам (i1, i2, …, in) номеров городов (1, 2, …, n). Количество таких перестановок равно n!. Количество различных гамильтоновых циклов в n раз меньше, то есть (n – 1)!.

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

Формализация задачи коммивояжера как задачи математического программирования

Введем переменные, отражающие факт перехода из точки i в точку j:

  (9)

где .

Тогда задача ставится следующим образом [9].

Найти значения булевых переменных xij, которые удовлетворяют условиям

                          (10)

с ограничениями вида

                             (11)

                             (12)

.          (13)

Будем считать, что все cii = +¥,  cij ³ 0 и, вообще говоря, cij ¹ cji.

Ограничения (11) и (12) означают, что из каждой точки можно выйти и войти в каждую точку ровно один раз. Ограничения (13) гарантируют невозможность распадения гамильтонова цикла на несвязные циклы.

Задача (9)–(13) представляет собой задачу булева линейного программирования.

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

Замечание. Поскольку оптимальные значения элементов матрицы X = Xopt получились булевыми, ограничения (9) выполнились автоматически.

Рассмотрим решение задачи методом ветвей и границ [10]. Для решения задачи коммивояжера этот метод был предложен в 1963 году американскими математиками Литтл, Мурти и др. (Little, Murty, Sweeney, Karel).

Идея метода ветвей и границ применительно к задаче коммивояжера проста.

Табица 2

Программа Mathcad. Решение задачи коммивояжера

Table 2

Mathcad. The solution of the traveling salesman problem

Ветвление основано на следующем соображении: проезд из любого города i в любой другой город j мо- жет либо принадлежать оптимальному циклу, либо не принадлежать. В процессе решения необходимо сделать вывод – принадлежит ли путь из города i в другой город j оптимальному циклу. Для этого используется понятие границы, которая позволяет сделать отсев неперспективных гамильтоновых циклов. Этот прием часто позволяет избежать полного перебора вариантов, то есть уменьшить количество вычислений. Однако метод ветвей и границ не гарантирует, что процесс решения задачи коммивояжера не сведется к полному перебору всех возможных гамильтоновых циклов.

Изложим идею метода ветвей и границ с использованием аналога метода минимальной стоимости для решения транспортной задачи. Для задачи коммивояжера аналог этого метода – МБГ.

Первый этап. Построение гамильтонова цикла с помощью МГБ.

Шаг 1. В матрице С найдем минимальный элемент. В данном случае mincij = c13 = 1 (i = 1, j = 3). Это означает, что для первого города ближайшим к нему является третий город. Составим список городов, в которых уже побывали, A ={1, 3}, и список городов, в которых еще не были, B ={2, 4}.

Очевидно, A È B = {1, 2, 3, 4} – множество всех городов. Контролировать состояние двух списков необходимо для предотвращения преждевременного возвращения в исходный город.

Шаг 2. Из третьего города переходим в ближайший город среди тех городов, в которых еще не были. Находим  (j = 2), то есть из третьего города переходим во второй.

Обновляем списки городов А и В: A ={1, 3, 2}, B = {4}.

Шаг 3. Из второго города переходим в ближайший город среди тех городов, в которых еще не были. Находим  (j = 4), то есть из второго города переходим в четвертый.

Обновляем списки городов А и В: A ={1, 3, 2, 4}, B = {Æ}.

Шаг 4. Из четвертого города переходим в первый, так как все города пройдены (множество В не содержит элементов), то есть наступил момент возвращения в исходный город.

Шаг 5. Подсчитываем длину l пройденного пути по построенному маршруту (1, 3, 2, 4): l(1, 3, 2, 4) = = c13 + c32 + c24 + c41 = 1 + 3 + 3 + 8 = 15. M: = 15.

Число М объявим верхней границей для искомой минимальной длины гамильтонова цикла.

Очевидно, что минимум среди всех длин гамильтоновых циклов удовлетворяет неравенству

Итак, с помощью МБГ найдена оценка сверху для оптимального значения целевой функции.

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

На рисунке 7 представлено дерево ветвления вариантов построения гамильтоновых циклов.

Левая ветка дерева построена с помощью МБГ. Начав движение из города 1, последовательно переходим через города 3, 2, 4 и, пройдя все города, возвращаемся в начальный город 1. При этом вычисляем длину пройденного пути (гамильтонова цикла). Она равна 15.

Эту величину принимаем за оценку сверху (границу) для дальнейшего перебора вариантов (M = 15).

Рассмотрим ветку построенного дерева (1 ® 3 ® ® 4 ® 2). При этом на каждом переходе от города к городу вычисляем накопленную сумму пройденного пути (l = 1 + 9 + 7 = 17 > M Þ stop). Поскольку получена величина, большая оценки сверху, дальнейшее продолжение этого маршрута нецелесообразно.

Следующая ветка для рассмотрения (1 ® 4). Для этой ветки имеем (l = 16 > M Þ stop), потому и ее отбрасываем как неперспективную.

Рассмотрим ветку дерева (1 ® 2 ® 3 ® 4). Для нее получаем (l = 3 + 4 + 9 = 16 > M Þ stop). Снова отбрасываем ветку как неперспективную.

Осталась последняя ветка дерева (1 ® 2 ® 4 ® ® 3 ® 1). Обратим внимание, что накопленная сумма пройденных расстояний равна (l = 3 + 3 + 6 + 2 = 14 < < M Þ opt). В этом случае оказалось, что установлен рекорд – сумма пройденного пути меньше предыдущего рекорда.

Обновляем величину рекорда (верхняя граница) (M: = l = 14). Если бы дерево вариантов имело больше веток, для отсева неперспективных вариантов использовалось бы уже обновленное значение верхней гра- ницы. Поскольку рассмотрены все варианты, послед- ний гамильтонов цикл оптимальный.

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

В данном примере жадный алгоритм (МБГ) дал неплохую верхнюю границу длины гамильтонова цикла.

Оценим выигрыш от применения данного метода для решения рассмотренной задачи коммивояжера. Будем считать, что трудоемкость решения задачи определяется количеством сложений для вычисления длины цикла. Количество сложений при полном переборе вариантов равно количеству дуг графа 4! = 24. В рассматриваемом случае затрачено 16 сложений, что составляет примерно 66,7 % от общего числа вариантов. Однако метод ветвей и границ не дает гарантии, что не придется осуществлять полный перебор вариантов.

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

Литература

1.     Edmonds J. Matroids and the greedy algorithm. Math. Programming, 1971, vol. 1, no. 2, pp. 127–136.

2.     Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность; [пер. с англ.]. М.: Мир, 1984. 510 с.

3.     Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы; [пер. с англ.; под ред. А. Шеня]. М.: МЦНМО, 2014. 320 с.

4.     Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ; [пер. с англ.]. М.: Вильямс, 2013. 1328 с.

5.     Очков В.Ф., Богомолова Е.П., Иванов Д.А. Физико-математические этюды с Mathcad и Интернет. СПб: Лань, 2016. 388 с.

6.     Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. Задачи транспортного типа. М.: Либроком, 2010. 184 c.

7.     Грешилов А.А. Прикладные задачи математического программирования. М.: Логос, 2006. 288 с.

8.     Беллман Р. Динамическое программирование; [пер. с англ.; под ред. Н.Н. Воробьева]. М.: Иностран. лит-ра, 1960. 400 с.

9.     Костевич Л.С., Лапко А.А. Исследование операций. Теория игр. Минск: Выш. шк., 2008. 368 с.

10.  Таха Х.А. Введение в исследование операций; [пер. с англ.]. М.: Вильямс, 2005. 912 с.

References

1. Edmonds J. Matroids and the greedy algorithm. Math. Programming. North-Holland Publ. Co. 1971, vol. 1, no. 2,
   pp. 127–136.
2. Papadimitriou Ch.H., Steiglitz K. Combinatorial optimization: Algorithms and Complexity. Dover Publ., 1998, 528 p.
   (Russ. ed.: Moscow, Mir Publ., 1984, 510 p.).
3. Dasgupta S., Papadimitriou Ch.H., Vazirani U. Algorithms. Science Engineering & Math Publ., 2011, 336 p. (Russ. ed.:
   Shen A. Moscow, MCCME Publ., 2014, 320 p.).
4. Cormen Th.H., Leiserson Ch.I., Rivest R.L., Stein Cl. Introduction to Algorithms. 3rd ed., The MIT Press, 2009, 1312 p.
   (Russ. ed.: Moscow, Vilyams Publ., 2013, 1328 p.).
5. Ochkov V.F., Bogomolova E.P., Ivanov D.A. Physics and Mathematics with Mathcad and the Internet. St. Petersburg, Lan Publ., 2016, 388 p.
6. Yudin D.B., Golstein E.G. Problems and Methods of Linear Programming. Transport Problems. Moscow, Librokom Publ., 2010, 184 p.
7. Greshilov A.A. Applied Problems of Mathematical Programming. 2nd ed., Moscow, Logos Publ., 2006, 288 p.
8. Bellman R.E. Dynamic Programming. Princeton Univ. Press, 1957 (Russ. ed.: Moscow, 1960, 400 p.).
9. Kostevich L.S., Lapko A.A. Operations Research. Game Theory. 2nd ed., Minsk, Vysh. shk. Publ., 2008, 368 p.
10. Taha H.A. Operations Research: An Introduction. 7th ed. Prentice Hall, 2002 (Russ. ed.: Moscow, Villiams Publ., 2005,
    912 p.).