Задачи распознавания и кодирование

Из соображений удобства теория NP-полных задач строится только для задач распознавания свойств. Как было сказано, эти задачи имеют только такие решения, как «да» или «нет». Заметим, что задача распознавания II состоит из двух множеств: множества Du всех возможных индивидуальных задач и множества Yn (Y,, с Dn) индивидуальных задач с ответом «да».

Стандартная форма, которую мы будем применять для описания задач, состоит из двух частей. В первой части дается описание условий задачи в терминах различных компонент: теории множеств, теории расписаний, теории графов и т.п. Во второй части в терминах условий формулируется вопрос, предполагающий ответ «да» или «нет». Это описание определяет множества YM и Dn. Индивидуальная задача принадлежит Dn только в том случае, если она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условий, и принадлежит Yn только в том случае, если ответом на вопрос задачи будет «да».

Приведем в качестве примера задачу распознавания «Коммивояжер».

Условия. Заданы конечное множество городов С р С2, ..., С ), расстояние d(Cr С.) е Z+ для каждой пары городов С., С.е Си граница В е Z+, где jL+ — положительные целые числа.

вопрос. Существует ли маршрут, проходящий через все города из С, длина которого не превосходит В? Иными словами, существует ли последовательность <Стс( 1), Сп(2), ..., Сп(т)> элементов С, такая, что

Этот пример служит для иллюстрации важного приема — получения из оптимизационной задачи соответствующей задачи распознавания. Если в оптимизационной задаче ищется решение на минимум (например, минимум затрат при производстве продукции), то этой задаче можно поставить в соответствие задачу распознавания, в которой в качестве дополнительного параметра будет выступать числовая граница В (например, маршрут длиной не более В).

Аналогичным образом задача распознавания может быть получена из задачи максимизации. В этом случае достаточно условие «не превосходит» заменить условием «не меньше».

Следует отметить, что задача распознавания не может быть сложнее соответствующей оптимизационной задачи. Например, если в задаче коммивояжера можно за полиномиальное время найти маршрут минимальной длины, то ясно, как за полиномиальное время можно решить соответствующую задачу распознавания. Для этого находится маршрут минимальной длины, вычисляется его длина и сравнивается с заданной границей В. Поэтому, если удастся показать, что «Коммивояжер» есть NP-полная задача, отсюда будет следовать, что и оптимизационная задача о коммивояжере столь же сложна. Таким образом, хотя в теории NP-полных задач рассматриваются только задачи распознавания, выводы этой теории вполне применимы к оптимизационным задачам. В работе [23] строго доказано, что многие задачи распознавания, и в частности «Коммивояжер», не проще соответствующих оптимизационных задач.

Как уже отмечалось, теория NP-полных задач ограничивается только задачами распознавания. Это объясняется тем, что задачи распознавания имеют очень естественный формальный эквивалент, удобный для изучения методами теории вычислений. Этот эквивалент называют «языком» и определяют следующим образом.

Для любого конечного множества символов X (называемого алфавитом) обозначим через X* множество всех конечных цепочек, составленных из символов алфавита X- Такие цепочки будем называть словами. Например, если X = {0, 1}, то X* состоит из пустого слова «Ь», а также слов 0, 1, 00, 01, 10, 11, 000, 001 и всех других конечных слов, состоящих из нулей и единиц. Любое подмножество LcX* будем называть языком в алфавите X. Таким образом, множество {01, 001, 111, 1001} является языком в алфавите 0, 1. Языком также будет множество квадратов целых чисел в двоичной системе, а также само множество {0, 1}.

Соответствие между задачами распознавания и языками устанавливается с помощью схем кодирования, которые обычно применяются в целях представления индивидуальной задачи для решения ее на компьютере.

Напомним, что схема кодирования е задачи 11 разбивает слова из X* на три класса:

  • • слова, не являющиеся кодами индивидуальных задач из 11;
  • • слова, являющиеся кодами индивидуальных задач из II с отрицательным ответом на вопрос;
  • • слова, являющиеся кодами индивидуальных задач с положительным ответом на вопрос.

Последний класс слов и есть тот язык, который ставится в соответствие задаче IIпри кодировании е и обозначается через ЦП, е):

При применении формальной теории NP-полноты к задачам распознавания будем говорить, что некоторый результат имеет место для задачи II при схеме кодирования е, если этот результат имеет место для языка ЦП, е).

Заметим, что если вести изложение в стиле, не зависящем от кодирования, то теряется связь с формальным понятием «длина входа». Поэтому необходим некоторый параметр, через который можно выразить временную сложность. Удобно считать, что с некоторой задачей распознавания связана независящая от схемы кодирования функция Length: Dn —> Z+, которая полиномиально эквивалентна длине кода индивидуальной задачи, получаемой при любой разумной схеме кодирования. Полиномиальная эквивалентность понимается в следующем смысле: для любой разумной схемы кодирования е задачи II существуют два полинома Р и Р', такие, что если I g Dn и слово X есть код индивидуальной задачи I при кодировании е, то Length(I) < Р(|Х|) и |Х| < P'(Length(I)), где |Х| — длина слова X.

В задаче «Коммивояжер» можно получить

Так как любые две разумные схемы кодирования задачи II дают полиномиально эквивалентные длины входов, то диапазон для выбора функции Length очень широк, а получаемые результаты будут верны для любой функции Length, удовлетворяющей сформулированным условиям.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >