Московский государственный университет им М.В. Ломоносова
Мехманико - математический факультет
Кафедра математической логики и теории алгоритмов
Наливайко Павел Владимирович
«История изучения теории потоков в сетях»
Реферат по истории математики
Научный руководитель: проф. Верещагин Н.К.
____________________
Ведущий семинары: к.ф.н. Катречко С.Л.
____________________
Москва, 2008
Оглавление
Введение
Теория потоков в сетях – одно из современных направлений развития компьютерных наук в целом, и теории графов в частности. Многие комбинаторные задачи и линейные программы могут быть сформулированы и эффективно решены в терминах потоков.
Сеть представляет собой специальный вид графа. Сеть состоит из вершин и ребер. В практических задачах каждая вершина сети соответствует фабрике, складу, компьютеру, географическому или какому-либо другому объекту. Ребро соединяет пару вершин, в соответствии с дорогами, кабелями или другими каналами связи. В теории потоков, каждое ребро имеет пропускную способность, которая ограничивает количество информации (грузов, товаров...) которое может быть одновременно переправлено по этому ребру. В сети также выделены терминальные вершины. Они могут быть двух типов – источники и стоки.
Наглядно сеть можно представить себе как разветвленный трубопровод. Вершинами будут начала (источники) и концы (стоки) трубопровода, а также промежуточные узловые точки. Ребрами – трубы. Поток в сети соответствует жидкости, перемещаемой по трубопроводу.
Поток в сети, с формальной точки зрения, это неотрицательная вещественнозначная функция, определенная на ребрах сети, обладающая дополнительными условиями консервативности (для каждой нетерминальной вершины сумма потока по входящим ребрам равна сумме потока по исходящим) и подчиненности пропускным способностей (поток по ребру не превышает его пропускной способности).
Первая, и самая естественная задача теории потоков – это организовать поток так, чтобы доставлять наибольшее количество потока из источника в сток. Эта задача получила название задачи о максимальном потоке.
С потоками в сетях тесно связана задача о паросочетании в двудольном графе. Эта задача возникла раньше, однако, является частным случаем задачи о максимальном потоке.
Далее в данной работе мы проследим за развитием исследований в этих областях. Мы постараемся понять, какие были мотивы у ученых для поиска решений этих задач.
Основные источники данной работы являются англоязычными. Более того, для многих терминов в русскоязычной литературе даже нет устоявшегося перевода. В таких случаях мы будем в скобках указывать англоязычный термин.
Для чего нужны быстрые алгоритмы?
Эффективность алгоритма принято измерять асимптотической оценкой времени работы алгоритма в зависимости от параметров исходной сети. (Употребляется также термин «сложность алгоритма» - «complexity» в англоязычной литературе.) Основным параметром является число вершин исходной сети (так как число ребер в большинстве практических задач не превосходит квадрата числа вершин). Алгоритмы, время работы которых не превосходит некоторого полинома от размера исходной сети (числа вершин), называются полиномиальными. Как правило, полиномиальные алгоритмы возможно эффективно реализовать на практике. Напротив, алгоритмы, так или иначе использующие перебор большого числа вариантов, по своей сложности обычно бывают экспоненциальными.
Начнем с рассмотрения простого примера, наглядно иллюстрирующего пользу теоретических исследований в области компьютерных наук. Пусть в памяти компьютера имеется N целых чисел, и необходимо расположить их в порядке возрастания. (Данная задача называется задачей сортировки). Рассмотрим следующий алгоритм: выберем среди данных чисел наименьшее, поставим его на первое место. Затем из оставшихся чисел снова выберем наименьшее, и поставим его на второе место. И так далее. Очевидно, что данный алгоритм решает задачу сортировки. Но насколько он эффективен? Несложно показать, что данному алгоритму требуется порядка N^2 действий. (Данная оценка называется асимптотикой работы алгоритма, и с помощью O-символики данный факт записывается так: сложность алгоритма есть O(N^2) ).
Предположим что N = 10^8. Современный однопроцессорный компьютер способен выполнять порядка ста миллионов элементарных операций (присваивание, сложение, вычитание...) в секунду. Таким образом, для сортировки данного набора чисел потребуется порядка (10^8)^2 / 10^8 = 100 миллионов секунд, или около трех лет.
В то же время, известны алгоритмы решения задачи сортировки со сложность O(NlogN). Самые известные из них – это алгоритм пирамидальной сортировки (heap sort) и «быстрая» (quick sort) сортировка Хоара (последняя, впрочем, имеет лишь время работы O(NlogN) «в среднем»). При N = 10^8 время работы таких алгоритмов получается около 30 секунд!
На примере данной задачи видно, что дополнительные исследования в алгоритмической области могут сократить объемы вычислений на порядки, за считанные секунды решить задачу, которая ранее с практической точки зрения казалась неразрешимой.
Глава 1. История изучения теории потоков
§1.1. Начало исследований
Впервые проблемы связанные с пересылкой потоков в сетях были рассмотрены Канторовичем в 1933 году. (Более того – он рассматривал более общую задачу с движением потока жидкостей различных типов (multicommodity flows)). Основы теории потоков были заложены в период с ноября 1954 по декабрь 1955 года исследователями корпорации RAND (Санта-Моника, Калифорния). Проследим за развитием теории потоков в хронологическом порядке по отчетам RAND.
Первый отчет «Максимальный поток в сети» датируется 19м ноября 1954 года. Авторы отчета – Форд (Ford) и Фалкерсон (Fulkerson), доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера (Robacher) было упомянуто, что впервые эту теорему доказал Фалкерсон.
Работа Форда и Фалкерсона о потоках и разрезах была мотивирована изучением транспортных сетей железных дорог (см. далее). В том же отчета они также описали простой алгоритм нахождения максимального потока для планарных графов, обладающих следующим дополнительным свойством: после добавления дуги из источника в сток граф остается планарным.
Более того, авторы заметили, что задача о максимальном потоке является частным случаем задачи линейного программирования, а стало быть, может быть решена симплекс-методом Данцига (Danzig). В отчете от 1 января 1955 года, Данциг и Фалекрсон показали, что теорема о максимальном потоке и минимальном разрезе может быть выведена из теоремы о сильной двойственности для задач линейного программирования (в работе упоминалось, что этот факт установлен Хоффманом (Hoffman)). Более того, было доказано существование максимального целочисленного потока, для сетей пропускные способности которых являются целочисленными. Следствием этого факта является известная теорема Менгера (Menger) о непересекающихся путях. 1 апреля 1955 года Данциг и Фалкерсон описали простой способ вычисления максимального потока основанный на симплекс-методе. 26 мая 1955 года Робахер независимо доказал теорему о максимальном потоке и минимальном разрезе, сведя ее к теореме Менгера.
§1.2. Эвристика Болдырева
До тех пор пока существующие алгоритмы вычисления максимального потока основывались на симплекс-методе, одной из важнейших задач в теории потоков было построение комбинаторного алгоритма решения этой задачи. 3 июня 1955 года в Нью-Йорке на встрече Американского Общества Исследования Операций Болдырев сделал доклад (опубликованный затем как отчет RAND от 5 августа 1955 года) об эвристическом алгоритме нахождения максимального потока. Метод Болдырева является так называемым «жадным алгоритмом»: он пытается послать как можно больше потока из источника, до тех пор, пока не обнаружится критическая вершина (т.е. такая вершина из которой невозможно передать поток далее). Такая ситуация устраняется путем возвращения избыточного потока в источник. По словам Болдырева, основные достоинства его метода заключались в том, что: