Cтраница 3
А - алгоритм при А0 ведет себя аналогично поиску в ширину. Он, действительно, превращается в поиск в ширину, если, кроме того, положить с ( п п) для всех дуг ( п п) пространства состояний. Отсутствие эвристической силы оценки приводит к большой комбинаторной сложности алгоритма. [31]
Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И / ИЛИ-дерева, не руководствуясь при этом какими-либо эвристиками. Для сложных задач подобные процедуры весьма не эффективны из-за большой комбинаторной сложности пространства поиска. В связи с этим возникает необходимость в эвристическом управлении поиском, направленном на уменьшение комбинаторной сложности за счет исключения бесполезных альтернатив. Управление эвристиками, излагаемое в настоящем разделе, будет основано на численных эвристических оценках трудности задач, входящих в состав И / ИЛИ-графа. Программу, которую мы составим, можно рассматривать как обобщение программы поиска с предпочтением в пространстве состояний гл. [32]
Сложность ее решения может быть большой. Это означает, что во многих случаях оптимизационную задачу (3.2) нужно решать только один раз. Для нелинейных сплайновых алгоритмов идея проведения вычислений заранее в общем случае не проходит, и комбинаторная сложность таких алгоритмов может оказаться очень большой. [33]
В примерах 3.2 и 3.3 ив обсуждении, предшествующем примеру 3.2, мы уже отмечали, что в нашу постановку можно формально включить теорию алгебраической сложности. Задача минимизации комбинаторной сложности дает нетривиальный пример того, как алгебраическая сложность укладывается в рамки этой постановки. [34]
Понятия комбинаторной ( рекурсивной) сложности и линейной сложности периодической последовательности однозначно определяются для последовательностей над простым полем как минимальная длина соответственно нелинейного и линейного регистра сдвига, порождающего эту последовательность. При оценке линейной сложности ( мульти -) последовательности над модулем следует использовать не один - а серию параметров, которые можно пока условно разделить на три группы: параметры, связанные ( а) с реализацией ее ( полилинейным) регистром сдвига; ( Ь) с описанием аналитического представления ее знаков; ( с) с размерностью модуля, порожденного системой сдвигов исходной последовательности. В данной работе развивается подход к оценке сложности, связанный с первым из перечисленных направлений. Проведенные исследования показывают, что комбинаторную сложность периодической ( мульти -) последовательности можно измерять размерностью специального автомата, порождающего эту последовательность, называемого мультирегистром сдвига на диаграмме Ферре. Для оценки линейной сложности периодической ( мульти -) последовательности над модулем строится соответствующий канонический полилинейный регистр сдвига, размерность которого зависит от используемого кольца коэффициентов модуля. Устанавливаются некоторые соотношения между указанными параметрами. [35]
Эллиптическое дифференциальное уравнение с частными производными рассматривается на квадрате. Для сетки, длина шага которой равна квадратному корню из длины шага исходной сетки, построен алгоритм четвертого порядка. На исходной сетке он дает результат второго порядка. Этот алгоритм асимптотически оптимален, поскольку его комбинаторная сложность пропорциональна числу точек решетки. [36]
Задачи с ограничениями, где gt - нелинейные функции, обычно гораздо труднее решать, чем соответствующие безусловные задачи. Если функция / и все ограничения gt являются линейными функциями, то говорят о задаче линейного программирования. Можно показать, что решение лежит в вершине выпуклого многогранника, определяемого ограничениями в я-мерном пространстве. Обычный метод решения состоит в поиске нужной вершины, осуществляемом перемещением от очередной вершины к смежной. Трудные проблемы линейного программирования по существу связаны с решением задач очень высокого порядка п, которое приводит к разреженным матричным задачам. В основе трудности таких задач лежит комбинаторная сложность общего n - мерного многогранника. Если функция / либо какое-нибудь из ограничений нелинейно, то говорят о задаче нелинейного программирования. Задачи линейного и нелинейного программирования выходят за рамки этой книги. [37]