Cтраница 1
Конечность алгоритма следует из конечности множества допустимых решений. [1]
Конечность алгоритма Литтла, Мурти, Суини и Кэрел непосредственно следует из конечности числа всех циклов в рассматриваемой задаче. [2]
Конечность алгоритма Дальтона и Ллевелина доказывается так же, как и конечность первого алгоритма Гомори. При этом должны соблюдаться условия, аналогичные условиям 1) и 2) из § 3 гл. [3]
Конечность алгоритмов локальной оптимизации очевидна, так как конечно множество допустимых решений, но количество шагов и точность, как правило, оценить не удается. Отметим, что алгоритмы указанного типа не требуют никакой дополнительной памяти. [4]
Для доказательства конечности алгоритма следует выяснить только один вопрос: будет ли в итерационном процессе, состоящем из шагов 1 и 2, при решении задачи ( 3) получаться каждый раз новая вершина ир. Выглядит вполне правдоподобным, что два неоптимальных значения у и у могут давать одну и ту же вершину и. [5]
К сожалению, описанная процедура не обеспечивает конечности алгоритма. Для доказательства конечности мы должны ввести в алгоритм дополнительные условия. [6]
Однако приведенное в следствии 5.1 необходимое условие конечности алгоритма Данцига не является до статочным. [7]
Трудности создания алгоритмического обеспечения связаны, в частности, со свойствами конечности алгоритма. Естественно, алгоритм должен заканчиваться после конечного числа шагов ( это свойство называют потенциальной осуществимостью), причем число шагов является критическим параметром, определяющим эффективность ( и сложность) алгоритма. Решить алгоритмически, в принципе, можно большое число задач, но время для получения решения может быть столь большим, что практически задача остается нерешенной. Поэтому практически реализуемый алгоритм должен давать ответ после небольшого числа шагов, которые могут быть выполнены за достаточно малый промежуток времени. [8]
Таблицы 6.11 - 6.16 иллюстрируют шесть возможных случаев выбора ведущего элемента и изменения в результате итерации. Возможные исходы итераций могут быть использованы для доказательства конечности алгоритма. [9]
Составьте программу для ЭВМ, которая допускает в качестве вводимых данных программы, написанные на некотором языке программирования совместно с некоторыми дополнительными утверждениями, и которая в состоянии выработать остальные утверждения, необходимые для доказательства правильности заданной программы. Заметьте, что существование такой программы делает отладку необязательной, если не считать докааательства конечности алгоритма. В тексте показано, как проводится доказательство по индукции утверждений Р ( п), зависящих от единственного целого параметра п, но не разбирается, как доказать по индукции утверждения Р ( т, п), зависящие от двух целочисленных параметров. В этих случаях доказательство часто проводят, используя своего рода двойную индукцию, что нередко бывает неудобно. Этот принцип называется полным упорядочением. [10]
Эти рассуждения можно оформить в виде алгоритма, который и приведен ниже. Сходимость алгоритма зависит от исходного множества ключей. Чтобы избежать чрезвычайно больших затрат на вычисление С и гарантировать конечность алгоритма, в нем использовано соответствующим образом подобранное значение CL, являющееся предельным для С. [11]
Теория квадратичных методов минимизации, изложенная в начале этой главы, основана на исследовании задачи о минимуме квадратичной функции. Некоторые свойства квадратичных методов минимизации - устойчивость, идентичность генерируемых последовательностей xt - установлены, по существу, для неквадратичных минимизируемых функций [ 67; 72; 11, с. Окончательное решение вопроса о возможности применения квадратичных методов к минимизации неквадратичных функций определяется исследованием сходимости рассматриваемых методов, так как свойство конечности алгоритма ( достижение минимума за конечное число итераций) для неквадратичных минимизируемых функций, вообще говоря, не выполняется. В то же время метод наискорейшего спуска, например, характеризуется, в общем, более слабой - линейной скоростью сходимости. Практическое подтверждение этих теоретических соображений основывается на результатах решения тестовых задач различными методами и последующей их сравнительной оценке. [12]
Даже при столь отличных предположениях о характере переменных доказательства всех утверждений, от Л / до А6, остаются в силе. Поэтому на любом этапе выполнения алгоритма все эти утверждения верны. Следовательно, доказательство утверждений А1 - А6 еще не означает конечность алгоритма. [13]
Если после введения дополнительного ограничения текущая таблица перестает быть прямо допустимой, то текущее решение, представляющее собой вершину многогранника решений, не удовлетворяет этому дополнительному ограничению. Другими словами, дополнительное ограничение отсекает часть пространства решений. Если дополнительные ограничения не отсекают ни одной целочисленной точки пространства решений исходной задачи, то, вполне вероятно, после введения достаточного числа дополнительных ограничений вершины суженного множества решений будут целочисленными. Трудность состоит в систематическом получении дополнительных ограничений и доказательстве конечности алгоритма. [14]