Реферат по истории математики Научный проф. Верещагин Н. К



Столичный муниципальный институт им М.В. Ломоносова

Мехманико - математический факультет

Кафедра математической логики и теории алгоритмов


Наливайко Павел Владимирович


«История исследования теории потоков в сетях»

Реферат по истории арифметики


Научный управляющий: проф. Верещагин Н.К.

____________________


Ведущий семинары: к.ф.н Реферат по истории математики Научный проф. Верещагин Н. К. Катречко С.Л.


____________________


Москва, 2008

Оглавление

Введение.

3

Зачем необходимы резвые методы?

4

Глава 1. История исследования теории потоков

  • Начало исследовательских работ

  • Эвристика Болдырева

  • Отчет Харриса-Росса

  • Способ Форда-Фалекрсона

  • Метод Эдмондса-Карпа

  • Последующие улучшения метода построения наибольшего потока

  • Хронологическая таблица Реферат по истории математики Научный проф. Верещагин Н. К результатов

6

^ Глава 2. Теория паросочетаний

  • Паросочетание в двудольном графе

  • Аксиома Фробениуса

  • Аксиомы Менгера и Кёнига

  • Связь меж потоками и паросочетаниями

13

^ Глава 3. Задачка о назначениях: «взвешенный» вариант задачки о паросочетаниях

  • Монж: среднее предназначение

  • Аксиома Эгервари

  • 1940е годы

  • Ранешние 1950е

  • Вычислительные результаты начала 1950х

  • Венгерский способ Куна Реферат по истории математики Научный проф. Верещагин Н. К-Манкреша

16

^ Глава 4. Последующие исследования в теории потоков

  • Потоки малой цены

  • Динамические потоки. Задачка транспортировки

  • Универсально-максимальные динамические потоки

  • Наибыстрейшие потоки

21

Заключение

25

Библиография

26






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


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


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



Рис. 1. Поток в сети. Иллюстрация из Реферат по истории математики Научный проф. Верещагин Н. К Wikipedia.

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

1-ая, и самая естественная задачка теории потоков – это организовать поток так, чтоб доставлять наибольшее количество потока из источника в Реферат по истории математики Научный проф. Верещагин Н. К сток. Эта задачка получила заглавие задачки о наивысшем потоке.


С потоками в сетях плотно сплетена задачка о паросочетании в двудольном графе. Эта задачка появилась ранее, но, является личным случаем Реферат по истории математики Научный проф. Верещагин Н. К задачки о наивысшем потоке.


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


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

^ Зачем необходимы резвые методы?
Эффективность метода принято определять Реферат по истории математики Научный проф. Верещагин Н. К асимптотической оценкой времени работы метода зависимо от характеристик начальной сети. (Употребляется также термин «сложность алгоритма» - «complexity» в английской литературе.) Главным параметром является число вершин начальной сети (потому что число ребер в Реферат по истории математики Научный проф. Верещагин Н. К большинстве практических задач не превосходит квадрата числа вершин). Методы, время работы которых не превосходит некого полинома от размера начальной сети (числа вершин), именуются полиномиальными. Обычно, полиномиальные методы может быть отлично воплотить Реферат по истории математики Научный проф. Верещагин Н. К на практике. Напротив, методы, так либо по другому использующие перебор огромного числа вариантов, по собственной трудности обычно бывают экспоненциальными.


Начнем с рассмотрения обычного примера, наглядно иллюстрирующего пользу теоретических исследовательских работ в области компьютерных Реферат по истории математики Научный проф. Верещагин Н. К наук. Пусть в памяти компьютера имеется N целых чисел, и нужно расположить их в порядке возрастания. (Данная задачка именуется задачей сортировки). Разглядим последующий метод: выберем посреди данных чисел меньшее, поставим его Реферат по истории математики Научный проф. Верещагин Н. К на 1-ое место. Потом из оставшихся чисел опять выберем меньшее, и поставим его на 2-ое место. И т.д.. Разумеется, что данный метод решает задачку сортировки. Но как он эффективен? Нетрудно показать Реферат по истории математики Научный проф. Верещагин Н. К, что данному методу требуется порядка N^2 действий. (Данная оценка именуется асимптотикой работы метода, и при помощи O-символики этот факт записывается так: сложность метода есть O(N^2) ).


Представим что N = 10^8. Современный однопроцессорный компьютер Реферат по истории математики Научный проф. Верещагин Н. К способен делать порядка 100 миллионов простых операций (присваивание, сложение, вычитание...) за секунду. Таким макаром, для сортировки данного набора чисел будет нужно порядка (10^8)^2 / 10^8 = 100 миллионов секунд, либо около 3-х лет.


В то же время, известны Реферат по истории математики Научный проф. Верещагин Н. К методы решения задачки сортировки со сложность O(NlogN). Самые известные из их – это метод пирамидальной сортировки (heap sort) и «быстрая» (quick sort) сортировка Хоара (последняя, вобщем, имеет только время работы O Реферат по истории математики Научный проф. Верещагин Н. К(NlogN) «в среднем»). При N = 10^8 время работы таких алгоритмов выходит около 30 секунд!


На примере данной задачки видно, что дополнительные исследования в алгоритмической области могут уменьшить объемы вычислений на порядки, за считанные секунды Реферат по истории математики Научный проф. Верещагин Н. К решить задачку, которая ранее с практической точки зрения казалась неразрешимой.

Глава 1. История исследования теории потоков

§1.1. Начало исследовательских работ


