Полиномиальный алгоритм

Cтраница 3

Последовательные алгоритмы размещения требуют небольших затрат машинного времени, относят их к классу полиномиальных алгоритмов со сложностью О ( п), приводящих к неоптимальным решениям. [31]

Иллюстрация венгерской теоремы. [32]

Следует отметить, что для задач, приведенных выше, не известен ни один полиномиальный алгоритм для случая произ вольных, не обязательно двудольных графов. [33]

Для доказательства того, что задача входит в оЛГУ, нужно только дать недетерминированный полиномиальный алгоритм для ее решения. [34]

Продублировав все ребра ЕМ. ОД, получаем граф с эйлеровым циклом. [35]

Можно было бы предположить, что свойства евклидовой метрики могут быть использованы для разработки полиномиального алгоритма решения этой задачи в случае множества точек, заданного на плоскости. Однако Гэри, Грэхем и Джонсон [ Qarey, Graham, Johnson ( 1976) ], Пападимитриу и Стайг-лиц [ Papadimitriou, Steiglitz ( 1976) ] и Пападимитриу [ Рара-dimitriou ( 1976) ] наряду с другими результатами о ЛФ-полноте некоторых геометрических задач доказали, что евклидова задача о коммивояжере ( ЕЗК) является ЛФ-трудной. [36]

Дана аннотированная библиография работ по приближенным полиномиальным алгоритмам решения комбинаторных задач, для которых неизвестны точные полиномиальные алгоритмы. [37]

В этой главе мы рассмотрим практические методы решения таких задач составления расписаний, Для которых отсутствуют полиномиальные алгоритмы нахождения оптимальных расписаний. [38]

Основной характер различия между этими классами, как считают многие исследователи, заключается в том, что полиномиальные алгоритмы как правило являются хорошими с точки зрения их быстродействия. В то же время экспоненциальные алгоритмы не являются таковыми и чаще всего представляют собой варианты полного перебора. Имеется распространенное мнение, согласно которому задача не считается хорошо решаемой до тех пор, пока для нее не получен полиномиальный алгоритм. Задачу будем называть труднорешаемой, если для ее решения не существует полиномиального алгоритма. Полиномиальные алгоритмы можно построить лишь тогда, когда удается более глубоко проникнуть в суть решаемой задачи. [39]

Если оптимизационная задача NP, трудна, то, как было сказано ранее скорее всего нельзя построить точный полиномиальный алгоритм решения этой задачи. [40]

Во-первых, в [19] уменьшена группа автоморфизмов, участвующих в описании, а в [20] утверждается существование полиномиального алгоритма, решающего проблему описания множества решений. При участии И. Г. Лысенка, авторам удалось объединить эти два усиления, что и нашло свое отражение в § 4 главы 1, где сформулирован соответствующий результат. [41]

В основном тексте книги Макконелла ( глава 8) сложностный класс NP вводится на основании рассмотрения недетерминированных полиномиальных алгоритмов. Здесь описан другой подход к определению класса NP - через сертификат и полиномиально проверяющий алгоритм, даются также иллюстрации вложенности классов и краткий исторический обзор. [42]

Тогда существует не более 11 положительных делителей п, сравнимых с г по модулю s, и существует полиномиальный алгоритм для определения всех этих делителей. [43]

Тогда существует не более 11 положительных делителей числа п, сравнимых с г по модулю s; есть полиномиальный алгоритм для нахождения этих делителей. [44]

В данном параграфе рассматривается ряд задач минимизации суммарного штрафа за обслуживание требований одним прибором, для которых известны полиномиальные алгоритмы решения. [45]

Страницы: 1 2 3 4