Составители:
Рубрика:
мы, реализующий этот алгоритм в той или иной степени эффек-
тивно, причем эти рассмотрения проводились в достаточно общей
ситуации.
Конечно, желателен был бы эффективный общий метод реше-
ния подобных задач, однако опыт развития методов показывает,
что эффективность метода и его общность находятся в противо-
речии друг к другу. Поэтому для создания эффективных методов
приходится разбивать множество задач на довольно узкие классы
и находить эффективные методы для этих классов, учитывая их
специфику.
Поскольку рассматриваемые задачи являются конечномерны-
ми, то их решение возможно методом перебора: для построения
параллельной формы алгоритма, граф которого содержит n вер-
шин, требуется по крайней мере n
2
действий. Однако, в рассмат-
риваемой ситуации даже полиномиальная сложность, как правило,
велика для практической реализации, ибо n — число вершин гра-
фа алгоритма является в то же время числом операций в алгорит-
ме, а это число в большинстве случаев чрезвычайно велико. Таким
образом, построение параллельной формы оказывается значитель-
но более сложной задачей, чем реализация алгоритма; поэтому ее
построение имеет смысл делать упомянутым методом лишь в том
случае, когда алгоритм будет реализован большое число раз.
Чаще всего конкретную вычислительную задачу можно рас-
сматривать как элемент определенного семейства задач, парамет-
ризованных натуральным параметром k и приближающих интере-
сующий физический процесс при k → +∞. В этом случае число n
операций в алгоритме является функцией параметра k, n = n(k).
Хотя для конкретной задачи в первую очередь важно знать число
n(k) операций в алгоритме при фиксированном k, однако, с ростом
требований к точности вычислений и с увеличением технических
возможностей для проведения вычислений весьма существенными
оказываются асимптотические оценки функции n(k).
Если n(k) ≈ k
α
, α > 0, то говорят о задаче полиномиальной
сложности (P -сложная задача); в противном случае задача имеет
более высокую (неполиномиальную) сложность.
Таким образом, по сложности решения все дискретные задачи
делятся на задачи полиномиальной сложности (P -сложные зада-
чи) и задачи более высокой сложности, чем полиномиальные (NP-
сложные задачи).
95
Страницы
- « первая
- ‹ предыдущая
- …
- 92
- 93
- 94
- 95
- 96
- …
- следующая ›
- последняя »