В первый раз препядствия связанные с пересылкой потоков в сетях подверглись рассмотрению Канторовичем в 1933 году. (Более того – он Реферат по истории математики Научный проф. Верещагин Н. К рассматривал более общую задачку с движением потока жидкостей разных типов (multicommodity flows)). Базы теории потоков были заложены в период с ноября 1954 по декабрь 1955 года исследователями компании RAND (Санта-Моника, Калифорния). Проследим за Реферат по истории математики Научный проф. Верещагин Н. К развитием теории потоков в хронологическом порядке по отчетам RAND.


1-ый отчет «Максимальный поток в сети» датируется 19м ноября 1954 года. Создатели отчета – Форд (Форд) и Фалкерсон (Fulkerson), обосновали аксиому о наивысшем потоке и Реферат по истории математики Научный проф. Верещагин Н. К наименьшем разрезе для неориентированных графов: значение наибольшего потока в сети равно малой пропускной возможности разреза. (Разрезом в сети именуется разбиение огромного количества ее вершин на два непересекающихся класса, таких что источник и Реферат по истории математики Научный проф. Верещагин Н. К сток лежат в различных классах. Пропускной способностью разреза именуется сумма пропускных возможностей ребер, концы которых лежат в различных классах.) В 1955 году в работе Робахера (Robacher) было упомянуто, что в первый раз эту Реферат по истории математики Научный проф. Верещагин Н. К аксиому обосновал Фалкерсон.


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


Более того, создатели увидели, что задачка о наивысшем потоке является личным случаем задачки линейного Реферат по истории математики Научный проф. Верещагин Н. К программирования, а стало быть, может быть решена симплекс-методом Данцига (Danzig). В отчете от 1 января 1955 года, Данциг и Фалекрсон проявили, что аксиома о наивысшем потоке и наименьшем разрезе может быть выведена из аксиомы Реферат по истории математики Научный проф. Верещагин Н. К о сильной двойственности для задач линейного программирования (в работе упоминалось, что данный факт установлен Хоффманом (Hoffman)). Более того, было подтверждено существование наибольшего целочисленного потока, для сетей пропускные возможности которых являются целочисленными. Следствием Реферат по истории математики Научный проф. Верещагин Н. К этого факта является популярная аксиома Менгера (Menger) о непересекающихся путях. 1 апреля 1955 года Данциг и Фалкерсон обрисовали обычной метод вычисления наибольшего потока основанный на симплекс-методе. 26 мая 1955 года Робахер независимо обосновал аксиому Реферат по истории математики Научный проф. Верещагин Н. К о наивысшем потоке и наименьшем разрезе, сведя ее к аксиоме Менгера.


§1.2. Эвристика Болдырева

До того времени пока имеющиеся методы вычисления наибольшего потока основывались на симплекс-методе, одной из важных задач в теории потоков было Реферат по истории математики Научный проф. Верещагин Н. К построение комбинаторного метода решения этой задачки. 3 июня 1955 года в Нью-Йорке на встрече Южноамериканского Общества Исследования Операций Болдырев сделал доклад (размещенный потом как отчет RAND от 5 августа 1955 года) об эвристическом методе нахождения Реферат по истории математики Научный проф. Верещагин Н. К наибольшего потока. Способ Болдырева является так именуемым «жадным алгоритмом»: он пробует отправить как можно больше потока из источника, до того времени, пока не обнаружится критичная верхушка (т.е. такая верхушка из Реферат по истории математики Научный проф. Верещагин Н. К которой нереально передать поток дальше). Такая ситуация устраняется методом возвращения лишнего потока в источник. По словам Болдырева, главные плюсы его способа заключались в том, что:

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

  2. Способ нахождения потока может быть описан в обычных определениях, без специальной технической подготовки.

  3. Есть обыкновенные способы проверки решения на корректность.

  4. Способ не просит использования огромных Реферат по истории математики Научный проф. Верещагин Н. К вычислительных мощностей.


«Техника решения формулируется как обычная игра, которой можно научить десятилетнего ребенка», утверждал Болдырев.


Но, данный способ является эмпирическим, не употребляет технику перебора с возвратом, и не гарантирует нахождения Реферат по истории математики Научный проф. Верещагин Н. К рационального решения. Но, это не смущало Болдырева, так как главным применением собственного метода он лицезрел транспортные сети. В собственной статье 1955 года он привел пример транспортной сети с 41 верхушкой и 85 дугами, для которой Реферат по истории математики Научный проф. Верещагин Н. К его метод посчитал верное решение наименее чем за 30 минут. В заключении статьи Болдырев пишет: «Возникает вопрос о периодическом, формальном обосновании; всесторонней математической базе для эмпирицизма и интуиции, и о связи данной техники Реферат по истории математики Научный проф. Верещагин Н. К с другими процессами, такими как многошаговые решающие процессы (multistage decision process), предложенные Беллманом. Все это остается для будущих исследований».


§1.3. Отчет Харриса-Росса

В собственном первом отчете о наибольших потоках, Форд и Фалкерсон Реферат по истории математики Научный проф. Верещагин Н. К упомянули, что задачка о наивысшем потоке была сформулирована Харрисом последующим образом: Разглядим транспортную сеть стальных дорог, соединяющих два городка через некое число промежных городов. Пусть также любая дорога, соединяющая два городка, имеет Реферат по истории математики Научный проф. Верещагин Н. К некую пропускную способность. Отыскать наибольший поток в данной сети, беря во внимание условие консервативности (т.е. для хоть какого промежного городка величина потока, пришедшая в город равна величине потока вышедшего из городка).


