Файл: 3.4.3 - Полиномиальные алгоритмы и труднорешаемые задачи.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 189
Скачиваний: 1
Полиномиальные
алгоритмы
и
труднорешаемые
задачи
Разные
алгоритмы
имеют
различную
временную
сложность
,
и
выяснение
того
,
какие
алгоритмы
"
достаточно
эффективны
",
а
какие
"
совершенно
неэффективны
",
всегда
будет
зависеть
от
конкретной
ситуации
.
Однако
теоретики
,
занимающиеся
разработкой
и
анализом
алгоритмов
,
предлагают
для
сравнения
эффективности
алгоритмов
один
простой
подход
,
позволяющий
существенно
прояснить
ситуацию
.
Речь
идет
о
различии
между
полиномиальными
и
экспоненциальными
алгоритмами
.
Будем
говорить
,
что
функция
f(n)
есть
0(g(n))
,
если
существует
константа
с
,
такая
,
что
|f(n)|
≤
c|g(n)|
для
всех
значений
n
≤
0
.
Полиномиальным
алгоритмом
(
или
алгоритмом
полиномиальной
временной
сложности
)
называется
алгоритм
,
у
которого
временная
сложность
равна
0(
р
(
п
))
,
где
р
(
п
)
-
некоторая
полиномиальная
функция
,
а
n
—
входная
длина
.
Алгоритмы
,
временная
сложность
которых
не
поддается
подобной
оценке
,
называются
"
экспоненциальными
".
Различие
между
двумя
указанными
типами
алгоритмов
становится
особенно
заметным
при
решении
задач
большого
размера
.
Таблица
на
рис
. 2
позволяет
сравнить
скорости
роста
нескольких
типичных
полиномиальных
и
экспоненциальных
функций
. (
Обратите
внимание
на
чрезвычайно
быстрый
рост
двух
приведенных
экспонент
.)
Различие
между
полиномиальными
и
экспоненциальными
алгоритмами
проявляется
еще
более
убедительно
,
если
проанализировать
влияние
увеличения
быстродействия
ЭВМ
на
время
работы
алгоритмов
.
Рис
. 3
показывает
,
насколько
увеличатся
размеры
задач
,
решаемых
за
один
час
машинного
времени
,
если
благодаря
совершенствованию
технологии
быстродействие
ЭВМ
возрастет
в
100
или
1000
раз
по
сравнению
с
современными
машинами
.
Заметим
,
что
для
функции
f(n)
=
2
n
увеличение
скорости
вычислений
в
1000
раз
приводит
лишь
к
тому
,
что
размер
наибольшей
задачи
,
разрешимой
за
один
час
,
возрастет
только
на
10,
в
то
время
как
для
функции
f(n)
=
n
5
этот
размер
возрастет
почти
в
4
раза
.
Функция
временной
сложности
Размер
п
10 20 30 40 50
60
п
0,0000
1
сек
0,00002
сек
0,000
03
сек
0,60004
сек
0,00005
сек
0,00006
сек
n
2
0,0001
сек
0,0004
сек
0,000
9
0,0016
сек
0,0025
сек
0,0036
сек
n
3
0,001
сек
0,008
сек
0,027
сек
0,064
сек
0,125
сек
0,216
сек
n
5
0,1
сек
3,2
сек
24,3
сек
1,7,
мин
5,2
мин
13,0
мин
2
n
0,001
сек
1.0
сек
17,9
мин
12,7
дней
35,7
лет
366
столетий
3
n
0,059
сек
58
мин
6,5
лет
3855
столети
2
х
10
8
столетий
l,3 x l0
13
столетий
Рис
. 2.
Сравнение
нескольких
полиномиальных
и
экспоненциальных
функций
временной
сложности
.
Функция
временной
сложности
На
современных
ЭВМ
На
ЭВМ
в
100
раз
более
На
ЭВМ
в
1000
раз
более
п
N
1
100
N
1
1000
N
1
п
2
N
2
10
N
2
31,6
N
2
п
3
N
3
4,64
N
3
10 N
3
п
5
N
4
2,5
N
4
3,98
N
4
2
n
N
5
N
5
+ 6,64
N
5
+ 9,97
3
n
N
6
N
6
+ 4,19
N
6
+ 6,29
Рис
.
3.
Влияние
технического
совершенствования
ЭВМ
на
полиномиальные
и
экспоненциальные
алгоритмы
.
Эти
таблицы
демонстрируют
некоторые
причины
,
по
которым
олиномиальные
алгоритмы
обычно
считаются
более
предпочтительными
по
сравнению
с
экспоненциальными
.
Эта
точка
зрения
различающая
,
с
одной
стороны
,
полиномиальные
алгоритмы
,
а
с
другой
стороны
,
экспоненциальные
,
является
отправным
пунктом
в
нашем
определении
труднорешаемых
задач
и
теории
NP-
полных
задач
.
Часто
отождествляют
полиномиальные
алгоритмы
с
"
хорошими
"
алгоритмами
.
Согласно
такой
точке
зрения
,
экспоненциальные
алгоритмы
не
следует
считать
"
хорошими
",
и
чаще
всего
так
оно
и
есть
.
Большинство
экспоненциальных
алгоритмов
-
это
просто
варианты
полного
перебора
,
в
то
время
как
полиномиальные
алгоритмы
обычно
можно
построить
лишь
тогда
,
когда
удается
более
глубоко
проникнуть
в
суть
решаемой
задачи
.
Имеется
широко
распространенное
соглашение
,
согласно
которому
задача
не
считается
"
хорошо
решаемой
"
до
тех
пор
,
пока
для
нее
не
получен
полиномиальный
алгоритм
.
Поэтому
мы
будем
называть
задачу
труднорешаемой
,
если
для
ее
решения
не
существует
полиномиального
алгоритма
.
Конечно
,
это
формальное
определение
следует
рассматривать
только
как
одну
из
возможных
трактовок
понятия
"
труднорешаемая
задача
".
Различие
между
"
эффективными
" (
полиномиальными
)
алгоритмами
и
"
неэффективными
"
(
экспоненциальными
)
алгоритмами
может
принять
совсем
иной
характер
,
когда
размеры
решаемых
задач
невелики
.
Даже
на
рис
. 2
функция
f(n)
=
2
n
ведет
себя
лучше
,
чем
f(n)
=
n
5
при
п
≤
20
.
Можно
легко
построить
еще
более
яркие
примеры
Более
того
,
известны
некоторые
экспоненциальные
алгоритмы
,
весьма
хорошо
зарекомендовавшие
себя
на
практике
.
Дело
в
том
,
что
временная
сложность
определена
нами
как
мера
поведения
алгоритма
в
наихудшем
случае
,
и
тот
факт
,
что
какой
-
то
алгоритм
имеет
временную
сложность
порядка
2
n
,
означает
только
,
что
решение
по
крайней
мере
одной
индивидуальной
задачи
размера
п
требует
времени
порядка
2
n
.
На
самом
деле
может
оказаться
,
что
большинство
индивидуальных
задач
требует
для
своего
решения
значительно
меньших
затрат
времени
,
и
такого
рода
ситуация
действительно
имеет
место
для
нескольких
хорошо
известных
алгоритмов
.
К
сожалению
,
подобные
примеры
очень
редки
.
Хотя
экспоненциальные
алгоритмы
известны
для
многих
задач
,
немногие
из
них
считаются
приемлемыми
для
практических
целей
.
Даже
при
наличии
успешно
работающих
экспоненциальных
алгоритмов
,
упомянутых
выше
,
исследователи
не
отказались
от
попыток
найти
для
соответствующих
задач
полиномиальные
алгоритмы
.
В
действительности
сам
факт
успешного
применения
экспоненциальных
алгоритмов
давал
основание
предположить
,
что
они
каким
-
то
образом
выявляют
некоторые
существенные
особенности
решаемых
задач
и
что
более
глубокое
их
исследование
может
привести
к
дальнейшему
улучшению
методов
.
В
настоящее
время
пока
не
получено
удовлетворительных
объяснений
,
почему
эти
алгоритмы
работают
успешно
,
и
не
известны
методы
,
позволяющие
заранее
прогнозировать
хорошую
работу
того
или
иного
экспоненциального
алгоритма
в
практической
ситуации
.
С
другой
стороны
,
полиномиальные
алгоритмы
часто
позволяют
делать
такого
рода
прогнозы
,
поскольку
полиномиальные
функции
значительно
более
адекватно
оценивают
время
работы
алгоритмов
.
Хотя
алгоритмы
,
имеющие
временную
сложность
типа
п
100
или
10
99
n
2
,
не
могут
считаться
эффективными
с
практической
точки
зрения
,
естественно
возникающие
"
полиномиальные
"
задачи
обычно
требуют
для
своего
решения
(
в
самом
худшем
случае
)
времени
порядка
п
2
или
п
3
,
причем
коэффициенты
при
старших
членах
полиномов
не
слишком
велики
.
Алгоритмы
,
обладающие
такими
оценками
,
можно
считать
"
эффективными
",
и
именно
это
весьма
желательное
свойство
заставляет
отдавать
предпочтение
полиномиальным
алгоритмам
как
средству
решения
задач
.
Наше
определение
"
труднорешаемой
задачи
"
создает
базу
для
теории
,
обладающей
значительной
общностью
и
большими
возможностями
.
Понятие
труднорешаемой
задачи
оказывается
,
по
существу
,
независимым
от
конкретной
схемы
кодирования
и
модели
ЭВМ
,
используемых
при
определении
временной
сложности
.
Можно
показать
,
что
при
различных
способах
описания
задачи
получаемые
входы
отличаются
друг
от
друга
не
более
чем
"
полиномиальным
образом
",
т
.
е
.
любой
алгоритм
,
имеющий
полиномиальную
временную
сложность
при
одной
из
этих
схем
кодирования
,
будет
также
обладать
полиномиальной
временной
сложностью
при
всех
остальных
схемах
.
В
действительности
стандартные
схемы
кодирования
,
используемые
на
практике
для
любой
конкретной
задачи
,
по
-
видимому
,
всегда
будут
отличаться
друг
от
друга
не
более
чем
полиномиальным
образом
.
Было
бы
трудно
представить
себе
разумную
схему
кодирования
для
какой
-
либо
задачи
,
которая
отличалась
бы
более
чем
полиномиальным
образом
от
стандартных
схем
.
Хотя
мы
не
можем
формально
выразить
такое
понятие
,
как
"
разумная
схема
кодирования
",
следующие
два
условию
охватывают
важные
требования
,
связанные
с
этим
понятием
(1)
код
любой
индивидуальной
задачи
I
должен
быть
"
сжатым
",
т
.
е
.
не
содержать
избыточной
информации
или
символов
;
(2)
числа
,
входящие
в
условия
задачи
I
,
должны
быть
представлены
в
двоичной
системе
счисления
(
или
десятичной
,
или
,
восьмеричной
,
или
иметь
любое
другое
основание
,
но
только
не
1).
Если
мы
ограничимся
рассмотрением
только
тех
схем
кодирования
,
которые
удовлетворяют
этим
условиям
,
то
выяснением
вопроса
,
является
ли
данная
задача
труднорешаемой
,
не
будет
зависеть
от
выбора
конкретной
схемы
кодирования
.
Аналогичные
замечания
можно
сделать
относительно
выбора
модели
ЭВМ
.
Все
известные
в
настоящее
время
реалистические
модели
ЭВМ
(
например
,
одноленточные
и
многоленточные
машины
Тьюринга
,
машины
с
произвольным
доступом
к
памяти
)
эквивалентны
относительно
.
Можно
ожидать
,
что
и
любая
иная
"
разумная
"
модель
ЭВМ
будет
эквивалентна
по
сложности
всем
пере
-
численным
моделям
.
Под
словами
"
разумная
модель
"
здесь
главным
образом
имеется
в
виду
то
,
что
объем
работы
,
выполняемой
машиной
в
единицу
времени
,
ограничен
(
сверху
)
полиномом
.
Так
,
например
,
модель
,
обладающая
способностью
выполнять
параллельно
произвольно
много
операций
,
не
будет
считаться
"
разумной
",
и
в
действительности
ни
одна
из
существующих
(
или
проектируемых
)
ЭВМ
не
обладает
подобным
свойством
.
Во
всяком
случае
,
если
ограничиться
рассмотрением
стандартных
моделей
реальных
ЭВМ
,
то
класс
труднорешаемых
задач
не
будет
зависеть
от
выбора
конкретной
модели
,
и
такой
выбор
можно
осуществлять
,
исходя
из
интересов
дела
и
не
уменьшая
при
этом
сферы
при
-
менимости
наших
результатов
.