Алгоритм называется полиномиальным, если время его работы T(n) ограничено сверху некоторым полиномом:
Алгоритм называется экспоненциальным, если время его работы T(n) ограничено снизу некоторым полиномом:
В задачах целочисленного программирования переменные задачи могут принимать только целые значения:
В задаче коммивояжера ищется максимум целевой функции:
В задаче о камнях веса камней входят в целевую функцию:
В задаче о рюкзаке его грузоподъемность V входит в целевую функцию:
В основе комбинаторных методов лежит идея разбиения области допустимых решений:
В худшем случае метод ветвей и границ сводится к полному перебору всех возможных вариантов решения задачи:
Задача коммивояжера принадлежит классу NP задач:
Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные:
Задача с ослабленными ограничениями - задача, которая возникает в результате исключения требования целочисленности некоторых переменных:
Задача с ослабленными ограничениями - задача, которая возникает в результате исключения требования целочисленности переменных:
Класс Р состоит из задач, для которых существуют полиномиальные алгоритмы решения:
Комбинаторные методы используются, если число переменных велико:
Любая задача с конечным множеством допустимых решений может быть решена методом перебора:
Метод ветвей и границ применяется в задачах, где число допустимых решений конечно:
Рекуррентное соотношение Беллмана используется в методе ветвей и границ: