Cтраница 2
Мы доказали, что определенный формулой (6.6) алгоритм является центральным. Оценим его комбинаторную сложность. [16]
В структурном распознавании образов каждый класс объектов характеризуется при помощи определенного множества взаимосвязей между частями объектов из этого класса. Главное внимание уделяется комбинаторной сложности и однозначности, которые присущи этой совокупности связей. Поэтому вместо методов анализа ошибок, типичных для статического распознавания образов, в структурном распознавании образов выясняются возможности методов построения покрытий для порождения решающих правил. Метод покрытия множества Михальского [19] или процедуры восстановления грамматик, обзор которых дан Фу и Бутом [10], Бирманом и Фельдманом [1], Пао [23], являются частными случаями общей схемы построения покрытий, которая, по нашему мнению, характеризует структурное распознавание образов. [17]
В случае когда T ( ker9l) - замкнутое подмножество в гильбертовом пространстве, существует единственный сплайновый алгоритм ф3, и он централен и линеен. В силу линейности, комбинаторная сложность алгоритма мала, так как можно воспользоваться методом проведения вычислений заранее. [18]
Рассматриваются одноточечные итерации максимального порядка для решения нелинейного уравнения / 0 в банаховом пространстве. Если / конечномерно, то комбинаторная сложность этих методов линейна по числу используемых скалярных элементов информации. Это дает хорошие оценки на индекс сложности. [19]
Для обоих этих случаев определена минимальная комбинаторная сложность. [20]
Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И / ИЛИ-дерева, не руководствуясь при этом какими-либо эвристиками. Для сложных задач подобные процедуры весьма не эффективны из-за большой комбинаторной сложности пространства поиска. В связи с этим возникает необходимость в эвристическом управлении поиском, направленном на уменьшение комбинаторной сложности за счет исключения бесполезных альтернатив. Управление эвристиками, излагаемое в настоящем разделе, будет основано на численных эвристических оценках трудности задач, входящих в состав И / ИЛИ-графа. Программу, которую мы составим, можно рассматривать как обобщение программы поиска с предпочтением в пространстве состояний гл. [21]
Рассматриваются оптимальные методы решения задач математической физики. Для параболических дифференциальных уравнений предложен асимптотически оптимальный алгоритм с линейной комбинаторной сложностью. [22]
Комбинаторная сложность оптимального по точности алгоритма может быть большой. В этой главе мы будем изучать линейные алгоритмы; для таких алгоритмов комбинаторная сложность заведомо мала. [23]
В § 4 рассматривается решение нелинейных скалярных уравнений при помощи нелинейного информационного оператора. Приводится основанный на работе Миккелли и Мирэнкера [75] интерполяционный центральный алгоритм, комбинаторная сложность которого пропорциональна log. Этот алгоритм асимптотически оптимален по сложности. [24]
Стягивая Т на Т, состоящий из шаров, продеформируем диск ф ( с неподвижной границей) в. Более того, этот диск г имеет ( по его построению) комбинаторную сложность с (); Jmk ( s ( m), где целое J 0 зависит от группы G. Теперь, полагая s - Si, / / sj в случае ( В) и, соответственно, г 2 5 [ 1 sJ / 2 ], tJ в случае ( А), получаем второе требуемое в предложении 6.37 свойство диска. Это завершает доказательство предложения. [25]
К счастью, для задач составления расписаний мы можем показать, что и в частном случае, когда времена выполнения равны 2 или даже 1 ( но при наличии ограничений предшествования), они все еще остаются yVP - полными. Следовательно, в некотором смысле структура ограничений предшествования вбирает в себя всю комбинаторную сложность, которая содержалась в больших временах выполнения. [26]
Оптимальный по точности алгоритм минимизирует погрешность, но не обязательно сложность, поскольку его комбинаторная сложность может быть большой. В качестве примера рассмотрим решение системы линейных уравнений Лх Ь, где А - невырожденная хл-матрица, а Ь - xl - вектор. [27]
ОТ, нелинейные уравнения, одна переменная, многоточечные итерации, сложность Рассматривается итеративное решение скалярных нелинейных уравнений. Как и у Кунга, Трауба [74] ( Computational complexity of one-point and multipoint iteration), комбинаторная сложность включается в индекс сложности. [28]
Разумеется, можно указать игры, сочетающие в себе черты комбинаторных и азартных игр. К числу таких игр относится, например, триктрак вместе со своими довольно многочисленными современными разновидностями, а также разного рода карточные пасьянсы, где неопределенность обусловливается, с одной стороны, случайным расположением карт в колоде, а с другой - комбинаторной сложностью конфигураций, составленных из открытых карт на столе. [29]
Программа, которую мы составили, демонстрирует основные принципы программирования игр. Но практически приемлемая реализация таких сложных игр, как шахматы или го, потребовала бы привлечения значительно более мощных методов. Огромная комбинаторная сложность этих игр делает наш наивный перебор-ный алгоритм, просматривающий дерево вплоть до терминальных игровых позиций, абсолютно непригодным. Этот вывод иллюстрирует ( на примере шахмат) рис, 15.1: пространство поиска имеет астрономические размеры - около 10 позиций. Можно возразить, что в дереве на рис. 15.1 встречаются одинаковые позиции. Однако было показано, что число различных позиций дерева поиска находится далеко за пределами возможностей вычислительных машин обозримого будущего. [30]