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


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


125

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

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

В настоящее время пока неизвестны удовлетворительные объяснения, почему эти алгоритмы работают успешно и неизвестны способы заранее прогнозировать хорошую работу того или иного экспоненциального алгоритма при решении практических задач.

С другой стороны, полиномиальные алгоритмы позволяют делать такие прогнозы, поскольку полиномиальные функции значительно более адекватно оценивают время работы алгоритмов.

Хотя алгоритмы, имеющие временную сложность типа п или 10«, не могут считаться эффективными с практической точки зрения, естественно возникающие «полиномиальные задачи» обычно требуют для своего решения (в самом худшем случае) времени порядка гг или причем коэффициенты полиномов не слишком велики. Алгоритмы, обладающие такими оценками, можно считать «эффективными».

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

Рассмотрим сначала схемы кодирования. Предположим, например, что решаемая задача определена на графе G(F,£), где V- множество вершин, Е - множество ребер и каждое ребро понимается как неупорядоченная пара вершин. Условия этой задачи могут быть описаны (табл. 12.3) либо списками всех вершин и ребер, либо с помощью матрицы инценденций графа, либо составлением для каждой вершины списка всех вершин, имеющих с данной общее ребро («список соседей»).



Таблица 12.3

Схема кодирования

Цепочка символов (слово)

Длина

Списки вершин и ребер

Списки соседей

(F[2])(F[1] F[3])(F[2])

Строки матрицы инценденций

0100/10101001010000

Эти схемы кодирования для одного и того же города могут дать входы разной длины. Однако легко сравнить (табл. 12.4), что получаемые входы отличаются друг от друга не более чем полиномиальным образом, т.е. любой алгоритм, имеющий полиномиальную временную сложность при одной из этих схем кодирования, будет также обладать полиномиальной временной сложностью при остальных схемах. Действительно, оценим длины схем кодирования для графа, различные способы кодирования которого представлены в табл. 12.3 с помощью табл. 12.4.

Таблица 12.4

Схема кодирования

Нижняя оценка

Верхняя оценка

Списки вершин

4F+ 10е

4F+ 10e + (F+2e)lgF

Список соседей

2F+8e

2F+8e + 2e \gV

Матрица инценденций

V2+V-\

V2+V-\

Здесь использованы обозначения: F = К; ll = е. Поскольку е<1, эти оценки показывают, что длины входов отличаются друг от друга не более чем «полиномиальным образом».

Формально трудно определить понятие разумности кодирования, хотя следующие два условия охватывают важные требования, связанные с этим понятием: 1) код любой индивидуальной задачи I должен быть сжатым, т.е. не содержать избыточной информации или символов; 2) числа, входящие в условие задачи I, должны быть представлены в двоичной системе счисления (или десятичной, или восьмеричной, или иметь другое основание, но только не 1).

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



Таблица 12.5

Моделируемая машина В

Моделирующая машина А

Машина Тьюринга с 1 лентой (1 МТ)

0{Т{п))

0{T{n))\gT(n)

Машина Тьюринга с К лентами (КМТ)

0{Ап))

о(т) \gm

Машина произвольного доступа (МПД)

0{f{n))

о{Ап))

Здесь показано время, требуемое машине А для моделирования алгоритма сложности Т(п) на машине В, При дальнейшем исследовании проблемы можно ожидать, что любая другая разумная модель вычислительной машины будет эквивалентна по сложности перечисленным моделям.

12.3. Труднорешаемые задачи

к числу NP-полных задач относится много таких, которые используются при анализе экономических процессов математическими методами. Это задачи целочисленного программирования, задачи оптимизации времени выполнения инвестиционных проектов, задачи оптимизации на графах, задачи теории расписаний и многие другие.

После обсуждения формального содержания понятия «трудноре-шаемая задача» рассмотрим современное состояние знаний об этих задачах.

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

Вторая ситуация может возникнуть, например, если в задаче коммивояжера в качестве дополнительного параметра фигурирует число В и требуется найти все маршруты длины, не превосходящей В, Для этого достаточно легко можно построить индивидуальную задачу коммивояжера, в которой имеется экспоненциальное число маршрутов, длина которых не превосходит В. Для этого достаточно найти максимальное расстояние между парой городов d(Ck,Cl) и далее умножить это число на количество городов т. Тогда, положив В = md(Ck, СГ), получим искомый пример. Следовательно, в этой ситуации не существует алгоритма с полиномиальной временной сложностью, который перечисляет все решения.

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