Параллельное программирование


              

Задача называется труднорешаемой, если для


Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.

Эта градация относительна, ибо сложность определяется по наихудшему варианту. Хотя реализация метода "ветвей и границ" — труднорешаемая задача (при теоретической оценке по максимальной сложности), сейчас для многих задач известны такие алгоритмы, которые практически очень быстро находят решение именно методом ветвей и границ.

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

Полиномиальные по сложности алгоритмы относят к классу P-сложных. Среди экспоненциальных выделяют алгоритмы, основанные на переборе, и их относят в класс NP-сложных. Т.е. формально возможно существование экспоненциальных алгоритмов, основанных не на переборе. Например, n!, растущий быстрее, чем 2n. К NP-сложным относятся, например, задачи линейного целочисленного программирования, составление расписания, поиск кратчайшего пути в лабиринте и т.д. Обратим внимание, что все это так называемые дискретные задачи — на основе "неделимых" объектов.

В данном контексте мы и будем понимать термин "задача высокой сложности", представляя важность применения методов распараллеливания.


Содержание  Назад  Вперед