Cтраница 1
Недетерминированный алгоритм ( при одном и том же входе) может действовать по-разному, в зависимости от того, какие произвольные числа будут выбраны. [1]
Постройте недетерминированный алгоритм с емкостной сложностью О ( п), выясняющий, пусто ли множество, представленное произвольным полурасширенным регулярным выражением. Почему ваш алгоритм не срабатывает, когда вы пытаетесь узнать, представляет ли данное регулярное выражение все цепочки. [2]
Например, недетерминированный алгоритм решения задачи коммивояжер можно было бы построить, используя в качестве стадии угадывания просто выбор произвольной последовательности городов, а в качестве стадии проверки упомянутую, полиномиальную процедуру и проверку доказательства для задачи коммивояжер. Очевидно, для любой индивидуальной задачи / найдется такая догадка S, что результатом работы стадии проверки на входе ( /, 5) будет да в том и только в том случае, если для индивидуальной задачи / существует маршрут искомой длины. [3]
Кроме того, недетерминированные алгоритмы позволяют в компактной форме задавать множество возможных вычислений для решаемой задачи, в которой каждая реализация соответствует одному из возможных вариантов. [4]
Определяется понятие полиномиальных недетерминированных алгоритмов; они соответствуют задачам, которые решаются путем перебора, описываемого деревом поиска полиномиальной глубины. [5]
Неочевиден этот факт для всех задач, разрешаемых за полиномиальное время недетерминированными алгоритмами. Верно ли, что нет маршрута, проходящего через все города и имеющего длину, не превосходящую В. Для выяснения, имеет ли поставленный вопрос ответ да, неизвестен способ, который был бы короче, чем проверка всех ( или почти всех) возможных маршрутов. [6]
Очевидно, никакое физическое устройство не способно на неограниченное недетерминированное поведение; недетерминированные алгоритмы - это абстракция, которая позволяет нам игнорировать некоторые проблемы программирования поиска с возвращением. Сравнивая алгоритм 9.1 с алгоритмом 4.1, мы видим сильное различие: алгоритм 9.1 не содержит возвращения, если достигается тупик, потому что функция выбор заставляет исследовать все пути. [7]
По существу в доказательстве дается процедура построения, которая для любого полиномиального недетерминированного алгоритма, выходом которого будет просто истинно или ложно, и для любой входной последовательности строит одно булево выражение в конъюнктивной нормальной форме, которое является выполнимым, если и только если для этой входной последовательности алгоритм вычисляет ответ истинно. Далее, в доказательстве показывается, что построение этого булевого выражения из формального описания недетерминированного алгоритма и его входной последовательности можно выполнить за полиномиальное время. Опираясь на этот результат, можно показать, что существует последовательность таких булевых выражений, соответствующая разрядам выходной последовательности для любого алгоритма из оЛГ 3 и любой входной последовательности. [8]
Неформально класс NP можно определить с помощью понятия, которое мы будем называть недетерминированный алгоритм. [9]
Класс NP, определяемый неформально, это класс всех задач распознавания II, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время. [10]
В основном тексте книги Макконелла освещены с различной степенью детальности элементы асимптотического анализа алгоритмов, включая решения рекуррентных соотношений, дано введение в сложностные классы задач с точки зрения недетерминированных алгоритмов и описаны наиболее распространенные методы разработки эффективных алгоритмов. [11]
Чтобы понять, какие следствия будут вытекать из того, что Р содержит задачу коммивояжера или одну из многих других загадочных задач, необходимо ввести класс № У задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма. Не формально мы определяем состояние алгоритма как комбинацию адреса выполняемой в текущий момент команды и значений всех переменных. Другими словами, детерминированный алгоритм в каждый момент времени может делать только что-то одно. В недетерминированном алгоритме для любого данного состояния может быть больше одного допустимого следующего состояния; другими словами, недетерминированный алгоритм в каждый момент времени может делать больше одной вещи. Недетерминированные алгоритмы не являются в каком-либо смысле вероятностными или случайными алгоритмами; они являются алгоритмами, которые могут находиться одновременно во многих состояниях. [12]
Поясним значение термина решает в этом определении. Основное назначение полиномиального недетерминированного алгоритма состоит в объяснении понятия проверяемости за полиномиальное время, а не в том, чтобы служить реалистическим методом решения задач распознавания свойств. [13]
В основном здесь различаются детерминированные алгоритмы САР и недетерминированные алгоритмы САП. Самоорганизующиеся системы работают по самоорганизующемуся алгоритму, изменяющемуся по ходу процесса управления. [14]
Задача принадлежит классу NP, если она разрешима за полиномиальное время недетерминированным алгоритмом. [15]