Возврат - содержание >>

6. Сложность решения задачи составления рабочих графиков

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

Различают меры сложности алгоритмов двух видов:

• статическая сложность, не зависящая от входных данных задачи;
• динамическая сложность, зависящая от входных данных задачи.

Типичным примером статической меры сложности алгоритма является длинна программы, определяемая, например, количеством операторов языка программирования, использованных для кодирования конкретной реализации алгоритма. 

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

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

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

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

Для многих алгоритмов неизвестно точных верхних и/или нижних оценок. Поэтому оказывается удобным при анализе алгоритмов подсчитывать только количество "элементарных" операций, а о сложности алгоритмов судить по асимптотическому росту числа элементарных операций.

В теории сложности выделяют два фундаментальных класса алгоритмов:

• алгоритмы, сложность которых оценивается полиномом от размерности задачи;
• алгоритмы с экспоненциальной оценкой сложности.

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

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

Формальным изучением отмеченного феномена, занимается теория NP-полных задач. Класс NP-полных задач обладает следующими свойствами:

1. Никакую NP-полную задачу нельзя решить никаким известным алгоритмом полиномиальной сложности;
2. Если будет найден полиномиальный алгоритм для какой-нибудь NP-полной задачи, то существуют полиномиальные алгоритмы для всех NP-полных задач.

Основываясь на этих двух фактах, многие исследователи высказывают гипотезу, что ни для какой NP-полной задачи не может существовать полиномиального алгоритма. Однако некому пока не удалось доказать это.

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

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

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

Возврат - содержание >>

На главную страницу сайта >>