ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Добавить в закладки

Следующий номер на сайте

3
Ожидается:
16 Сентября 2019

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

On the application of greedy algorithms in some problems of discrete mathematics
Дата подачи статьи: 2018-12-05
УДК: 519.6
Статья опубликована в выпуске журнала № 1 за 2019 год. [ на стр. 055-062 ]
Аннотация:Алгоритмы, основанные на идее локальной оптимальности, кажутся естественными и являются соблазном при решении задач оптимизации. Однако задачи оптимизации, которые будут рассмотрены в данной статье, многошаговые, а получение жадными алгоритмами оптимального решения в многошаговых задачах, вообще говоря, не гарантировано. Это будет показано на примерах решения транспортной задачи, задачи о кратчайшем расстоянии между городами на заданной сети дорог и задачи коммивояжера. Объектами проведенного исследования являются жадные алгоритмы, примененные к решениям таких задач. В работе приводится пример парадоксального решения одной транспортной задачи малой размерности. При ее решении одним из жадных алгоритмов строится план перевозок продукции. Однако этот план не является оптимальным и обладает парадоксальным свойством. А именно: по маршруту, который оказывается самым дешевым в оптимальном плане, перевозка не осуществляется. Оптимальное решение рассмотренной задачи достигается с помощью пакета Mathcad. На примере задачи о кратчайшем расстоянии показано, что жадный алгоритм тоже не приводит к оптимальному пути. А три контрпримера на евклидовых графах показывают, что, вообще говоря, невозможно получить оптимальный марш-рут даже при расчете вариантов на несколько шагов вперед. В качестве третьего примера применения жадного алгоритма для решения задачи коммивояжера рассматривается метод ближайших городов. С его помощью описывается последовательное построение гамильтонова цикла. Приведенная версия алгоритма застрахована от получения несвязных графов в процессе решения. Далее длина полученного гамильтонова цикла используется как верхняя оценка при реализации простейшей версии метода ветвей и границ. Опти-мальность полученного решения проверяется с помощью программы, выполненной в пакете Mathcad. В рассмотренных примерах решения, полученные с помощью жадных алгоритмов, используются в качестве начального приближения для дальнейшей оптимизации целевой функции.
Abstract:The algorithms that are based on the idea of local optimality seem natural and tempting when solving optimization problems. However, the optimization problems discussed in the paper are multistage. In this case, the obtaining an optimal solution in a multistage problem by greedy algorithms is not guaranteed generally. This fact is demonstrated by the examples of solving a transport problem, the problem of the shortest distance between cities on a given road network, and the traveling salesman prob-lem. The research objects are greedy algorithms applied to solving the same problems described in this paper. The paper gives an example of a paradoxical solution of a small dimension transportation problem. When solving the prob-lem, one of greedy algorithms constructs a product transportation plan. However, this plan is not optimal and has a paradoxical property. Namely, no transportation by the route that is the cheapest in the optimal plan. The optimal solution of the considered problem is given by mathematical package Mathcad. The fact that the greedy algorithm does not show the optimal path is shown on the example of the shortest distance problem. Three counterexamples on Euclidean graphs show that it is impossible to obtain an optimal route even when calculating options several steps ahead. The third example of applying the greedy algorithm to solve the traveling salesman problem is the nearest city method. The method describes the sequential construction of the Hamiltonian cycle. The above version of the algorithm is secured from ob-taining non-connected graphs during a solution process. Further, the length of the Hamiltonian cycle is used as an upper bound when implementing the simplest version of the branch and bound method. The program made in Mathcad checks the optimality of the obtained solution. In the considered examples, the solutions obtained by greedy algorithms are used as an initial approximation for further op-timization of the target function.
Авторы: Бойков В.А. (vboykov@inbox.ru) - Одинцовский филиал МГИМО МИД России (старший научный сотрудник), Одинцово, Россия, кандидат физико-математических наук
Ключевые слова: метод ветвей и границ, задача коммивояжера как задача математического программирования, задача коммивояжера, задача о кратчайшем расстоянии, парадоксальное решение транспортной задачи, транспортная задача, жадный алгоритм
Keywords: branch and bound method, traveling salesman problem as a mathematical programming problem, traveling salesman problem, shortest distance problem, paradoxical solution of the transport problem, vehicle routing problem, greedy algorithms
Количество просмотров: 630
Статья в формате PDF
Выпуск в формате PDF (6.60Мб)

Размер шрифта:       Шрифт:

Впервые жадный алгоритм (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

Комментарий

ORIGIN := 1

Встроенная функция Mathcad, задающая минимальные значения индексов матрицы

Исходные данные транспортной задачи

Формула вычисления суммарных транспортных затрат

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

Given

Начало блока решения задач

Ограничения для транспортной задачи. Неравенство означает, что все элементы матрицы Х больше или равны нулю

Вызов функции Minimize, которая находит такую матрицу Х, которая минимизирует функцию f.

Xopt := присвоение оптимальной матрицы

f(Xopt) = 134

Вычисление значений суммарных затрат для матрицы перевозок Xopt

Обратим внимание, что значение суммарных затрат на перевозку грузов по плану, построенному пакетом 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 >

Dn> 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

Оператор Mathcad

Комментарий

ORIGIN := 1

Встроенная функция Mathcad, задающая минимальные значения индексов матрицы

Исходные данные:

C – матрица расстояний между городами; w – большое число; X – начальное значение матрицы исходных маршрутов; u – вспомогательные переменные

Формула вычисления суммарной длины гамильтонова цикла для матрицы маршрутов Х – формула (9)

Given

Начало блока решения задач

Ограничения (10)–(12) для задачи коммивояжера без условий булевости элементов матрицы X (n = 4, n – 1 = 3)

Вызов функции Minimize, находящей такую матрицу Х, которая минимизирует функцию f.

Xopt := присвоение оптимальной матрицы маршрутов.

Вычисление значений суммарной длины оптимального гамильтонова цикла (Xopt)

Вычисление значений суммарной длины оптимального гамильтонова цикла, полученного МБГ

Ветвление основано на следующем соображении: проезд из любого города 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.).

Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=4556&lang=
Версия для печати
Выпуск в формате PDF (6.60Мб)
Статья опубликована в выпуске журнала № 1 за 2019 год. [ на стр. 055-062 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: