Основное различие между математикой и информатикой заключается в том, что в информатике недостаточно иметь доказательство существования объекта, требуется найти конструктивное доказательство этого факта, т.е. алгоритм. Но даже существования алгоритма может оказаться недостаточно.
Мы должны учитывать противоречия пространства и времени, которые навязывает нам мир: необходимо, чтобы решение можно было вычислить, используя объем памяти и время, приемлемое для человека или машины.
Идеальный случай, когда для решения задачи известна явная математическая формула. Тогда сложность задачи не зависит от входных данных и является постоянной.
Если же мы не располагаем ни явной формулой, ни рекуррентным выражением приемлемой сложности, нам остается только два способа:
1. построение эффективного алгоритма;
2. метод перебора всех возможностей.
Опр.1. Сложность задачи – сложность наилучшего алгоритма, известного для ее решения.
Опр.2. Вычислительная сложность алгоритма равна числу элементарных шагов, выполняемых алгоритмом в самом плохом случае, и зависит от размерности входных данных.
Объясним более точно, что подразумевается под «элементарным шагом».
Допустим, что транслятор типичной ЭВМ переводит программу в машинный язык, имеющий арифметические операции, условные переходы, операции ввода-вывода, команды переноса из памяти в буфер и т.д. Выполнение любой такой операции будем считать элементарным шагом.
Очевидно, что сложность алгоритма будет зависеть от конкретного транслятора.
Однако нас будет интересовать не абсолютная сложность, а сложность с точностью до умножения на произвольную постоянную.
Такая сложность показывает, как быстро растет число шагов при неограниченном увеличении размерности входных данных.
Такая сложность называется асимптотической и не зависит от способа трансляции.
Будем использовать следующие обозначения.
Пусть f(n) и g(n) – неотрицательные функции, n – размерность задачи,
Читается это так: «f(n) порядка не более, чем g(n)» или «f(n) порядка О большое от g(n)».
Три класса задач
"Хорошие", т.е. эффективные алгоритмы имеют сложность, представляющую собой многочлен (полином) заданной степени, где n – размерность входных данных: О(n), O(n2), O(n3)...
Например алгоритм поиска эйлеровых циклов в графе является линейным и имеет вычислительную сложность О(n).
Опр.3. Задачи, решаемые алгоритмами полиномиальной вычислительной сложности, относятся к классу Р полиномиальных алгоритмов.
Есть задачи, которые по своей природе имеют экспоненциальную сложность порядка не менее an, где a – константа или полином от n. Это задачи, в которых требуется построить все подмножества данного множества, все перестановки данного множества, все клики (полные подграфы) данного графа и т.д. Число ответов в этих задачах уже само по себе экспоненциально, поэтому только их печать (перечисление) потребует экспоненциального числа шагов.
Опр.4. Задачи, в которых только перечисление ответов требует экспоненциального числа шагов, относятся к классу Е экспоненциальных алгоритмов.
Теперь введём в классификацию ещё один класс - класс NP (недетерминированных полиномиальных алгоритмов). Какие задачи относятся к этому классу?
Во-первых, это это задачи класса Р полиномиальных алгоритмов, т.к. детерминированные полиномиальные алгоритмы есть частный случай недетерминированных полиномиальных.
Во-вторых, это задачи, не попавшие ни в класс Р, ни в класс Е.
В их условиях не содержатся экспоненциальные множества,
для них не разработан полиномиальный алгоритм,
для них не доказано, что такого алгоритма не существует.
Задачи из класса NP, решаемые за полиномиальное время, называются легкорешаемыми.
Задачи из класса NP, для решения которых неизвестны полиномиальные алгоритмы, называются труднорешаемыми.
Для большинства труднорешаемых задач (так называемых NP–полных задач) была доказана эквивалентность – если для одной из них удастся найти полиномиальный алгоритм, автоматически будут решены все остальные.
Так как NP-полные задачи являются "самыми трудными" в классе NP, в смысле так называемой полиномиальной сводимости, то решить одну из них полиномиальным алгоритмом, значит, доказать, что
Все результаты современной теории алгоритмов получены в предположении, что
Большая часть современных задач, возникающих во всех областях науки, техники и производства, являются NP-полными. Например, это:
Решение систем уравнений в целых числах.
Определение гамильтонова цикла.
Составление расписаний и раскрасок.
Существование множества значений логических переменных, которые позволяют сделать значение произвольного заданного логического выражения истинным.
Оптимизация пути коммивояжера через сеть городов.
Отбор файлов при запросе в информационный банк данных для получения информации с наименьшей стоимостью.
Размещение обслуживающих центров для максимального чис-ла клиентов при минимальном числе центров.
Оптимальная загрузка емкости, оптимальный раскрой.
Диагностика (болезни, поломки).
Планирование операций, размещение персонала, управление производством.
Оптимизация перевозок.
Проектирование в области электроники.
Но не надо печали!
При практическом изучении подобных задач нужно помнить следующее:
1. Для небольших и даже средних n составленный с умом экспоненциальный или псевдополиномиальный алгоритм часто более эффективен, чем полиномиальный.
2. Для реальных производственных задач большой размерности приближенные и эвристические полиномиальные алгоритмы дают решения не оптимальные, но удовлетворяющие заказчика.
Литература
Витольд Липский Комбинаторика для программистов. М.: Мир, 1988, 213 стр.
ЗЫ. Продолжение следует. Обсуждение приветствуется.
to folk