Позже в Реферат по истории математики Научный проф. Верещагин Н. К собственной книжке «Потоки в сетях» (1962), Форд и Фалкерсон дали более точную ссылку: в 1955 году Харрис, в соавторстве с Россом, определили ординарную модель для трафика в транспортных сетях, и рассматривали эту Реферат по истории математики Научный проф. Верещагин Н. К задачку (прим. – задачку о наименьшем разрезе). Идет речь о секретном отчете Харриса и Росса «Фундаментальный способ оценки пропускных возможностей транспортных сетей», датированном 24 октября 1955, и созданном для ВВС США. В отличие от Форда и Фалкерсона, центральной Реферат по истории математики Научный проф. Верещагин Н. К задачей для Харриса и Росса была задачка о наименьшем разрезе. А ее применением: нахождение слабеньких мест в системе стальных дорог СССР. (А конкретно, наименьшему разрезу тут соответствует малый набор транспортных Реферат по истории математики Научный проф. Верещагин Н. К путей, ликвидирование которого нанесет критичный вред транспортному сообщению СССР).





Рис. 2. Сеть стальных дорог СССР. Иллюстрация из книжки [1]

§1.4. Способ Форда-Фалкерсона

Аксиома Форда и Фалкерсона о связи малого потока и наибольшего разреза позволяет доказать последующий Реферат по истории математики Научный проф. Верещагин Н. К общий способ решения задачки о наивысшем потоке. Мысль заключается в том, что случайный поток в сети можно дополнить до наибольшего. По произвольному сгустку f разглядим «остаточную сеть» этого потока. Ребрами сети Реферат по истории математики Научный проф. Верещагин Н. К будут начальные ребра графа с пропускной способностью cf(uv) = c(uv) – f(uv), также оборотные ребра с пропускной способностью cf(uv) = f(vu). Способ Форда и Фалкерсона состоит в нахождении в остаточной сети Реферат по истории математики Научный проф. Верещагин Н. К случайного пути из источника в сток, и дополнении имеющегося потока (вначале нулевого) повдоль этого пути. Аксиома о наивысшем потоке и наименьшем разрезе позволяет доказать тот факт, что в случае если Реферат по истории математики Научный проф. Верещагин Н. К такового пути не существует, то поток является наибольшим.


В оригинале этот способ был сформулирован в 1956 без использования «остаточной сети», но его описание в определениях обыкновенной сети очень громоздко, потому мы его тут не приводим. Термин Реферат по истории математики Научный проф. Верещагин Н. К «остаточная сеть» появился позже, и в текущее время является одним из главных инструментов исследователей в области потоков.


§1.5. Метод Эдмондса-Карпа

Но, в общем случае способ Форда и Фалкерсона не является корректным Реферат по истории математики Научный проф. Верещагин Н. К. Существует пример сети с иррациональными пропускными возможностями, для которой метод Форда и Фалкерсона не остановится (будет работать «бесконечное время»). Для сетей с целочисленными пропускными возможностями время работы составляется O(UVE), где U – наибольшая пропускная Реферат по истории математики Научный проф. Верещагин Н. К способность, V – количество вершин и E количество ребер в сети. Сети с оптимальными пропускными возможностями могут быть сведены к целочисленному случаю методом домножения на больший общий делитель знаменателей всех Реферат по истории математики Научный проф. Верещагин Н. К дробей.


В 1969 году Эдмондсом и Карпом была предложена модификация этого метода, позволяющая получить гарантированное время O(VE^2) работы метода последующим методом: на каждом шаге путь из источника в сток необходимо выбирать не Реферат по истории математики Научный проф. Верещагин Н. К случайный, а кратчайший. В данном случае удается обосновать оценку O(VE) на число фаз работы метода. Разыскиваемая оценка следует из того, что в неориентированном графе может быть отыскать расстояние меж 2-мя верхушками за время O Реферат по истории математики Научный проф. Верещагин Н. К(E).


§1.6. Последующие улучшения метода построения наибольшего потока

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

Блокирующий поток – это поток, величину Реферат по истории математики Научный проф. Верещагин Н. К которого нереально сделать лучше методом только роста потока повдоль отдельных ребер. Строить таковой поток Диниц предлагал с помощью традиционного метода поиска «в ширину».


Другое направление исследовательских работ – усовершенствованные методы для нахождения наибольшего потока Реферат по истории математики Научный проф. Верещагин Н. К в сети с целочисленными пропускными возможностями. Способ, предложенный Эдмондсом и Карпом в 1972 году (и независимо Диницом в 1973) получил заглавие способа масштабирования пропускных возможностей (capacity scaling). Мысль способа ординарна: поток в сети Реферат по истории математики Научный проф. Верещагин Н. К с пропускными возможностями, равными половине пропускных возможностей начальной сети, мы просто можем получить поток в начальной сети методом умножения его значения на 2. Раздельно необходимо обрабатывать ребра с нечетными пропускными возможностями. Приобретенный метод имеет Реферат по истории математики Научный проф. Верещагин Н. К время работы O(nm log U), где n – число вершин сети, m – число ребер, U – наибольшая пропускная способность.


Карзанову в 1974г удалось, при помощи модификации метода Диница, достигнуть оценки быстродействия O(n^3). Им Реферат по истории математики Научный проф. Верещагин Н. К также в первый раз было введено понятие “предпотока”. В 1978г Малхотри, Кумару м Махешвари (Malhotra, Kumar, Maheshwari) удалось повторить этот итог, но их метод отличался от метода Карзанова.

Наилучший Реферат по истории математики Научный проф. Верещагин Н. К из узнаваемых на сегодня алгоритмов был предложен в 1997 году Гольдбергом и Рао (Goldberg, Rao). В качестве вспомогательной процедуры метод употребляет структуру данных, полученную Гольдбергом и Тарьяном (Tarjan).

В заключение приведем сводную хронологическую таблицу результатов Реферат по истории математики Научный проф. Верещагин Н. К, приобретенных для задачки о наивысшем потоке (всюду дальше n – число вершин сети, m – число ребер, U – наибольшая пропускная способность ребер сети)





