стся показать, что коммивояжер есть NP-полная задача, то отсюда следует, что и оптимизационная задача о коммивояжере будет столь же сложна. Таким образом, хотя в теории NP-полных задач рассматриваются только задачи распознавания, выводы этой теории вполне применимы к оптимизационным задачам. В работе [1] строго доказано, что многие задачи распознавания и в частности коммивояжер не проще соответствующих оптимизационных задач.
Как уже отмечалось, теория NP-полных задач ограничивается только задачами распознавания. Это объясняется тем, что задачи распознавания имеют очень естественный формальный эквивалент, удобный для изучения методами теории вычислений. Этот эквивалент называют «языком» и определяют следующим образом.
Для любого конечного множества символов (называемого алфавитом) обозначим через X* множество всех конечных цепочек, составленных из символов алфавита Е. Такие цепочки мы будем называть словами. Например, если X = {ОЛ}, то состоит из пустого слова «8», а также слов О, 1, 00, 01, 10, 11, ООО, 001 и всех других конечных слов, состоящих из нулей и единиц. Любое подмножество L g X* будем называть языком в алфавите Х- Таким образом, множество {01, 001,111,1001} является языком в алфавите 0,1. Языком также является множество квадратов целых чисел в двоичной системе, а также само множество {0,1}. Соответствие между задачами распознавания и язьпсами устанавливается с помощью схем кодирования, которые обычно применяются для представления индивидуальной задачи для решения ее компьютером.
Напомним, что схема кодирования е задачи II разбивают слова из 2* на три класса: слова, не являющиеся кодами индивидуальных задач из II; слова, являющиеся кодами индивищуальных задач из II с отрицательным ответом на вопрос, и слова, являющиеся кодами индивидуальных задач с положительным ответом на вопрос. Третий класс слов как раз и есть тот язык, который ставится в соответствие задаче II при кодировании е и обозначается через ЦП, е)
т / гг \ JZ есть алфавит схемы кодирования, а Х- код индивидуальной задачи; / е Гц при схеме кодирования.
При применении формальной теории NP-полноты к задачам распознавания будем говорить, что некоторый результат имеет место для задачи II при схеме кодирования, если этот результат имеет место для языка ДП,). 388
Заметим, что если вести изложение в стиле, не зависящем от кодирования, то теряется связь с формальным понятием «длина входа». Поэтому необходим некоторый параметр, через который можно выразить временную сложность. Удобно считать, что с некоторой задачей распознавания связана не зависящая от схемы кодирования функция Length: Du -> Z*, которая полиномиально эквивалентна длине кода индивидуальной задачи, получаемой при любой разумной схеме кодирования. Полиномиальная эквивалентность понимается в следующем смысле: для любой разумной схемы кодирования е задачи II существует два полинома Р и Р такие, что если I е Dn слово X есть код индивидуальной задачи / при кодировании е, то Length(/) < Р(\Х\) и\Х\<Р (Length [i]), где \Х\ - длина словах.
В задаче коммивояжер можно получить
Length [\] = т + log2 + max {log2d (С/, Q); С/, Cj е С}.
Так как любые две разумные схемы кодирования задачи II дают полиномиально эквивалентные длины входов, то диапазон для выбора функции Length очень широк, а получаемые результаты будут верны для любой функции Length, удовлетворяющей сформулированным условиям.
12.5. Детерминированная машина Тьюринга и класс Р
Для того чтобы формализовать понятие алгоритм необходимо зафиксировать определенную модель процесса вычисления. Далее такой моделью будет служить детерминированная одноленточная машина Тьюринга (сокращенно ДМТ), которая схематически изображена на рис. 12.2.
| Устройство управления | |
| | читающая (пишущая) головка |
| | | | | |
-3 -2
О 1 2 Рис. 12.2
Машина Тьюринга состоит из управляющего устройства с конечным числом состояний, читающей / пишущей головки, которая может считывать и записывать символы, и неограниченной в обе стороны ленты, разделенной на бесконечное число одинаковых ячеек, занумерованных числами..., -3, -2, -1, О, 1, 2, 3,....
Программа для ДМТ или ДМП-программа определена следующими компонентами: 1) конечным множеством Г-символов, которые записываются на ленте подмножеством I с Г входных символов и выделенным пустым символом b (Z Г \ Е\ 2) конечным множеством состояний в котором выделены начальное состояние и два заключительных состояния qy, qj 3) функция перехода 6: {Q\{qy,qN}xr-QxГ{-1,1}.
Работа программы определяется следующим образом. Входом для детерминированной программы является слово х е Слово записывается на ленте в ячейках с номерами 1,2, jc по одному символу в ячейке. Все другие ячейки в начальный момент времени содержат пустой символ и называются пустыми. Программа начинает работу, находясь в состоянии qo. При этом читающая/пишущая находится под ячейкой с номером 1.
Далее процесс вычислений осуществляется последовательно шаг за шагом. Если текущее состояние q есть qy или qi, результатом будет «да», если q = qyU «нет», если q = q.B противном случае текущее состояние принадлежит множеству Q \ { qy, qN}, при этом головка читает на ленте некоторый символ S е Ги определено значение 5 (,5. Предположим, что S (q,S) = {q\ S\ А). В этом случае головка стирает S и пишет на этом месте 5 и сдвигается на одну ячейку влево, если Д = -1 или на одну ячейку вправо, если Л = +1. Одновременно управляющее устройство переходит из состояния q в q\Ha этом заканчивается один «шаг» процесса вычисления и программа готова к выполнению следующего шага.
Пример простой ДМТ-программы представлен на рис. 12.3.
Г= {0,1,Ь}, S = {0,1} е = (qo, qu qi, Чъ. 4, Яу, Ы
| | | |
| (0, 0,+1) | (0,1,+1) | |
| {Я2,Ь,-\) | (3,,-1) | {Яы.Ь,-\) |
| (Яу,Ь,-1) | (Яы,Ь,-\) | (я,Ь,-1) |
| (qs.b,-\) | (7,,-1) | {Яы,Ь,-\) |
Рис. 12.3. Пример ДМТ-программы
м={г,д,5)