Cтраница 4
Современные методы точного или приближенного решения задач дискретного программирования не могут изучаться без знания основ теории сложности алгоритмов, в основе которой лежит описание задач из классов Р и NP. К классу NP относятся задачи, разрешаемые с экспоненциальной временной сложностью на ДМТ; вместо ДМТ в обоих случаях можно рассматривать программу, написанную на алгоритмическом языке высокого уровня. С практической точки зрения разница между полиномиальными алгоритмами ( для полиномов высокой степени) и экспоненциальными весьма условна, а смысл разницы - в возможности или невозможности избежать полного перебора при реальном решении задач. [46]
В разделе I описана постановка общей задачи дискретного программирования и ее особенности. Рассмотрены наиболее часто встречающиеся в приложениях модели. При построении этих моделей мы стремились везде, где это представляется возможным, отметить их связь между собой и дать описание в нескольких вариантах. [47]
Этот прием часто довольно эффективно применяется в дискретном программировании при построении весьма точных оценок метода ветвей и границ. [48]
Несмотря на упрощения, задача В остается задачей дискретного программирования, которая не может быть решена известными точными методами. [49]
Отметим также, что трактовке с помощью моделей дискретного программирования поддаются и многие другие экстремальные задачи на графах. [50]