Глава 2. Теория паросочетаний

§2.1. Паросочетание в двудольном графе

Базы теории паросочетаний в двудольных графах Реферат по истории математики Научный проф. Верещагин Н. К были заложены Фробениусом (сформулировавшим их в определениях матриц и детерминантов) и Кёнигом. В статье Кёнига (1915г), представленной ранее в Венгерской Академии он обрисовал метод построение двудольного графа по случайной матрице Реферат по истории математики Научный проф. Верещагин Н. К (a_ij): верхушки графа соответствуют строчкам и столбцам матрицы, при всем этом ребро меж строчкой i и столбцом j существует в том и только том случае, когда a_ij не равно нулю.


Ранее Реферат по истории математики Научный проф. Верещагин Н. К, в апреле 1914 года на Конгрессе Философии Арифметики в Париже, Кёниг представил аксиому о том, что хоть какой постоянный граф без циклов нечетной длины является двудольным.


В первый раз, задачка близкая к задачке о Реферат по истории математики Научный проф. Верещагин Н. К паросочетании подверглась рассмотрению Кёнигом в 1916 году. Он обосновал, что если требуется расположить на квадратной доске размера n*n (при всем этом часть клеток доски может отсутствовать) фишки в количестве k*n (при Реферат по истории математики Научный проф. Верещагин Н. К всем этом на одной клеточке может лежать более одной фишки), таким макаром что в каждой строке и в каждом столбце находится ровно по k фишек, то такую конфигурацию можно получить Реферат по истории математики Научный проф. Верещагин Н. К методом объединения k конфигураций, для каждой из которой в каждом столбце и каждой строке находится ровно одна фишка.


§2.2.Аксиома Фробениуса

В 1917 году Фробениус обосновал последующую аксиому: пусть в матрице A = (a_ij) размера Реферат по истории математики Научный проф. Верещагин Н. К n*n выполнено последующее условие: для хоть какой перестановки p выполнено условие a_1p(1)*..*a_np(n) = 0, то для некого числа k найдутся k строк и n – k + 1 столбцов матрице А, такие Реферат по истории математики Научный проф. Верещагин Н. К что хоть какой элемент, лежащий на скрещении этих строк и столбцов, равен нулю. Используя построение Кёнига, этот итог можно переформулировать в определениях двудольных графов: для хоть какого двудольного графа G = (V, E), огромное Реферат по истории математики Научный проф. Верещагин Н. К количество вершин которого разбито на толики V1 и V2, такие, что |V1| = |V2| = n, существует совершенное паросочетение в том и только том случае, когда нереально избрать k вершин из V1 и Реферат по истории математики Научный проф. Верещагин Н. К n – k + 1 вершин из V2, таких что меж этими верхушками не существует ни 1-го ребра. Что в особенности ценно, Фробениус представил обычное комбинаторное подтверждение этой аксиомы.

§2.3.Аксиома Менгера о непересекающихся путях и аксиома Кёнига о Реферат по истории математики Научный проф. Верещагин Н. К паросочетании

В 1927 году тополог Карл Менгер определил и обосновал последующую аксиому. Пусть в неориентированном графе G = (V, E) заданы подмножества P, Q огромного количества вершин V. Тогда наибольшее число непересекающихся Реферат по истории математики Научный проф. Верещагин Н. К путей из P в Q равно наименьшему размеру огромного количества W вершин, такового что каждый путь из P в Q пересекает W.


Любопытно, что сначало аксиома была сформулирована в топологических определениях: компактах и постоянных Реферат по истории математики Научный проф. Верещагин Н. К кривых. Позже, в 1932 году Кёниг нашел в подтверждении Менгера некорректность. В марте 1931 года на встрече Математического общества Lorand Eotvos в Будапеште, Кёниг представил новый итог, послуживший основой для подтверждения аксиомы Менгера: мощность Реферат по истории математики Научный проф. Верещагин Н. К наибольшего паросочетания в двудольном графе приравнивается наименьшему количеству вершин, нужных для покрытия всех ребер. (По определению, верхушка покрывает все ребра, примыкающие с данной верхушкой, и только их). Кёниг ссылался на результаты Реферат по истории математики Научный проф. Верещагин Н. К, приобретенные Фробениусом, но не отметил, что его аксиома может быть получена из аксиомы Фробениуса. Напротив, в базе подтверждения приобретенного Кёнигом лежит принцип дополнения повдоль чередующихся путей (ставший потом базовым в теории паросочетаний). Размещены эти Реферат по истории математики Научный проф. Верещагин Н. К результаты были в 1932 году.


§2.4. Связь меж потоками и паросочетаниями

Последующее обычное построение позволяет установить связь меж потоками в сетях и Паросочетаниями в двудольном графе. Разглядим случайный двудольный граф с обилием вершин V разбитым Реферат по истории математики Научный проф. Верещагин Н. К на толики X и Y. Добавим две дополнительные верхушки – источник s и сток t. Добавим ребро sx из источника в каждую верхушку толики x и аналогично ребро yt из каждой верхушки Реферат по истории математики Научный проф. Верещагин Н. К толики Y в сток. Все пропускные возможности положим единичными. Оказывается, что меж потоками в построенной сети и паросочетаниями в начальном графе существует взаимнооднозначное соответствие. А поэтому мощность наибольшего Паросочетания в начальном Реферат по истории математики Научный проф. Верещагин Н. К графе приравнивается величине наибольшего потока. Таким макаром, задачка о паросочетании является личным случаем задачки о нахождении наибольшего потока в сети. А поэтому хоть какой метод нахождения наибольшего потока можно применить к решению задачки о Реферат по истории математики Научный проф. Верещагин Н. К паросочетании.

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

