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


[Старт] [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]


126

Труднорешаемостью этого вида нельзя пренебрегать и важно ее вовремя обнаружить. Этот аспект труднорешаемости задачи можно рассматривать как указание на то, что постановка задачи нереалистична, поскольку запрашивается такой объем информации, который полностью никогда не может быть использован. В связи с этим в дальнейшем мы будем рассматривать только первый аспект труднорешаемости, т.е. будут изучаться такие задачи, длина решения которых ограничена полиномиальной функцией от длины входной информации. Первые результаты о труднорешаемости задач бьши получены Тьюрингом около 40 лет назад. Он доказал, что существуют «неразрешимые» задачи в том смысле, что вообще не существует алгоритма их решения. К ним, например, относится десятая проблема Гильберта (разрешимость в целых числах полиномиальных уравнений). Поскольку эти задачи не могут быть решены никакими алгоритмами, то тем более не могут быть решены и полиномиальным алгоритмом и, следовательно, они труднорешаемы в самом сильном смысле.

Первые примеры труднорешаемых разрешаемых задач бьши получены в начале 60-х годов в работах Хартнаниса и Стирнза, а также позднее в работах Фишера и Рабина. В число этих задач вошли задачи по теории автоматов, математической логике, формальной теории языков.

Анализ труднорешаемых задач, с одной стороны, предполагает разработку методов доказательства труднорешаемости задач, с другой стороны, ведутся работы по сравнению сложности различных задач. Основной метод, используемый для доказательства труднорешаемости задач, состоит в «сведении» их друг к другу с помощью преобразования, которое отображает любую индивидуальную задачу первого типа в эквивалентную ей индивидуальную задачу второго типа. Такое преобразование позволяет превратить любой алгоритм решения второй задачи в соответствующий алгоритм решения первой задачи. К числу примеров такой сводимости относятся примеры, приведенные в работах Данцига по сведению нескольких комбинаторных задач оптимизации к общей задаче целочисленного программирования с булевыми переменными.

Фундамент теории NP-полных задач бьш заложен в работе С. Кука, опубликованной в 1971 г. под названием «Сложность процедур вывода теории». В этой работе было получено несколько важных результатов. Бьша обоснована важность понятия «сводимость за полиномиальное время», т.е. сводимость, которая вьшолняется с помощью алгоритма с полиномиальной временной сложностью. С. Кук обратил внимание на класс задач распознавания свойств (класс NP), которые могут быть ре-



шены за полиномиальное время на недетерминированном вычислительном устройстве. Отметим, что задачей распознавания свойств называется задача, решением которой могут быть либо «да», либо «нет». Большинство не поддающихся решению задач после их переформулировки попадают в этот класс. Далее он доказал, что конкретная задача из NP, называемая задачей о выполнимости, обладает тем свойством, что всякая другая задача из класса NP может быть сведена к ней за полиномиальное время. Таким образом, если задача о выполнимости может быть решена за полиномиальное время, то любая задача из класса NP полиномиально разрешима. Если же какая-либо задача из NP труднорешаема, то задача о выполнимости также труднорешаема.

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

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

Из соображений удобства теория NP-

В теории ЫР-полных задач рассматривакяся только зада- полных задач строится только для задач чи распознавания, но выводы этой теории вполне примени-

мы к соответствующим оптимизационным задачам.

распознавания свойств. Как было упомянуто в предыдущем разделе, такие задачи имеют только возможные решения «да» или «нет». Заметим, что задача распознавания II состоит из двух множеств: множества Оц всех возможных индивидуальных задач и множества Гц (Гц с Оц) индивидуальных задач с ответом «да».



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

Приведем в качестве примера задачи распознавания, соответствующей задаче коммивояжера, следующее описание.

Пример. Заданы конечное множество С = (С1, С2„ Cm) «городов», расстояние d(C/, Cj) е для каждой пары городов С/, Cj е С и граница В G 2. (Здесь означает положительные целые числа.)

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

Е (Сл-(/),Сл-(/ + 1)) + (Слг(ш),Слг(1))<5? /=1

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

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

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

[Старт] [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]