Алгоритм - форд
Cтраница 1
Алгоритм Форда - Фалкерсона основан на двух процедурах: расстановки пометок и изменения потока. [1]
Рассмотрим табличный алгоритм Форда нахождения максимального потока в сети, который состоит из ряда шагов. [2]
Основой алгоритма Форда является теорема о критерии оптимальности: множество чисел Kj будут давать оптимальное расстояние от точки PI до точки PJ, если выполняется условие h - i - г hi, где ID - длительность работ между событиями Pt и PJ, Kj - ki - - ltj показывает, что строят набор маршрутов на основании приведенного равенства и критерия оптимальности. [3]
Можно использовать алгоритм Форда - Фалкерсона, видоизменив его соответствующим образом. [4]
 |
Сеть к примеру расчета максимального потока с пометками в вершинах и потоками в дугах. [5] |
Основным вычислительным достоинством алгоритма Форда - Фалкерсона является то, что помеченные и просмотренные вершины не участвуют в оставшейся части процесса; перебор производится только по помеченным непросмотренным и пек непомеченным вершинам. [6]
Оценим количество операций в алгоритме Форда и Фалкерсо-на. Каждое увеличение потока приводит к появлению дуги с нулевым или насыщенным потоком по ней. Такая дуга далее не участвует в пометке вершин. Всего дуг U, а значит, для окончания алгоритма требуется не более 0 ( pf U) операций приращения потока. Сложность алгоритма является степенной. [7]
Отметим, что для реализации алгоритма Форда - Беллмана требуется порядка п3 операций, тогда как в алгоритме Дейкстры необходимо выполнить порядка п2 операций. [8]
Здесь читатель может заметить, что алгоритм Форда - Фалкер-сона - это специальный случай вышеприведенной процедуры, когда достаточно хороший означает поток вдоль ( в) - орцепи, который насыщает по меньшей мере одно ребро цепи. Алгоритм Эдмондса - Карпа соответствует случаю, когда достаточно хороший означает поток вдоль кратчайшей ( s, 2) - орцепи. [9]
Алгоритм Дейкстры является более эффективным, чем алгоритм Форда - Беллмана, но используется только для взвешенных графов, в которых веса всех дуг неотрицательны. [10]
Стоит отметить, что такую же сложность имел алгоритм Форда - Беллмана нахождения расстояний от фиксированной вершины до всех остальных вершин. [11]
Кроме того, решение получается не постепенным увеличением какого-либо потока ( как в алгоритме Форда - Фулкерсона), а сразу конструируется максимальный поток. В общем случае сначала определяются потоки по ребрам множества Т, а затем общий максимальный поток. [12]
PJ) является соблюдение для любого звена маршрута соотношения А - А; fa - Алгоритм аналогичен алгоритму Форда для отыскания кратчайшего маршрута. Единственное отличие состоит в предварительном шаге, где строятся наборы маршрутов: в первом случае - по минимальной длительности, а во втором - по максимальной. [13]
Алгоритмы Эдмондса - Карпа и Диница - Карзанова полиномиальны при этих точных вычислениях с действительными числами, тогда как алгоритм Форда - Фалкерсона даже не сходится. [14]
В случае, когда моделью для расчета производственной мощности ХТС служит сеть произвольного вида, вычисление пропускной способности может базироваться на алгоритме Форда - Фалкер-сона [55, 66.], излагаемом в разделе 2 этой главы. [15]
Страницы: 1 2