ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 135
Скачиваний: 1
Сложность
и
труднорешаемые
задачи
Многим
приходилось
сталкиваться
с
задачами
,
при
решении
которых
после
многочисленных
и
безуспешных
попыток
оказывалось
,
что
ничего
кроме
прямого
перебора
предложить
невозможно
.
Если
бы
с
самого
начала
удалось
доказать
,
что
задача
труднорешаема
,
то
можно
было
бы
избежать
бессмысленной
траты
времени
.
К
сожалению
,
доказать
,
что
задача
труднорешаема
,
может
быть
,
не
менее
трудно
,
чем
найти
эффективные
алгоритмы
.
Даже
выдающиеся
теоретики
оказывались
беспомощными
в
попытках
получить
подобное
доказательство
для
часто
встречающихся
трудных
задач
.
Теория
NP-
полных
задач
предлагает
много
простых
методов
доказательства
того
,
что
та
или
иная
конкретная
задача
столь
же
трудна
,
как
и
большое
число
других
задач
,
признанных
очень
трудными
и
уже
много
лет
не
поддающихся
усилиям
специалистов
.
На
самом
деле
выявление
NP-
полноты
—
это
обычно
лишь
начало
работы
над
задачей
.
Однако
знание
этого
факта
действительно
дает
ценную
информацию
о
том
,
какие
подходы
к
ее
решению
окажутся
наиболее
перспективными
.
Очевидно
,
что
в
этом
случае
не
следует
делать
ставку
на
поиски
эффективного
точного
алгоритма
.
Лучше
сосредоточить
свое
внимание
на
иных
,
более
скромных
подходах
.
Например
,
вы
могли
бы
начать
разработку
эффективных
алгоритмов
,
позволяющих
решать
различные
частные
случаи
поставленной
общей
задачи
.
Можно
было
бы
заняться
отысканием
алгоритмов
,
хотя
и
не
гарантирующих
быстрого
решения
,
однако
работающих
быстро
в
большинстве
случаев
.
Наконец
,
можно
даже
ослабить
некоторым
образом
постановку
задачи
и
искать
быстрый
алгоритм
,
у
которого
заданным
требованиям
удовлетворяет
большая
часть
характеристик
.
Короче
говоря
,
основное
предназначение
теории
NP-
полных
задач
состоит
в
том
,
чтобы
помочь
разработчикам
алгоритмов
и
направить
их
усилия
на
выбор
таких
подходов
к
решению
задач
,
которые
,
вероятнее
всего
,
приведут
к
практически
полезным
алгоритмам
.
Для
того
чтобы
в
дальнейшем
изучать
такие
понятия
,
как
"
труднорешаемые
задачи
"
и
"
эквивалентные
по
сложности
задачи
",
необходимо
сначала
договориться
о
значении
нескольких
основных
терминов
.
Начнем
с
понятия
задачи
.
Под
массовой
задачей
(
или
просто
задачей
)
П
мы
будем
понимать
некоторый
общий
вопрос
,
на
который
следует
дать
ответ
.
Обычно
задача
содержит
несколько
параметров
,
или
свободных
переменных
,
конкретные
значения
которых
не
определены
.
Задача
П
определяется
следующей
информацией
:
(1)
общим
списком
всех
ее
параметров
,
(2)
формулировкой
тех
свойств
,
которым
должен
удовлетворять
ответ
или
,
другими
словами
,
решение
задачи
.
Индивидуальная
задача
I
получается
из
массовой
задачи
П
,
если
всем
параметрам
задачи
П
присвоить
конкретные
значения
.
В
качестве
примера
рассмотрим
классическую
задачу
о
коммивояжере
.
Параметры
этой
массовой
задачи
состоят
из
конечного
набора
"
городов
"
С
=
{c
1
,
c
2
, ..., c
m
}
и
расстояний
d(c
i
,
с
j
)
между
каждой
парой
городов
c
i
,
с
j
,
из
С
.
Решение
-
это
такой
упорядоченный
набор
заданных
городов
>
<
c
c
c
m
)
(
)
2
(
)
1
(
,
,
,
π
π
π
K
,
который
минимизирует
величину
∑
−
=
+
+
1
1
)
1
(
)
(
)
1
(
)
(
)
,
(
)
,
(
m
i
m
i
i
c
c
d
c
c
d
π
π
π
π
Это
выражение
дает
длину
маршрута
,
начинающегося
в
городе
c
)
1
(
π
,
проходящего
последовательно
через
все
города
и
возвращающегося
в
c
)
1
(
π
непосредственно
из
последнего
города
c
m
)
(
π
Индивидуальная
задача
о
коммивояжере
,
показанная
на
рис
. 1,
задается
следующим
образом
:
Последовательность
<c
1
, c
2
, c
4
, c
3
>
представляет
собой
решение
задачи
,
поскольку
соответствующий
маршрут
имеет
минимальную
возможную
длину
,
равную
27.
Под
алгоритмом
будем
понимать
общую
,
выполняемую
шаг
за
шагом
процедуру
решения
задачи
.
Для
определенности
мы
можем
считать
ее
програм
-
мой
для
ЭВМ
,
написанной
на
формальном
машинном
языке
.
Будем
говорить
,
чго
алгоритм
решает
массовую
задачу
П
,
если
он
применим
к
любой
индивидуаль
-
ной
задаче
I
из
П
и
обязательно
дает
решение
задачи
I
.
Подчеркнем
,
что
термин
"
решение
"
понимается
здесь
строго
в
соответствии
с
данным
выше
определением
.
Поэтому
,
в
частности
,
нельзя
сказать
,
что
алгоритм
"
решает
"
задачу
о
коммивояжере
,
если
он
не
выдаст
маршрут
минимальной
длины
хотя
бы
для
какой
-
то
одной
индивидуальной
задачи
.
Рис
. 1.
Индивидуальная
задача
о
коммивояжере
и
маршрут
минимальной
возможной
длины
,
равной
27.
Вообще
говоря
,
нам
нужен
наиболее
"
эффективный
"
алгоритм
для
решения
задачи
.
В
самом
широком
смысле
понятие
эффективности
связано
со
всеми
вычислительными
ресурсами
,
необходимыми
для
работы
алгоритма
.
Однако
обычно
под
"
самым
эффективным
"
алгоритмом
понимается
самый
быстрый
.
Поскольку
ограничения
по
времени
часто
являются
доминирующим
фактором
,
определяющим
пригодность
конкретного
алгоритма
для
практики
,
основное
внимание
мы
сосредоточим
главным
образом
на
этом
виде
ресурсов
.
Время
работы
алгоритма
удобно
выражать
в
виде
функции
от
одной
переменной
,
характеризующей
«
размер
»
индивидуальной
задачи
,
т
.
е
.
объем
входных
данных
,
требуемых
для
описания
этой
задачи
.
Такой
подход
удобен
,
поскольку
в
дальнейшем
сравнительная
сложность
задач
будет
оцениваться
через
их
размеры
.
Часто
размер
задачи
измеряется
неформально
.
В
задаче
о
коммивояжере
,
например
,
для
этой
цели
обычно
используется
число
городов
.
Однако
в
задаче
с
т
городами
кроме
номеров
этих
городов
на
объем
входной
информации
влияют
также
т
(
т
—
1)/2
величин
,
определяющих
расстояния
между
городами
,
и
значения
этих
величин
.
Если
нам
предстоит
иметь
дело
с
временными
характеристиками
в
точной
математической
постановке
,
то
мы
должны
так
определить
размер
задачи
,
чтобы
все
эти
факторы
были
учтены
.
Для
этого
обратим
внимание
на
то
,
что
описание
индивидуальной
задачи
,
которое
мы
даем
в
терминах
входа
для
ЭВМ
,
можно
рассматривать
как
одну
конечную
цепочку
(
или
слово
)
символов
,
выбранных
из
конечного
входного
алфавита
.
Невзирая
на
то
что
существуют
различные
пути
описания
данной
ин
-
дивидуальной
задачи
,
предположим
,
что
заранее
выбран
некоторый
определенный
способ
и
что
с
каждой
массовой
задачей
связана
некоторая
фиксированная
схема
кодирования
,
которая
отображает
индивидуальные
задачи
в
соответствующие
цепочки
символов
.
Входная
длина
индивидуальной
задачи
I
из
П
определяется
как
число
символов
в
цепочке
,
полученной
применением
к
задаче
I
схемы
кодирования
для
массовой
задачи
П
.
Именно
это
число
,
т
.
е
.
входная
длина
,
и
используется
в
качестве
формальной
характеристики
размера
индивидуальной
задачи
.
Например
,
различные
конкретные
задачи
о
коммивояжере
можно
описать
с
помощью
алфавита
{
с
, [, ], /, 0, 1, 2, 3, 4, 5, 6
,
7, 8, 9},
при
этом
предыдущий
пример
будет
закодирован
в
виде
такой
цепочки
символов
:
с
[1]
с
[2]
с
[3]
с
[4]//10/5/9//6/9//3
Более
сложные
индивидуальные
задачи
кодируются
аналогичным
образом
.
При
такой
кодирующей
схеме
для
задачи
о
коммивояжере
входная
длина
в
нашем
примере
будет
равна
32.
Временная
сложность
алгоритма
отражет
требующиеся
для
его
работы
затраты
времени
.
Это
функция
,
которая
каждой
входной
длине
п
ставит
в
соответствие
максимальное
(
по
всем
индивидуальным
задачам
длины
n
)
время
,
затрачиваемое
алгоритмом
на
решение
индивидуальных
задач
этой
длины
.
Естественно
,
что
эта
функция
не
будет
полностью
определена
до
тех
пор
,
пока
не
зафиксирована
схема
кодирования
,
определяющая
входную
длину
индивидуальной
задачи
,
и
не
выбрано
вычислительное
устройство
(
или
его
модель
),
определяющее
время
работы
.
Однако
,
как
будет
видно
из
дальнейшего
,
подобные
детали
окажут
незначительное
влияние
на
различия
между
классами
,
возникающими
в
теории
NP-
полных
задач
.
Поэтому
в
дальнейшем
читателю
рекомендуется
зафиксировать
мысленно
какую
-
либо
конкретную
схему
кодирования
для
каждой
задачи
,
выбрать
некоторое
конкретное
вычислительное
устройство
или
его
модель
и
рассматривать
затем
временную
сложность
алгоритмов
в
соответствии
с
получающимися
входными
длинами
и
соответствующими
затратами
времени
.
