АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Нахождение потока заданной мощности минимальной стоимости. Алгоритм Басокера-Гоуэна

Читайте также:
  1. A)нахождение средней из двух соседних средних, для отнесения полученного результата к определенной дате
  2. IV. Современные методы синтеза неорганических материалов с заданной структурой
  3. VI. По размеру предприятий (по мощности производственного потенциала)
  4. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  5. Алг «нахождение минимума»
  6. Алгоритм
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм
  10. Алгоритм 65 «Кровотечение в послеродовом периоде»
  11. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»
  12. Алгоритм MD4

Задана сеть каждой дуге которой поставлено в соответствие 3 числа: С(х,у) – пропускная способность дуги, f(x,y) -, d(x,y) - стоимость провода единицы потока по дуге x,y. Требуется пропустить в сети поток заданной величины V или максимальный поток минимальной стоимости.

Алгоритм Басакера-Гоуэна

Шаг 0. Решение начинаем с нулевого потока V=0.

Шаг 1. Строим граф модифицированных стоимостей Gf по следующим правилам

1.Множество вершин графа Gf совпадает с множеством вершин графа G.

2.Если в графе G 0<f(x,y)<c(x,y), тогда в графе строится 2 дуги: прямая, с длиной равной стоимости(e(x,y)=d(x,y)); e(x,y)=-d(x,y).

3.Если в графе G f(x,y)=0, то в графе Gf строится одна дуга e(x,y)=d(x,y).

4.Если f(x,y)=c(x,y), то рисуем e(x,y)=-d(x,y).

Шаг 2. Находим в графе Gf минимальный путь из S в T. Обозначим его P*. В исходном графе G определяем путь P, соответствующий Р*. На прямых дугах пути Р вычисляем €1=c(x,y)-f(x,y), €2=f(x,y), min €1. На прямых дугах +€, на обратных -.

Шаг 3. Получаем V=V*. Если в V = заданному потоку, то алгоритм свою работу заканчивает. В графе G построим поток мощности V min стоимости.

Замечание: Если задача на нахождение максимального потока мин стоимости, то алгоритм свою работу заканчивает когда в графе Gf нет ниодного пути Р* из S в T.

Пример: построить поток V=3

S
d [3204]" strokecolor="#243f60 [1604]" strokeweight="2pt">
b
t
a


4,0\5 2,0\1

 

3,0\1

 

2,0\1 3,0\6

 

P: s-b-a-t

S
b
t
a
P*: s-b-a-t

1 mXXk2RQrDWTLcKoY58LG6ciE2QkmldYjsPw78JCfoCLP7QgelP2x6ojIlZ2NI9go6+B31ePu2LIc 8o8ODLqTBZeu3ud3zdbgAGavDp8lTfiP+wz//qWX3wAAAP//AwBQSwMEFAAGAAgAAAAhAGS8Z/Hg AAAACgEAAA8AAABkcnMvZG93bnJldi54bWxMj0FOwzAQRfdI3MEaJDaI2k1bmoY4VRXEAiEWtD2A E5skwh6HjJOG22NWsBz9p//f5PvZWTaZgTqPEpYLAcxg7XWHjYTz6fk+BUZBoVbWo5HwbQj2xfVV rjLtL/hupmNoWCxBypSENoQ+45zq1jhFC98bjNmHH5wK8Rwargd1ieXO8kSIB+5Uh3GhVb0pW1N/ Hkcn4ZUonax4Gcv0UH7Zp+rtjoSW8vZmPjwCC2YOfzD86kd1KKJT5UfUxKyE1VasIyphs9wCi8Ba JDtglYRktdsAL3L+/4XiBwAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAA AAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEA AAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAM9XdUgHAgAAGgQA AA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAGS8Z/HgAAAA CgEAAA8AAAAAAAAAAAAAAAAAYQQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABuBQAA AAA= " strokecolor="#4f81bd [3204]" strokeweight="2pt">

5 6

 

1 1

 

 

€1=(2,3,2)=2

€=min(€1, €2,V)=> €=2

V*=V*+€=2

S
d [3204]" strokecolor="#243f60 [1604]" strokeweight="2pt">
t
a
5 SzrSbPK1ArKjOFWUMW7CdGTC7AgTUqkRWPwdeMyPUJ7mdgQPyv5YdUSkytaEEaylsfC76mF/alkM +ScHBt3RgktbH9K7JmtwAJNXx88SJ/zHfYJ//9KrbwAAAP//AwBQSwMEFAAGAAgAAAAhAJEGj6Xg AAAACwEAAA8AAABkcnMvZG93bnJldi54bWxMj8tOwzAQRfdI/IM1SGwQtWlJk4Y4VRXEAiEWlH6A Ew9JhB8hdtLw9wwrWI7u0b1niv1iDZtxDL13Eu5WAhi6xuvetRJO70+3GbAQldPKeIcSvjHAvry8 KFSu/dm94XyMLaMSF3IloYtxyDkPTYdWhZUf0FH24UerIp1jy/WozlRuDV8LseVW9Y4WOjVg1WHz eZyshJcQstmI56nKDtWXeaxfb4LQUl5fLYcHYBGX+AfDrz6pQ0lOtZ+cDsxI2KQiJVTCOsk2wIhI dlkCrKZoe58CLwv+/4fyBwAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAA AAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEA AAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAOkXgyEHAgAAGgQA AA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAJEGj6XgAAAA CwEAAA8AAAAAAAAAAAAAAAAAYQQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAABuBQAA AAA= " strokecolor="#4f81bd [3204]" strokeweight="2pt">
b

 


5

-1

1 -1

 

-1 6

 

P*:s->a->b->t

P:s->a<-b->t

€1=(4,3)=3

€2=2

€=(3,2,1)=1

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)