Часть 2. Оптимизация на графах

Под дискретной оптимизацией понимается оптимизация числовых функций, заданных на конечных множествах. В терминологии раздела 3.5 такие функции называются функциями типа A → R, где A – конечное множество, R – множество всех вещественных чисел. Трудно рассчиты-вать на какую-либо теорию для столь широкого класса задач. Поэтому обычно рассматривают-ся специальные подклассы задач, которые, с одной стороны, вызывают практический интерес, и, с другой стороны, поддаются решению при реальных размерностях.

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

Представляется важным начать эту часть с достаточно подробного определения и описа-ния основных рассматриваемых в ней объектов - ориентированных и неориентированных гра-фов. Этому посвящена 1-ая глава. Во 2-ой главе рассмотрена одна из наиболее известных и хо-рошо исследованных задач оптимизации на графах – классическая задача поиска максимально-го потока. В 3-ей главе рассмотрена не менее знаменитая задача о кратчайших путях между вер-шинами и описаны два существенно различных подхода к её решению – алгоритм Дейкстры и алгоритм Флойда-Уоршалла. В 4-ой главе рассмотрена почти также знаменитая задача о паро-сочетаниях в двух оптимизационных постановках – о максимальном паросочетании и о назна-чении; подходы к их решению основаны на алгоритмах, ранее рассмотренных этой части: пото-ковом алгоритме и алгоритме нахождения циклов отрицательной длины. В 5-ой главе рассмат-ривается одна из центральных задач дискретной оптимизации – многошаговая задача. Эта об-щая задача эквивалентна задаче нахождения пути максимальной стоимости на графе, что и по-служило одним из оснований включения этой задачи в данную часть пособия. Рассмотрены так-же некоторые важные модификации общей постановки.

Центральное место в этой части пособия занимают классические алгоритмы нахождения максимального потока, кратчайшего пути, эффективного назначения и пр. Практически во всех случаях предложены таблицы и простые правила их последовательного заполнения, позволяю-щие «вручную» решать упомянутые задачи в небольшой размерности (но всё же в такой, при которой решение прямым перебором является затруднительным). Представляется, что именно такая работа с алгоритмами позволяет действительно понять, как они «работают» не только на чисто формальном, но и на содержательном уровне.

Дата добавления: 2015-10-16