Алгоритм Форда-Фалкерсона поиска максимального потока в сети.
Метод решения Алгоритмом Форда-Фалкерсона.
Дан несимметричный ор-граф с выходом и входом, числа на матрице инцидентности задают пропускные способности трубопроводов между пунктами. Надо найти максимальный поток, который можно дать через сеть трубопроводов.
Ищется цепочка с ненулевыми пропускными способностями через которую можно дать сквозной поток.
По узкому звену находится пото
(Код: Алгоритм Форда)(2 задачи на пару 90 мин). Алгоритмом Форда-Фалкерсона найти максимальный поток в сети
(Презентация
ИССЛЕДОВАНЕ ОПЕРАЦИЙ)
При решении только САМ граф перерисовывается 5-6 раз. Кроме этого в ответе даётся граф потоков.
При выполнении каждой итерации необходимо нарисовать новый граф и произвести его разметку в соответствии с алгоритмом, найти новый элементарный (не разветвлённый) поток и, пересчитав веса нарисовать новый граф, повторяя итерации пока возможно проводить потоки.
В условии на каждом ребре стоит две пропускных способности – это соответствует наличию двух трубопроводов ведущих в прямую и обратную сторону (то, что трубопроводы односторонние, может быть связано, с направлением ориентации турбин в них).
Итерации основаны на том, что когда по цепочке даётся поток частично заполненные потоком трубопроводы теряют пропускную способность на размер потока в направлении движения потока и встречный участок трубопровода формально «как бы» приобретает пропускную способность ровно на туже величину (сумма прямой и обратной пропускной способности остаётся постоянной), т.к. прежде чем загрузить этот встречный участок во избежание встречной транспортировки можно полностью выключить поток в прямом направлении.
В ответе.
1)Восстановить граф потоков по разности пропускных способностей на старом и новом графе
2)построить матрицу потоков
3) дать СУММУ потоков,
а) как сумму прямолинейных потоков на каждой итерации
б) проверить совпадение с суммой выходящих из Sи
в) входящих в Fпо матрице потоков.
Динамическое программирование. Динамическое программирование. Кратчайшие пути на ориентированном графе.
(1 условная задача) Рассчитать методом динамического программирования (решения полученные другими способами не принимаются) кратчайший путь по системе дорог.
Найти кратчайший путь из SдоT.
На каждом шаге в очередном слое расставляются наименьшие возможные расстояния до Т на основе длин путей до предыдущего слоя (указаны возле стрелок) и ранее вычисленных расстояний предыдущего слоя. Результаты вычислений должны быть записаны рядом с вершинами, в противном случае в процессе проверки не возможно установить факт использования алгоритма. Кроме того, напротив каждой вершины одна из исходящих стрелок должна быть помечена как решение оптимизационной задачи поиска кратчайшего пути в этой вершине. Это даст возможность восстановить оптимальный путь.
Алгоритм решения:
В концевой вершине (в нашем случае это Т) ставится метка Z=0/галочка не ставится (в общем случае терминальные вершины образуют - некое множество, в непрерывном случае говорят о границе, которую требуется достичь).
В вершинах опирающихся на концевую (на терминальную поверхность), т.е. в вершинах первого слоя можно рассчитать целевые функции.
Общее правило целевые функции рассчитывать в тех вершинах, которые опираются только на уже рассчитанные вершины (и не опираются ни на одну нерассчитанную).
Расчет в каждом случае происходит как прибавление к большой накопленной сумме записанной в вершине, на которую опирается данная и расстояния до неё. Среди всех таких сумм берётся минимум, на соответствующем направлении ставится галочка. Против рассчитываемой вершины ставится оптимальное значение Z=…
Расчёт длится до тех пор, пока не достигнем стартовую вершину S. Перед этим обязаны рассчитать все остальные вершины, т.к. стартовая вершинаSпрямо или опосредованно опирается на все следующие за ней вершины.