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


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


124

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

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

Например, реализуемые конкретные задачи о коммивояжере можно описать с помощью алфавита {С, [,], /, О, 1, 2, 3, 4, 5, 6, 7, 8, 9,} при этом задача на рис. 12.1 может бьггь закодирована цепочкой символов вида: С[1] С[2] С[3] С[4] 10/5/9 6/9 3/.

Аналогичным образом могут быть закодированы и более сложные индивидуальные задачи. При такой кодирующей схеме индивидуальная задача о коммивояжере на рис. 12.1 имеет длину 32.

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

12.2. Полиномиальные алгоритмы и труднорешаемые задачи

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

Будем говорить, что функция fji) есть 0(g(n)), если существует константа С такая, что < C\g(ri)\ для всех значений « > 0. Полиномиаль-

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



ным алгоришом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна 0{Р{п)\ где Р{п) некоторая полиномиальная функция, din - входная длина.

Алгоритмы, временная сложность которых не поддается такой оценке, называются экспоненциальными.

Различие между двумя указанными типами алгоритмов становится особенно заметно при решении задач большого размера. Табл. 12.1 позволяет сравнить скорости роста нескольких типичных полиномиальных и экспоненциальных функций [20].

Таблица 12.1

Функция

Размеры

временной

сложности

0.00001

0.00002

0.00003

0.00004

0.00005

0.00006

сек.

сек.

сек.

сек.

сек.

сек.

0.001

0.004

0.0009

0.0016

0.0025

0.0036

сек.

сек.

сек.

сек.

сек.

сек.

0.001

0.008

0.027

0.064

0.125

0.216

сек.

сек.

сек.

сек.

сек.

сек.

24.3

13.0

сек.

сек.

сек.

мин.

мин.

0.001

17.9

12.7

35.7

сек.

сек.

мин.

дней

столетий

0.059

3855

2 10

1.3-10

сек.

мин.

столетий

столетий

столетий

Таблица 12.2

Функций временной сложности

На современных компьютерах

На компьютерах в 100 раз более быстрых

На компьютерах в 1 ООО раз более быстрых

100 N1

1 000N1

10 N2

31.6 N2

4.64 N3

10 N3

2.5 N4

3.98 N4

N5+6.64

N5 + 9.97

3"

N6+4.19

N6 + 6.29

Различие между полиномиальными и экспоненциальными алгоритмами проявляется еще более убедительно, если проанализировать влияния увеличения быстродействия компьютера на время работы алгорит-380



MOB. в табл. 12.2 показано, на сколько увеличатся размеры задач, решаемых за 1 ч машинного времени, если благодаря совершенствованию технологий быстродействие компьютера возрастет в 100 или 1000 раз по сравнению с современными. Заметим, что для функции Д/) = 2" увеличение скорости вычисления в 1 ООО раз приводит к тому, что размер наибольшей задачи, разрешаемой за 1 ч, возрастает точно на 10, в то время как для функции Д«) = п этот размер возрастает почти в 4 раза.

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

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

Необходимо отметить, что различия между «эффективными» (полиномиальными) алгоритмами и «неэффективными» (экспоненциальными) алгоритмами в пользу эффективных проявляется лишь для больших значений п, В противном случае это различие принимает совсем иной характер. В качестве примера, сравнивая функции /1(«) = 2" и fl(n) = п , видим, что для « < 20 функция j\{n) ведет себя лучше.

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

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