Глава 3. Задачка о назначениях: «взвешенный» вариант задачки о паросочетаниях


§3.1. Монж: наилучшее предназначение

Задачка о назначениях является одной из наистарейших задач комбинаторной оптимизации. Еще в 1784 году ее изучил Монж (Monge) (в собственных работах он использовал Реферат по истории математики Научный проф. Верещагин Н. К термин «задача о транспортировке». Монж был мотивирован задачей транспортировки земли, которую он рассматривал как дискретную, комбинаторную задачку транспортировки молекул: «Когда нужно перевезти землю из 1-го места в другое, нужно учесть как количество перевозимой земли Реферат по истории математики Научный проф. Верещагин Н. К, так и наличие свободного места там, куда она перевозится. Стоимость транспортировки одной молекулы пропорциональна ее весу и расстоянию перевозки, а означает, полная стоимость перевозки должна быть пропорциональна сумме произведений весов молекул на Реферат по истории математики Научный проф. Верещагин Н. К пройденное расстояние».


Формально, Мондж рассматривает последующую задачку: «Пусть на плоскости заданы две области, ABCD и abcd, ограниченные произвольным контуром, непрерывные либо дискретные, отыскать пусть которому должна следовать любая молекула М первой области, чтоб Реферат по истории математики Научный проф. Верещагин Н. К перейти в некую молекулу m второго области, таким макаром, что в итоге этого перемещения область ABCD была перемещена в область abcd, и сумма произведений веса каждой молекулы на пройденное Реферат по истории математики Научный проф. Верещагин Н. К ей расстояние было минимальным». Мондж предложил геометрический способ решения данной задачки. Невзирая на его геометрическую интуитивность, он был не совершенно верен, как увидел в 1928 году Аппель.


§3.2. Аксиома Эгервари

В 1931 году Эгервари опубликовал «взвешенный Реферат по истории математики Научный проф. Верещагин Н. К» вариант аксиомы Кёнига: Пусть элементы a_ij матрицы A размера n неотрицательные целые числа, и пусть для неких наборов неотрицательных чисел L_i и M_j выполнены условия: а_ij <= L_i Реферат по истории математики Научный проф. Верещагин Н. К + M_j (для всех I и j), тогда получим что min sum (L_k + M_k) = max (a_1p(1) + .. + a_np(n)), где максимум берется по всем перестановкам p.


Подтверждение, предложенное Эгервари, чисто алгоритмично Реферат по истории математики Научный проф. Верещагин Н. К и ведет к методу, использующему «невзвешенную» задачку о паросочетании в качестве подзадачи. Пусть W – наибольшее число в матрице А, тогда методу будет нужно применить задачку о Паросочетании O(nW) раз Реферат по истории математики Научный проф. Верещагин Н. К, а суммарное время работы метода составит O(nWB(n)), где B(n) – лучшая оценка времени работы метода нахождения наибольшего Паросочетания. Этот способ послужил основой для сформулированного в 1955 году «Венгерского метода» Куна, которые мы Реферат по истории математики Научный проф. Верещагин Н. К подробнее разглядим дальше.


Другим результатом Эгервари было установление последующей двоякой природы задачки о взвешенном Паросочетании: пусть G = (V, E) – двудольный граф и пусть w: E -> R неотрицательная весовая функция. Тогда вес наибольшего Паросочетания в Реферат по истории математики Научный проф. Верещагин Н. К G приравнивается наименьшему значению y(V), где y: V -> R, таково что: y >= 0 и y_u + y_v >= w(uv).


§3.3. 1940е годы

1-ый метод для задачки о назначениях был размещен Истерфилдом (Easterfield) в Реферат по истории математики Научный проф. Верещагин Н. К 1946 году. Мотивация этого метода была последующей: «Что касается исследования в области задач демобилизации вооруженных сил, представляется вероятным организовать переход людей из расформированных отрядов в другие отряды таким макаром, чтоб их Реферат по истории математики Научный проф. Верещагин Н. К не пришлось позже переводить опять то момента их демобилизации. Более того, исследования количеств людей в разных группах позволили бы организовать этот процесс с минимальным вероятным количеством задержек. К огорчению, неожиданный конец Японской войны не Реферат по истории математики Научный проф. Верещагин Н. К отдал способности проверить эффективность этой теории в деле. Все же, метод, изложенный в данной статье, появился конкретно в процессе исследовательских работ в этой области».

Похоже, что Истерфилд работал, не имея Реферат по истории математики Научный проф. Верещагин Н. К представления о других исследовательских работах в данной области. Он определил и обосновал аксиому эквивалентную аксиоме Халла, также представил способ решения данной задачки, из которого можно извлечь результаты, приобретенные Эгервари.


Мысль Истерфильда базирована Реферат по истории математики Научный проф. Верещагин Н. К на переборе всех подмножеств вершин в словарном порядке, что привело к методу со сложностью O(n^2 * 2^n) (что является улучшением по сопоставлению с перебором всех перестановок, на который требуется n! действий). Этот Реферат по истории математики Научный проф. Верещагин Н. К метод был в предстоящем уточнен в 1960 году.


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


Диниц рассматривал задачку о назначениях применительно к рассредотачиванию работы посреди людей. Он писал: «Как было сказано, в задачке о Реферат по истории математики Научный проф. Верещагин Н. К назначениях появляется только конечное число перестановок. Потому с математической точки зрения довольно разглядеть все перестановки и избрать из их лучшую. К примеру, если мы разглядим задачку для хотя бы для 10 человек Реферат по истории математики Научный проф. Верещагин Н. К, возникнет более 3-х с половиной миллионов перестановок, потому данный математический подход окажется неприменимым на практике».


В 1949 году Робинсон в отчете для RAND написал что его «неудачный попытки» решения задачки о коммивояжере Реферат по истории математики Научный проф. Верещагин Н. К привели к увлекательному методу решения задачки о назначениях, основанном на «отмене циклов». Мысль его была последующей: разглядим произвольную перестановку p. Для всех i,j определим «длину» L_ij = a_jp(j Реферат по истории математики Научный проф. Верещагин Н. К) – a_ip(i) если j != p(i), и бесконечности в неприятном случае. Если в графе с такими длинами возникнет цикл отрицательного веса, это позволит сходу сделать лучше перестановку p. Если же такового цикла не Реферат по истории математики Научный проф. Верещагин Н. К окажется, то перестановка p оптимальна. Как отметил Робинсон, данный способ можно использовать к графам из 50 вершин, при условии наличия нужных вычислительных средств.


§3.3. Ранешние 1950е

На семинаре по теории игр в Принстонском Реферат по истории математики Научный проф. Верещагин Н. К Институте в 1951 году, Фон Нейман (Von Neumann) указал на то, что задачка о назначениях может быть сформулирована в виде игры с нулевой суммой для 2-ух игроков, и нахождение ее решения эквивалентно поиску хорошей стратегии в Реферат по истории математики Научный проф. Верещагин Н. К этой игре. Игра устроена последующим образом: пусть задана матрица A. 1-ый игрок будет играть строчками этой матрицы, 2-ой игрок – столбцами. 1-ый игрок выбирает номер строчки, 2-ой – номер столбца, после этого 1-ый Реферат по истории математики Научный проф. Верещагин Н. К «платит» второму A_ij «денег». Индексы строк и столбцов чередоваться не могут, таким макаром игра длится n раундов (где n – размер матрицы).


Сведение данной игры к задачке о назначениях не Реферат по истории математики Научный проф. Верещагин Н. К разумеется. В предстоящем к этой идее обращались Браун (Brown) и Робинсок. Фон Нейман также увидел, что поиск хорошей стратегии по видимому можно выполнить за время пропорциональное некой степени n, что приметно меньше Реферат по истории математики Научный проф. Верещагин Н. К чем «очевидное» решение за время n!. Все же, никакой аргументации этого наблюдения не последовало. Похожие идеи также были в работах Дулмага (Dulmage) и Гальперина (Halperine) (1955) и Купманса (Koopmans) и Бекмана (Beckmann) (1955, 1957).


В работах Лорда (Lord Реферат по истории математики Научный проф. Верещагин Н. К) (1952) и Двайера (Dwyer) (1954), был изложен некий геометрический подход («метод хороших регионов»). Обзор способов решения задачки о назначениях по состоянию на 1953 год был изготовлен Моцкиным (Motzkin) в 1956 году.


§3.4. Вычислительные результаты начала Реферат по истории математики Научный проф. Верещагин Н. К 1950х годов

В статье, представленной в 1951 году на Симпозиуме по Линейным Неравенствам и Линейному Программированию в Вашингтоне, Воташ (Votaw) и Орден (Orden) упомянули, что для решения задачки о назначениях размера 10 * 10 требуется около 3 минут вычислений на Реферат по истории математики Научный проф. Верещагин Н. К машине SEAC (National Bureau of Standards Eastern Automatic Computer). В то же время для решения задачки о назначениях такого же размера при использовании симплекс-метода требовалось около 20 минут.


Но, в мемуарах Куна Реферат по истории математики Научный проф. Верещагин Н. К от 1991 года он пишет: «Эта история началась летом 1953 года, когда Национальное Бюро Эталонов США собрали группу выдающихся алгебраистов и профессионалов по комбинаторике в Институте Численного анализа (INA) размещенного на местности Реферат по истории математики Научный проф. Верещагин Н. К Института Калифорнии в Лос-Анджелесе. Из-за нехватки места, я разделял кабинет с Тедом Моцкиным, чьи работы в области линейных неравенств продвинули эту теорию на 10 лет вперед. Одной из новинок, презентованных Реферат по истории математики Научный проф. Верещагин Н. К в INA, был компьютер SWAC (Standards Western Automatic Computer). SWAC был меньше, но резвее чем его предшественник – компьютер SEAC. В течение лета, Томпкинс (C.B. Tompkins) решал пробы решить задачку о назначениях размера 10*10 на Реферат по истории математики Научный проф. Верещагин Н. К машине SWAC. Но потому что эта задачка является задачей линейного программирования со 100 неотрицательными переменными и 20 ограничивающими равенствами, ему это не удалось. В 1953 году в мире просто не было машины, способной совладать с Реферат по истории математики Научный проф. Верещагин Н. К такими объемами вычислений».


§3.5. Венгерский способ Куна-Манкреша

В 1955 году Кун разработал новый комбинаторный подход решения задачки о назначениях. Он базируется на работе Егервари от 1931 года, а поэтому Кун избрал для него заглавие «Венгерский метод Реферат по истории математики Научный проф. Верещагин Н. К». В 1957 году способ был улучшен Манкрешом (Munkres). Невзирая на то, что в оригинале способ был сформулирован в определениях матриц, он представляет собой комбинаторный подход к решению задачки о назначениях. Уникальный метод Реферат по истории математики Научный проф. Верещагин Н. К имеет сложность работы O(N^4). В одной из статей Форда и Фалкерсона от 1957 года, в примечании было приведено последующее увлекательное сопоставление: «Для решения задачки об хороших назначениях размера 20*20, при использовании симплекс-метода, требовалось Реферат по истории математики Научный проф. Верещагин Н. К около часа вычислений на компьютере. Новый подход Куна позволяет решить эту задачку всего за 30 минут вручную».

В 1970 году Эдмондс и Карп улучшили метод, что позволило достигнуть времени работы O Реферат по истории математики Научный проф. Верещагин Н. К(N^3). С этих пор задачку о назначениях можно было практически считать решенной.

Глава 4. Последующие исследования в теории потоков


§4.1. Потоки малой цены

Аналогично тому, как задачка о паросочетании была обобщена на случай ребер с разными весами Реферат по истории математики Научный проф. Верещагин Н. К (задачка о назначениях), задачка о наивысшем потоке может быть обобщена как задачка о наивысшем потоке малой цены. Для решения этой задачки также справедлив способ Форда и Фалкерсона, кроме того, что дополняющий путь необходимо Реферат по истории математики Научный проф. Верещагин Н. К избрать кратчайшим относительно стоимостей ребер сети. Для этой цели можно использовать традиционный метод Форда-Беллмана нахождения кратчайшего пути. Это позволит достигнуть оценки времени работы метода для наибольшего потока малой цены O(E V Реферат по истории математики Научный проф. Верещагин Н. К^3). Джонсон (Johnson) разработал способ потенциалов, обобщающий традиционный метод Дейкстры нахождения кратчайшего пути на случай графов с отрицательными ребрами, что позволило сделать лучше время работы до O(E V^2).


Но, есть Реферат по истории математики Научный проф. Верещагин Н. К более действенные с практической точки зрения методы решения задачки. Мысль состоит в поочередном приближении («алгоритм масштабирования») начальной сети. Соответственный метод был изложен в 1987-1989 годах Гольдберг (Goldberg) и Тарьян (Tarjan) выпустили целую серию Реферат по истории математики Научный проф. Верещагин Н. К статей по этой теме. Другой метод в 1988 году представил Орлин (Orlin) в статье «Быстрый сильно-полиномиальный метод нахождения наибольшего потока малой стоимости».


§4.2. Динамические потоки. Задачка транспортировки

Энтузиазм к транспортировке появился в области потоков Реферат по истории математики Научный проф. Верещагин Н. К в сетях в течение 1940-х и 50-х годов. Было размещено огромное количество работ в этой области, но они все содержали одно увлекательное упущение. Невзирая на естественную связь меж потоками в сетях и задачками Реферат по истории математики Научный проф. Верещагин Н. К транспортировки, большая часть исследовательских работ в области теории потоков игнорировали самый главный вопрос, который задает хоть какой ребенок, сидячий на заднем сидение автомобиля: «Мы уже приехали?». Предки, обязанные повсевременно слушать этот вопрос, непременно Реферат по истории математики Научный проф. Верещагин Н. К, помыслят о времени, до того как мыслить о том, куда и как ехать дальше.


Форд и Фалкерсон были отлично ознакомлены о значимости времени в транспортировке, и они учли его Реферат по истории математики Научный проф. Верещагин Н. К в их модели сети. Они обобщили стандартное определение сети методом прибавления в него транзитных времен меж верхушками, получив тем динамическую сеть. Каждое ребро yz в динамической сети моделирует трубопровод из верхушки y в верхушку z Реферат по истории математики Научный проф. Верещагин Н. К. Пропускная способность ребра yz соответствует площади сечения труб, тем ограничивая количество потока, которое может быть передано за единицу времени. Транзитные времена соответствуют длине трубопровода; они определяют, сколько времени требуется Реферат по истории математики Научный проф. Верещагин Н. К сгустку на прохождения из верхушки y в верхушку z повдоль ребра yz. Динамический поток перемещается со временем в динамической сети. Он является расширением обычных потоков; отображением пар (ребро, время) в величину потока, а не Реферат по истории математики Научный проф. Верещагин Н. К отображением ребер как это было ранее.


Со времен Форда и Фалкерсона исследования в области динамических потоков ориентированы как на теоретические исследования математических моделей, так и на практические и алгоритмические нюансы их реализации Реферат по истории математики Научный проф. Верещагин Н. К. В то же время было уделено недостаточно внимания алгоритмической теории. А именно, очень малость было понятно о вычислительной трудности задач о динамических потоках. В диссертации Хоупа (Hoppe, 1995) акцент был изготовлен конкретно на Реферат по истории математики Научный проф. Верещагин Н. К разработке на теоретическом уровне действенных алгоритмов. Эта работа убрала разрыв меж исследованием потоков в обычных и динамических сетях.


§4.3. Универсально-максимальные динамические потоки

Форд и Фалкерсон рассматривали простейшую потоковую задачку в динамической сети: задачку о Реферат по истории математики Научный проф. Верещагин Н. К наивысшем динамическом потоке. Входом для данной задачки является временной интервал T и динамическая сеть с одним источником и одним стоком; решением является допустимый динамический поток, который пересылает наибольшее вероятное количество Реферат по истории математики Научный проф. Верещагин Н. К потока из истока в сток за время T.

Форд и Фалкерсон нашли уникальный полиномиальный метод для данной задачки. Гэйл, Уилкинсон и Миниека рассматривали вариант задачки о наивысшем динамическом потоке, в каком Реферат по истории математики Научный проф. Верещагин Н. К сток был должен получить как можно больше потока на каждом промежном шаге до T и включительно. Вприбавок к этому поток должен покидать источник как можно позже. (Факт существования такового потока нетривиален и Реферат по истории математики Научный проф. Верещагин Н. К был установлен Гэйлом). Позднее Уилкинсон и Миниека независимо получили псевдополиномиальный метод нахождения такового потока.


1-ый полиномиальный метод нахождения значения универсально-максимального динамического потока для хоть какого ребра для каждого отдельного момента времени Реферат по истории математики Научный проф. Верещагин Н. К (т.е. временной разрез полного решения) был предложен Хоупом. Он также предложил 1-ый полиномиальный метод, который приближает универсально-максимальный динамический поток с коэффициентом 1 + eps для хоть какого eps > 0. (Метод работает полиномиальное относительно 1/eps время).


§4.4. Наибыстрейшие Реферат по истории математики Научный проф. Верещагин Н. К потоки

Другой вариант задачки о наивысшем динамическом потоке это задачка о наибыстрейшем потоке, в какой нам задана величина потока v и

требуется отыскать допустимый динамический поток, который доставит v единиц потока из источника Реферат по истории математики Научный проф. Верещагин Н. К в сток за меньшее вероятное время. Задачка о наибыстрейшем потоке может быть сведена к задачке о наивысшем динамическом потоке при помощи двоичного поиска. Баркард (Burkard) и др. изучали эту задачку и Реферат по истории математики Научный проф. Верещагин Н. К обрисовали более эффективную технику ее решения.


Задачка эвакуации является обобщением задачки о наибыстрейшем потоке на случай нескольких источников. Для каждого из их нам задан вектор снабжения и требуется отыскать допустимый динамический поток Реферат по истории математики Научный проф. Верещагин Н. К, который доставляет требуемое количество потока из каждого источника в сток за меньшее вероятное время. В классической сети без времен транзита, задачка эвакуации элементарно сводится к задачке о наивысшем потоке с одним источником Реферат по истории математики Научный проф. Верещагин Н. К (методом прибавления "суперисточника"). Но, в динамическом случае, задачка является еще более сложной, чем задачка о наибыстрейшем потоке. В то же время она полезнее: задачка эвакуации была вначале сформулирована в практической модели эвакуации из Реферат по истории математики Научный проф. Верещагин Н. К построек.


Хоуп (Hoppe) в собственной диссертации (1995) представил 1-ый (очень) полиномиальный метод для задачки о наибыстрейших перевозках - обобщении задачки эвакуации, где в дополнение к нескольким источникам разрешены несколько стоков. Метод Хоупа также Реферат по истории математики Научный проф. Верещагин Н. К для целочисленных входных данных гарантирует целочисленное решение.


В 2005 году в работе «Наибыстрейшие потоки с несколькими источниками» Рауфа (Rauf) метод Хоупа был обобщен на случай сетей с несколькими источниками.


§4.5. Планирование сетей

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


Эта задачка просто сводится к задачке о наибыстрейших перевозках, применяя наш метод решения которой мы получим 1-ый полиномиальный Реферат по истории математики Научный проф. Верещагин Н. К метод решения задачке о планировании вычислительных сетей для задач единичного размера, но исключительно в неких очень особых случаях. Физзано (Fizzano) и Штейн (Stein) рассматривали кольцевые сети с единичными пропускными возможностями и транзитными Реферат по истории математики Научный проф. Верещагин Н. К периодически. Хоуп предложил метод, работающий в сети вида, с случайными пропускными возможностями и периодически транзита.

Заключение

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


Но, структура потоковых задач ведет к еще более действенным решениям (как с теоретической, так и с практической Реферат по истории математики Научный проф. Верещагин Н. К точек зрения), чем решение линейных программ. И тот подход получил наибольшее внимание со стороны исследователей с того времени как Форд и Фалкерсон избрали его в собственном базовом труде по потокам в сетях Реферат по истории математики Научный проф. Верещагин Н. К.


В течении следующих 4 десятилетий одной из главных задач для общества исследователей в области компьютерных наук и исследования операций стало увеличение эффективности алгоритмов для потоков в сетях. Решенной эту задачку можно считать в Реферат по истории математики Научный проф. Верещагин Н. К 1997 году, с возникновением метода Рао - Гольдберга. С того времени главные усилия исследователей ориентированы на исследование динамических потоков – обобщения обыденных («статических») потоков, учитывающего время.


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


«Мирным» применением теории потоков являются различные задачки связанные с транспортировкой грузов. В более обычный модели ответ на этот вопрос дает задачка о Реферат по истории математики Научный проф. Верещагин Н. К назначениях – обобщение задачки о наивысшем паросочетании. Более сложные модели опираются на теорию динамических потоков, и тут еще есть много задач для последующих исследовательских работ.

Библиография


  1. Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficieny. Volume A Реферат по истории математики Научный проф. Верещагин Н. К. Springer, Berlin, 2003

  2. Bruce E. Hoppe. Efficient Dynamic Flow Algorithms. PhD Thesis, Cornell Univeristy, 1995

  3. T. Кормен, Ч. Лейзесон, Р. Ривест. Методы: построение и анализ. МЦНМО, 2001

  4. Л. Р. Форд, Д. Р. Фалкерсон. Потоки в сетях. Перевод Реферат по истории математики Научный проф. Верещагин Н. К с британского И.А. Вайнштейна. М:Мир, 1966

  5. E. Minieka. Dynamic network flows with arc changes. Networks journal, 1974

  6. David Gale. Transient Flows in networks. RAND, 1958

  7. Imran Rauf. Earliest Arrival Flows with Multiple Sources Реферат по истории математики Научный проф. Верещагин Н. К. Master Thesis in Computer Science. Saarland University, 2005

  8. Wikipedia, the Free Encyclopedia http://en.wikipedia.org

  9. «Алголист». http://algolist.manual.ru/maths/graphs/maxflows/



referat-po-etike-na-temu-cerkov-i-religiya-i-ih-vliyanie-na-formirovanie-etiketnoj-kulturi.html
referat-po-fizicheskoj-kulture-na-temu-sportivno-ozdorovitelnij-turizm.html
referat-po-gosudarstvennomu-regulirovaniyu-ekonomiki-na-temu-.html