Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 97
Текст из файла (страница 97)
Заметим, что в последнем случае все узлы должны принадлежать одному компоненту связности, и процесс выбора ребер можно прекратить. Пример 1О.1. В графе на рис. 10.1 сначала рассматривается ребро (1, 3), поскольку оно имеет минимальный вес — 1О. Так как вначале 1 и 3 принадлежат разным компонентам, это ребро принимается, а узлам 1 и 3 приписывается один и тот же номер компонента, скажем, "компонент 1". Следующее по порядку возрастания веса ребро — (2, 3) с весом 12.
Поскольку 2 и 3 принадлежат разным компонентам, то это ребро принимается, и 2 добавляется в "компонент 1". Третье ребро — (1, 2) с весом 15. Но узлы 1 и 2 уже находятся в одном компоненте, поэтому данное ребро отбрасывается, и мы переходим к четвертому ребру — (3, 4). Поскольку 4 не содержится в "компоненте 1", данное ребро принимается. Теперь у нас есть остовное дерево из трех ребер, и можно остановиться. (л Этот алгоритм обработки графа с нг узлами и е ребрами можно реализовать (с помощью компьютера, а не машины Тьюринга) за время 0(т + е)обе).
Более простая реализация имеет е этапов. Номер компонента каждого узла хранится в некоторой таблице. Выбор ребра наименьшего веса среди оставшихся занимает время 0(е), а поиск компонентов, в которых находятся узлы, связанные этим ребром, — 0(нг). Если эти узлы принадлежат различным компонентам, то на просмотр таблицы для объединения всех узлов с соответствуюшими номерами нужно время 0(нг). Таким образом, обгцее время работы этого алгоритма — 0(е(е.г нг)). Это время полиномиально зависит от "размера" входных данных, в качестве которого можно неформально выбрать сумму е и нг.
' у. В. Кгиз!га! 1г„"Оп Ше яйоггеж зрапшп8 зпыгее ог" а ягар!г апг! Ше ггаче!!п8 за!езгпап ргоЫет", Ргос. АМЗ 7: ! (1956), рр.48 — 50. ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 426 При перенесении изложенных идей на машины Тьюринга возникают следующие вопросы. я Выход алгоритмов разрешения различных проблем может иметь много разных форм, например, список ребер ОДМВ. Проблемы же, решаемые машинами Тьюринга, можно интерпретировать только как языки, а их выходом может быть только ДА или НЕТ (допустить или отвергнуть).
Например, проблему поиска ОДМВ можно перефразировать так: "Для данного графа б и предельного числа И'выяснить, имеет ли С остовное дерево с весом не более И"?". Может показаться, что эту проблему решить легче, чем проблему ОДМВ в знакомой нам формулировке, поскольку не нужно даже искать остовное дерево. Однако в рамках теории труднорешаемости нам, как правило, нужно доказать, что проблема трудна (не легка), А из того, что "да/нет"-версия проблемы трудна, следует, что трудна и ее версия, предполагающая полный ответ.
° Хотя "размер" графа можно неформально представить себе как число его узлов или ребер, входом МТ является цепочка в некотором конечном алфавите. Поэтому такие элементы, фигурирующие в проблеме, как узлы и ребра, должны быть подходящим образом закодированы.
Выполняя это требование, получаем в результате цепочки, длина которых несколько превышает предполагаемый "размер" входа. Однако есть две причины проигнорировать эту разницу. Размеры входной цепочки МТ и входа неформальной проблемы всегда отличаются не более, чем малым сомножителем, обычно — логарифмом размера входных данных. Таким образом, все, что делается за полиномиальное время с использованием одной меры, можно сделать за полиномиальное время, используя другую меру. Длина цепочки, представляющей вход, — в действительности более точная мера числа байтов, которые должен прочитать реальный компьютер, обрабатывая свой вход. Например, если узел задается целым числом, то количество байтов, необходимых для представления этого числа, пропорционально его логарифму, а это не "1 байт на каждый узел", как можно было бы предположить при неформальном подсче- те размера входа.
Пример 10.2. Рассмотрим код для графов и предельных весов, который может быть входом для проблемы ОДМВ. В коде используются пять символов: О, 1, левая и правая скобки, а также запятая. Припишем всем узлам целые числа от 1 до аь В начало кода поместим значения а и предельного веса И' в двоичной системе счисления, разделенные запятой.
Если существует ребро, соединяющее узлы ! и ! и имеющее вес и, то в код записывается тройка (б ь н), где целые числа 1, у и н кодируются в двоичном виде. Порядок записи узлов ребра и порядок ребер в графе не играют роли. 10.1. КЛАССЫ Р И НР 427 Таким образом, один из возможных кодов графа на рис. 10.1 с предельным весом 1г'= 40 имеет вид 100, 101000(1, 10, 1111)(1, 11, 1010)(10, 11, 1100)(10, 100, 10100)(11, 100, 10010).
П Если кодировать входы проблемы ОДМВ так, как в примере 10.2, то вход длины и может представлять максимум 0(л/!одл) ребер. Если число ребер очень мало, то число узлов а может быть экспоненциальным относительно л. Однако если число ребер е меньше е — 1, то граф не может быть связным, и независимо от того, каковы эти ребра, не имеет ОДМВ. Следовательно, если количество узлов превосходит число н/!об и, то нет никакой необходимости запускать алгоритм Крускала — мы просто говорим: "нет, остовного дерева с таким весом не существует".
Итак, пусть у нас есть верхняя граница времени работы алгоритма Крускала, выражаемая в виде функции от а и е, например, как найденная выше верхняя граница О(е(е+ т)). Можно изменить т и е на л и сказать, что время работы выражается функцией от длины входа н, имеющей вид 0(п(п+ н)) или 0(п~).
В действительности, более удачная реализация алгоритма Крускала требует времени 0(н!оя а), но сейчас это не важно. Представленный алгоритм Крускала предназначен для реализации на языке программирования с такими удобными структурами данных, как массивы и указатели, но в качестве модели вычислений мы используем машины Тьюринга. Тем не менее, описанную выше версию алгоритма можно реализовать за 0(й) шагов на многоленточной машине Тьюринга. Дополнительные ленты используются для выполнения нескольких вспомога- тельных задач. 1.
На одной из лент можно хранить информацию об узлах и их текущих номерах компонентов. Длина такой таблицы составит 0(п). 2. Еше одна лента может применяться в процессе просмотра входной ленты для хранения информации о ребре, имеющем на данный момент наименьший вес среди ребер, не помеченных как "использованные" (выбранные). С помощью второй дорожки входной ленты можно отмечать те ребра, которые были выбраны в качестве ребер наименьшего веса на одном из предыдуших этапов работы алгоритма. Поиск непомеченного ребра наименьшего веса занимает время 0(л), поскольку каждое ребро рассматривается лишь один раз, и сравнить вес можно, просматривая двоичные числа линейно, справа налево.
3. Если ребро на некотором этапе выбрано, то соответствующие два узла помещаются на ленту. Чтобы установить компоненты этих двух узлов, нужно просмотреть таблицу узлов и компонентов. Это займет О(п) времени. 4. Еше одна лента может хранить информацию об объединяемых компонентах ( и /, когда найденное ребро соединяет различающиеся на данный момент компоненты.
В этом ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 428 ! случае просматривается таблица узлов и компонентов, и для каждого узла из компопента 1 номер компонента меняется на 1. Зта процедура также занимает 0(п) времени. Теперь нетрудно самостоятельно завершить доказательство, что на многоленточной МТ каждый зтап работы алгоритма может быть выполнен за время 0(л).
Поскольку число зтапов е не превышает п, делаем вывод, что времени 0(п ) достаточно для многоленточной МТ. Теперь вспомним теорему 8.10, утверждавшую„что работу, которую много- ленточная МТ выполняет за в шагов, можно выполнить на одноленточной МТ за 0(в') шагов. Таким образом, если миоголенгочной МТ требуется сделать 0(п') шагов, то можно построить одноленточную МТ, которая делает то же самое за 0((л~) ) = 0(п ) шагов.
Следовательно, "да/нет"-версия проблемы ОДМВ ("имеет ли граф 0 ОДМВ с обсцим весом не более И"!") принадлежит Р. 10.1.3. Недетерминированное полиномиальное время Фундаментальный класс проблем в изучении труднорешаемости образован проблемами, разрешимыми с помощью недетерминированной МТ за полиномиальное время. Формально, мы говорим, что язык Е принадлежит классу Л'Р (недетерминированный полиномиальный), если существуют недетерминированная МТ М и полиномиальная временная сложность Т(п), для которых Е = ЦМ), и у М нет последовательностей переходов длиной более Т(л) при обработке входа длины и.
Поскольку всякая детерминированная МТ представляет собой недетерминированную МТ, у которой нет возможности выбора переходов, то Р ~ ЛР. Однако оказывается, что в АТР содержится множество проблем, не принадлежащих Р. Интуиция подсказывает: причина в том, что НМТ с полиномиальным временем работы имеет возможность угадывать зкспоненциальное число решений проблемы и проверять "параллельно" каждое из иих за полиномиальное время. И все-таки, ° одним из самых серьезных нерешенных вопросов математики является вопрос о том, верно ли, что Р = Л'Р, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
