назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [ 127 ] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


127

стся показать, что коммивояжер есть 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)

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [ 127 ] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]