Алгоритм - форд
Cтраница 2
Как видим, полученные условия (4.19), являющиеся результатом решения задачи для рассматриваемого случая одиночного прибора, достаточно просты и требуют не более ЛГ проверок выражения (4.19), что намного проще, чем выполнение алгоритма Форда - Фал керсона. [16]
 |
Двухполюсная сеть с секцией. 202. [17] |
Прежде всего заметим, что если все секции, содержащиеся в сети, описывающей ХТС, двухполюсные, то каждая из них по способу, изложенному в разделе 3 главы IV, приводится к последовательной цепочке дуг, так что в этом случае мы снова придем к сети без секций, которая может быть рассчитана посредством алгоритма Форда и Фал-керсона. [18]
Алгоритм Форда может быть использован для отыскания максимального пути таких графов. [19]
Заметим, что важной особенностью оценки числа шагов в алгоритме Эдмондса - Карпа, полученной в теореме 2.2.3, является то, что она не зависит от пропускных способностей. Этот факт важен даже в случае целочисленных пропускных способностей, поскольку может быть так, что алгоритм Форда - Фалкерсона ( при очень неудачном выборе увеличивающих цепей) будет выполняться гораздо дольше, чем версия Эдмондса - Карпа. [20]
Естественно, что если результатом работы алгоритма является действительное число, то это означает, что алгоритм может вычислять аппроксимации с произвольно заданной точностью. Можно показать, что удачные модификации алгоритмов Эдмондса - Карпа и Диница - Карзанова будут полиномиальными в этом смысле, тогда как алгоритм Форда - Фалкерсона даже не сходится. [21]
А - некоторое подмножество элементарных интервалов, определяющее некоторый разрез в сети-аналоге. Однако непосредственное применение условий (4.14) невозможно, так как требуется полный перебор всех подмножеств элементарных интервалов, что намного сложнее, чем непосредственное построение потока по алгоритму Форда - Фал керсона. [22]
Трудности начинают возникать даже если числа в задаче целые. Для примера рассмотрим случай, когда все пропускные способности в сети целочисленные. Мы отмечали, что алгоритм Форда - Фалкерсона, начиная работу с нулевого потока, всегда приводит к максимальному потоку не более чем за t итераций, где t - максимальное значение величины потока. Полиномиален ли такой алгоритм. Но можем ли мы считать его полиномиальным, если с ( и, v) весьма велики. [23]
В теории графов широко распространены задачи отыскания наибольшего потока через заданную сеть. Подобные задачи решаются не только для определения потока, но и для определения максимального па-росочетания. Для решения таких задач обычно используется алгоритм Форда - Фалкерсона. [24]
Для решения этой задачи строят график упорядоченных событий, где задано время продолжительности работ и предполагается наличие хотя бы одного пути, состоящего из конечного числа звеньев и приводящего из начального события в нами выбранное конечное. Доказывается, что эта задача может быть сведена к задаче целочисленного программирования и решение этой задачи существует. Для выбора кратчайшего маршрута используются алгоритм Форда и алгоритм Форда-Фалкерсона. [25]
Ранний срок свершения события - это наиболее раннее время свершения данного события относительно начала выполнения комплекса работ. Отметим, что в реальной крупной сети число путей от ее начала до любого события, расположенного ближе к концу, может быть и очень велико. Поэтому прямо использовать приведенное выше определение для расчета ранних сроков событий не представляется возможным. Для этого используется специальный алгоритм, называемый алгоритмом Форда, существенно сокращающий объем проводимых вычислений: 1) для начального события сети всегда tpl 0; 2) для каждого последующего события по порядку выбирается максимум по всем его предкам tpj - max tpi у. L) в столбце таблицы равно числу предков у данного события; максимальное значение как-либо выделяется и используется для расчетов ранних сроков последующих событий. [26]
Сравнение вариантов ведется в первую очередь по длине кабеля. Соизмеримые пути сравниваются по степени заполнения разреза кабельной трассы. Пошаговый анализ в случае разветвления трасс определяет путь с меньшим числом перегибов. Критерием при размещении кабелей на конструкциях заданного типа является сведение к минимуму ненужных пересечений кабелей при переходах от разреза к разрезу или от трассы к трассе. В основу решения задачи кабельных разводок положены идеи алгоритмов Форда - Фулкерсона, а также принципы динамического программирования. [27]
Страницы: 1 2