Cтраница 3
В этих рассуждениях не принималось в расчет то обстоятельство, что колебания содержаний на одной тарелке приводят к колебаниям и на соседних тарелках. Можно показать, что наибольшая допустимая величина отношения Л1 / 6 / / / П; равна 0 50 независимо от числа тарелок. Общий объем вычислений возрастает пропорционально числу тарелок в кубе. [31]
Довольно распространенный критерий оценки метода - скорость сходимости, и при этом считают, что чем выше скорость сходимости, тем лучше метод. Конечно, чем быстрее сходится метод, тем меньшее число итераций необходимо для получения решения с заданной точностью. Однако при оценке метода важное значение имеет не столько скорость сходимости метода, сколько общий объем вычислений, требуемый для получения решения с заданной. А общий объем вычислений зависит не только от числа итераций, но и от трудоемкости вычислений на каждой итерации. [32]
Таким образом, в методе слепого поиска число требуемых вычислений значений целевой функции весьма резко увеличивается с возрастанием размерности решаемой задачи. Аналогичные проблемы уже встречались при рассмотрении поиска оптимума методом сканирования, где для устранения трудностей с размерностью иногда может использоваться поиск с переменным шагом сканирования. Точно такой же прием можно применить и в методе слепого поиска, если после выполнения определенной серии проб дальнейший поиск ( уточнение) производить в некоторой суженной области, охватывающей найденную в предыдущей серии точку наименьшего ( наибольшего) значения функции цели. При этом вероятность попадания в заданную Д - окрестность оптимума возрастает, за счет чего можно существенно сократить общий объем вычислений. [33]
AW не равно нулю. Также заполнение в столбце b ( jk) может быть меньше, чем 6 / fe) btk так как в действительном методе RGS может иметь место взаимное уничтожение слагаемых. Этим объясняется, почему gj дает максимальное, а не действительное заполнение. Наш опыт учит, что такие случаи1) редки и когда они имеют место, то составляют лишь небольшой процент от общего объема вычислений. Поэтому действительное заполнение очень близко к § tt ] - Как бы там ни было, из. [34]
Довольно распространенный критерий оценки метода - скорость сходимости, и при этом считают, что чем выше скорость сходимости, тем лучше метод. Конечно, чем быстрее сходится метод, тем меньшее число итераций необходимо для получения решения с заданной точностью. Однако при оценке метода важное значение имеет не столько скорость сходимости метода, сколько общий объем вычислений, требуемый для получения решения с заданной. А общий объем вычислений зависит не только от числа итераций, но и от трудоемкости вычислений на каждой итерации. [35]
Другой источник альтернатив в правилах выделения операторов, аргументов и результатов возникает при рассмотрении нашего исследования с другого конца - фактической реализации найденных алгоритмов экономии. Элементарный анализ составленной программы показывает, что экономия памяти характеризуется большим объемом вычислений. Вычисление матрицы смежности U [ l: /, 1: Z ] графа несовместимости по заданным матрицам начальных R [ i: I, 1: re ] и транзитных Т [ 1: I, 1: п ] операторов ( § 4.5) требует 12хп действий, где Z - число областей действия, an - число операторов. Нахождение канонического распределения памяти и транзитных операторов требует вычисления q 21 транзитивных замыканий. В то же время, если считать в машинных командах, число элементарных операторов в символических программах исчисляется многими сотнями, а стало быть, общий объем вычислений будет выражаться десятками и сотнями миллионов машинных операций. Поэтому желательно переход от команд программы к операторам схемы сделать не таким буквальным: по возможности укрупнить операторы и сократить число величин, подлежащих экономии по общему алгоритму. [36]
Теорема 6.1 показывает, что мы ничего не теряем при исключении текущих активных и только что порожденных вершин, стоимость которых превышает стоимость решения, дающего верхнюю оценку. Теорема 6.2 показывает, что потребности в вычислительных ресурсах не увеличатся, если будут исключены вершины, не имеющие допустимого продолжения. Потребности в ресурсах могут увеличиться при использовании более строгого отношения доминирования ( теорема 6.3), но это происходит обычно в вырожденных случаях. Даже в том случае, когда соотношения () выполняются, нет никакой гарантии, что реальное время выполнения алгоритма не увеличится. Например, более сильное отношение доминирования может потребовать большего времени счета. Теоремы 6.4 и 6.5 утверждают, что соотношения () остаются в силе, когда более точная функция нижней оценки используется совместно с правилами FIFO и LIFO, но они не обязательно выполняются при использовании правил LLB или DF / LLB. На практике более точная функция нижней оценки обычно сокращает общий объем вычислений, но для того, чтобы выигрыш оказался реальным, это сокращение должно компенсировать увеличение затрат, связанных с вычислением более точной нижней оценки. [37]