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


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


123

решить быстро. В этом случае вы могли бы уверенно заявить: «Я не могу найти эффективного алгоритма, потому что такого алгоритма не существует».

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

Мы предлагаем подходы, позволяющие найти достойный выход из положения: это методы доказательства того, что та или иная задача так же трудна, как и большое число других задач, признанных очень трудными и не поддающимися усилиям специалистов в течение многих лет. Такие методы изложены в теории так называемых NP-полных задач.

Используя изложенные в этой главе подходы и методы, вы могли бы доказать NP-полноту задачи о выпуске новой продукции и таким образом установить ее эквивалентность всем другим задачам этого класса. В этом случае можно было бы смело отправиться к шефу и сообщить: «Я не могу найти эффективного алгоритма, но этого никто не может сделать». В этом случае по крайней мере ваш руководитель будет знать, что нет смысла увольнять вас и брать на работу другого специалиста. Если же говорить серьезно, то проблема решения задачи после выявления ее NP-полноты не исчезает, а работа над ней только начинается. Знание же этого факта дает важную информацию о том, какие методы окажутся наиболее перспективными. В этом случае не следует пытаться разработать эффективный точный алгоритм, а сосредоточить внимание на получении иных, более скромных результатов. Например, попытаться разработать эффективные алгоритмы, позволяющие решать различные частные случаи поставленной общей задачи. Можно заняться отысканием алгоритма, хотя и не гарантирующего быстрого решения во всех случаях, однако работающего быстро в большинстве ситуаций. И, наконец, можно ослабить постановку задачи, потребовав при разработке алгоритма проектирования нового вида продукции вьшолнения не всех требований на значение характеристик продукции, а только части из них. Иными словами основное предназначение теории NP-полных задач состоит в том, чтобы помочь разработчикам алгоритмов и направить их усилия на выбор таких подходов к решению задач, которые вероятнее всего приведут к практически полезным алгоритмам.



12.1. Задачи, алгоритмы, сложность

В дальнейшем будут использо-

□У1ассовая задача определяется: [.Общим списком всех ее ---------- дных параметров

ные ПО сложности задачи», а также

некоторые другие термины.

Рассмотрим понятие «задача». Под массовой задачей (или просто задачей) мы будем понимать некоторый общий вопрос, на который необходимо дать ответ. Обычно задача содержит несколько параметров или свободных переменных, конкретные значения которых не определены. Далее массовую задачу назовем «задача II», и определяется она следующей информацией: 1) общим списком всех ее параметров; 2) формулировкой тех свойств, которым должно удовлетворять решение задачи. Индивидуальная задача I может быть получена из массовой, если всем параметрам задачи II присвоить конкретные значения.

В качестве примера рассмотрим классическую задачу коммивояжера. Параметры этой задачи состоят из конечного набора «городов» С = {С1, С2, Cw} и расстояний d (Ci, Cj) между каждой парой городов (С/, Cj) из С. Решение задачи - это такой упорядоченный набор < Сл;(1), С7с(2), Ск{т) > заданных городов, который минимизирует величину

Z (1(Слг(0,Слг(/ + 1)) + с1(Слг(т),Слг(1)). /=1

Это выражение дает длину маршрута, начинающегося в городе Сл;(1), проходящего последовательно через все города и возвращающегося в Ск(\) непосредственно из последнего города Ск(т), Индивидуальная же задача коммивояжера, указанная на рис 12.1, задается следующим образом: С = (С1, С2, СЗ, С4);

(С1,С2)= 10(С1,СЗ) = 5;

rf(C2,C4) = 9,(C2,C3) = 6;

rf(Cl,C4) = 9,(C3,C4) = 3.

Последовательность <С1,С2,С4,СЗ> представляет собой решение задачи, поскольку соответствующий маршрут имеет минимальную возможную длину равную 27.

2. Формулировкой свойств, которым должно удовлетворять решение задачи.

Индивидуальная задача может быть получена из массовой если всем параметрам массовой задачи присвоить конкретные значения.



Под алгоритмом будем понимать общую, выполняемую шаг за шагом процедуру реше- ния задачи. Будем говорить, что алгоритм решает массовую задачу, если он применим для любой индивидуальной задачи, полученной из данной массовой.

Рис. 12.1

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

В большинстве случаев, учитывая размерность решаемых задач, исследователя интересует наиболее эффективный алгоритм решения. Понятие эффективности связано со всеми вычислительными ресурсами, необходимыми для работы алгоритма. Однако под «самым эффективным алгоритмом» понимается самый быстрый, так как именно быстродействие алгоритма является доминирующим фактором, определяющим пригодность конкретного алгоритма для практики. Время работы алгоритма удобно выражать в виде функций от одной переменной, характеризующей размер индивидуальной задачи, т.е. объема входимых данных, требуемых для описания этой задачи. Такой подход удобен, так как в дальнейшем сравнительная сложность задачи будет оцениваться через ее размеры. Часто размер задачи определяется неформально. Например, для определения размера в задаче коммивояжера используется число городов. Кроме числа городов в этой задаче важно учитывать расстояния между m городами, которые представляют собой т (т - \) / 2 чисел. Чтобы учесть 378

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