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

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

Авторы: Бойков Владимир Алексеевич ЧИТАТЬ PDF
Бойков В.А. О применении жадных алгоритмов в некоторых задачах дискретной математики / В.А.Бойков // Программные продукты и системы. – 2019. – Т.32. – №1. – С. 55-62. – DOI: 10.15827 / 0236-235X.125.055-062.

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

Объектами исследования, проведенного в данной работе, являются жадные алгоритмы, примененные к решениям таких задач.

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

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

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

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


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