Глава I Основные понятия

§1. Введение

Учебное пособие посвящено методам решения оптимизацион­ных задач дискретной математики. Бурное развитие этой области математики в последние десятилетия во многом связано с широ­ким внедрением ЭВМ в различные сферы жизни и деятельности человека.

Приведем несколько примеров дискретных оптимизационных задач.

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

Еще один пример: есть n станков и n деталей, каждую деталь можно обрабатывать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Пусть эти времена для каждой пары станок — деталь заданы. Требуется так организовать производство деталей, т.е. разместить их по станкам, чтобы суммарное время работы было наименьшим (задача оптимального назначения).

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

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

Все приведенные выше задачи имеют ряд общих свойств, характеризующих дискретные оптимизационные задачи.

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

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

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

§2. Алгоритмы и их сложности

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

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

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

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

Для оценки качества алгоритмов имеется много критериев. Одним из важнейших таких критериев является понятие вычислительной сложности (или просто сложности) алгоритма.

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

Под шагом алгоритма будем понимать выполнение "простой" операции, обычно аппаратно реализованной на любой ЭВМ, а именно любой арифметической операции, операции сравнения, пересылки, косвенной адресации и т.п. Ясно, что при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд. Однако нас никогда не будет интересовать точная сложность алгоритма, а только асимптотическая сложность, т.е. порядок роста числа шагов алгоритма, когда размерность задачи неограниченно растет.

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем использовать следующие понятия.

Будем говорить, что функция f(n) имеет порядок роста не более чем g(n) (запись: f(n) = О(g(n))), если существуют константы с. N > 0 такие, что f(n) < cg(n) для всех n > N.

Говорят, что функция f(n) имеет порядок роста не менее чем g(n) (запись: f(n) = Ω (g(n)) ), если существуют константы с, N > 0 такие, что f(n) ≥ c g(n) для всех n > N.

Например, справедливы следующие соотношения:

log₂n = О(n); n² = 0(2ⁿ); n = Ω (log₂n):

На практике алгоритм решения некоторой задачи считается достаточно хорошим, если сложность этого алгоритма есть O(n^p) при некотором р > 0. В этом случае говорят, что задача полиномиалъно разрешима, или, что то же самое, задача может быть решена за полиномиальное время.

Отметим, что как задача о кратчайшем пути, так и задача оптимального назначения относятся к классу полиномиально разрешимых. В то же время для задачи коммивояжера неизвестен алгоритм решения, имеющий полиномиальную сложность, впрочем, нет и доказательства того, что такой алгоритм не существует. Однако, для задачи коммивояжера, как и для целого ряда других естественно формулируемых задач, известно, что если будем найден алгоритм ее решения, имеющий полиномиальную сложность, то тем самым будут найдены полиномиальные алгоритмы и для очень обширного круга задач дискретной оптимизации. Такие задачи называют NP-полными. Проблема, заключающаяся в том, имеет ли хотя бы одна NP-полная задача (например, задача коммивояжера) алгоритм ее решения полиномиальной сложности, является одной из самых интересных и актуальных проблем современной математики. Рассмотрение вопросов, относящихся к теории NP-полных задач, не входит в рамки данного пособия. Читателя, заинтересовавшегося данной проблематикой, мы адресуем к книге М.Гэри и Д.Джонсона [2].

Важность понятия сложности алгоритма хорошо иллюстрируют следующие таблицы, заимствованные из книги А.Ахо, Дж.Хопкрофта, Дж.Ульмана [1].

Первая таблица построена в предположении, что один шаг работы алгоритма требует для своего выполнения 1 миллисекунду. Как следует из таблицы, при увеличении времени с 1 секунды до I часа, т.е. в 3,6*10³ раз, размер задачи, решаемой алгоритмом сложности 2ⁿ, увеличивается только в 21/9 раза, а для алгоритма сложности п ровно в 3,6*10³ раз.

Может показаться, что рост скорости вычислений, вызванный появлением новых ЭВМ, уменьшит значение эффективных (т.е. имеющих "небольшую" сложность) алгоритмов. Однако, как это видно из таблицы 1.1, в действительности происходит в точности противоположное. Так как ЭВМ работают все быстрее и возможно решение задач все большей размерности, именно сложность алгоритма определяет то увеличение размера задачи, которое можно достичь с увеличением скорости ЭВМ.

Сложность алгоритма	Максимальный размер задачи
	за 1 сек.	за 1 мин	за 1 час
n	1000	6*10^4	3,6*10^6
n*log2n	140	4893	210^5
n^2	31	244	1897
n^3	10	39	153
2^n	9	15	21

Таблица 1.1. Максимальная размерность задач, разрешимых за данное время

Сложность алгоритма	Размер наибольшей задачи, разрешимой за единицу времени
	На современных ЭВМ	На ЭВМ, в 10 раз более быстрых	На ЭВМ, в 1000 раз более быстрых
n	К	10К	1000К
n*logn	L	Почти 10L для больших L	Почти 1000L для больших L
n^2	М	3.I6M	31,6М
n^3	N	2,15N	10N
2^n	Р	Р+3,3	Р+9,97

Таблица 1.2. Влияние технического совершенствования ЭВМ на полиномиальные и экспоненциальные алгоритмы

Пусть для решения некоторой задачи имеется алгоритм сложности n³. Тогда, как это следует из таблицы 1.2, десятикратное увеличение скорости быстродействия ЭВМ позволит увеличить размер задачи, решаемой за 1 минуту в 2,15 раз. Однако замена этого алгоритма другим, имеющим сложность n², позволит решать задачу в 6 раз большего размера (см. таблицу 1.1). Если в качестве единицы взять 1 час, то сравнение будет еще более впечатляющим.

Отметим, что для алгоритма сложности 2ⁿ десятикратное увеличение скорости ЭВМ увеличивает размер задачи, которую можно решить только на три единицы, тогда как для алгоритма сложности n² размер задачи более чем утраивается, а для алгоритма сложности n происходит десятикратное увеличение допустимого размера разрешимости задачи.