Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ И ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ

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

Будем говорить, что функция f(n) есть 0(g(n)), если существует константа С, такая, что ]Дя)| < Cg{h) для всех значений п > 0.

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

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

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

Различие между полиномиальными и экспоненциальными алгоритмами становится еще более явным, если проанализировать, как влияет увеличение быстродействия компьютера на время работы алгоритмов. В табл. 9.2 показано, насколько увеличатся размеры задач, решаемых за один час машинного времени, если благодаря совершенствованию технологий быстродействие компьютера возрастет в 100 или 1000 раз по сравнению с современными. Заметим, что для функции f(n) = 2" увеличение скорости вычисления в 1000 раз приводит к тому, что размер наибольшей задачи, решаемой за один час, возрастает только на 10, в то время как для функцииДл) = п5 почти в 4 раза.

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

По мнению многих исследователей, полиномиальные алгоритмы, как правило, являются «хорошими» с точки зрения их быстро-

Таблица 9.1

Скорость роста некоторых полиномиальных и экспоненциальных функций

Функция

временндй

сложности

Размерность задач

10

20

30

40

50

60

п

0,00001 с

0,00002 с

0,00003 с

0,00004 с

0,00005 с

0,00006 с

л2

0,001 с

0,004 с

0,0009 с

0,0016 с

0,0025 с

0,0036 с

л3

0,001 с

0,008 с

0,027 с

0,064 с

0,125 с

0,216 с

л5

0,1 с

3,2 с

24,3 с

1,7 мин

5,2 мин

13,0 мин

2"

0,001 с

1,0с

17,9 мин

12,7 дня

35,7 лет

366 столетий

3"

0,059 с

58 мин

6,5 лет

3855

2 • 108

1,3 -1013

столетий

столетий

столетий

Таблица 9.2

Увеличение размеров наибольшей задачи, решаемой за 1 час, в зависимости от быстродействия компьютеров

Функция временнбй

СЛОЖНОСТИ

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

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

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

п

100^

1000 Л/.,

п2

Л/2

10 л/2

31,6 л/2

п3

л/3

4,64 Л/3

ю л/3

п5

л/4

2,5 Л/4

3,98 Л/4

2"

л/5

Л/5 + 6,64

Л/5 + 9,97

3я

л/в

Л/6 + 4,19

Л/6 + 6,29

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

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

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

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

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

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

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

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

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

Таблица 9.3

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

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

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

Длина

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

ИИ И2] ИЗ], И4] СИП И2])

27

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

(И2П СИП ИЗ]) СИ2]) ()

24

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

0100/1010/0010/0000

19

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

Таблица 9.4

Длина схем кодирования для графа из табл. 9.3

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

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

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

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

41/+ 10е

41/+ 10е + (l/+2e) Igl/

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

21/+ 8е

21/+ 8е + 2е Igl/

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

V2 + V-/

l/2 + 1/-1

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

Формально трудно определить понятие разумности кодирования, хотя следующие два условия охватывают важные требования, связанные с этим понятием.

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

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

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

Таблица 9.5

Временная сложность алгоритов моделирования машины В

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

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

1МТ

КМТ

МПД

Машина Тьюринга с одной лентой ИМИ Машина Тьюринга с К лентами (КМТ) Машина произвольного доступа (МПД)

СКТЧп)) 01ТЧп))

ОШ) 0[т4п))

ОШ) 1дПл) 0(ПлН 1дПл)

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>