Cтраница 1
Прямой алгоритм для вычисления H ( v) требует 0 ( пг) времени. В данном случав предполагается использование хорошего алгоритма для вычисления объединений множеств, в результате чего алгоритм имеет почти линейную трудоемкость. Каждая вершина получает метку Н точно один раз. Если ( и, w) - следующая для обработки обратная дуга, то каждая не помеченная к данному моменту вершина, исключая w, на пути из w в и имеет метку Н, равную w, я может быть так помечена. [1]
Прямой алгоритм для проблемы выполнимости требует примерно 2Л шагов для формулы с п переменными. Неизвестно, существуют ли неэкспоненциальные алгоритмы для проблемы выполнимости. [2]
Структурная схема алгоритма Евклида. [3] |
Прямой алгоритм состоит из простой последовательности шагов, которые выполняются только один раз в порядке их следования. На практике прямые алгоритмы встречаются редко, например когда требуется производить расчеты громоздких формул с большой точностью. [4]
Прямые алгоритмы ( Клейна, метод потенциалов) осуществляют итеративную коррекцию допустимого потока заданной величины. Они сводятся к последовательному исключению отрицательных контуров в графе приращений за счет ввода циклических потоков, причем на каждом шаге ликвидируется одно из нарушенных условий оптимальности. По существу, эти алгоритмы являются переложением для потоковых задач прямого симплекс-метода. [5]
Структурная схема алгоритма Евклида. [6] |
Примером прямого алгоритма является приведенная на рис. 15 - 1 структурная схема алгоритма для определения значения полинома. [7]
Доказательство конечности прямого алгоритма состоит из двух частей, связанных необходимым порядком следования. Сначала используя правило выбора ведущего столбца, докажем, что rs лексикографически возрастает от таблицы к таблице. Затем при помощи этого результата и свойств, которыми обладают допустимые правила выбора производящей строки, покажем, что условие rs - 0 ( условие оптимальности) должно иметь место после конечного числа преобразований. [8]
Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых полностью целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. [9]
Таким образом при равноценной точности прямой алгоритм реконструкции для случая веерных проекций ОПФСВП принципиально значительно более трудоемок, чем универсальный алгоритм ОПФСЭПП, и технико-экономическая оправданность его использования должна критически анализироваться в каждом конкретном случае разработки систем ПРВТ. Целесообразность его использования не вызывает сомнений лишь в задачах, требующих реконструкции в темпе сбора измерительных данных, и обусловлена наличием быстродействующего специализированного процессора ОПФСВП, способного выполнить необходимый объем вычислений по свертке и взвешенному обратному проецированию каждой веерной проекции за цикл измерения следующей проекции. [10]
Работа данной программы построена на прямом алгоритме симплекс-метода с верхними ограничениями на переменные. [11]
Таким образом, при одинаковой точности прямой алгоритм реконструкции для веерных проекций ОПФСВП принципиально значительно более трудоемок, чем универсальный алгоритм ОПФСЭПП, и оправданность его использования должна критически анализироваться в каждом конкретном случае разработки систем ПРВТ. [12]
Чтобы показать структуру отсекающей плоскости в прямых алгоритмах, рассмотрим этот алгоритм и решим пример. [13]
Чтобы получить короткое и не слишком громоздкое представление о прямом алгоритме и доказательстве его конечности, мы обычно не будем делать различия между стационарными и переходными циклами. [14]
Для первых четырех задач, представленных в предыдущем разделе, довольно легко разработать прямые алгоритмы с полиномиальной оценкой для времени. [15]