WikiDer > Бинарное ограничение
А двоичное ограничение, в математическая оптимизация, это ограничение, которое включает ровно две переменные.
Например, рассмотрим проблема n королев, где цель - разместить п шахматные королевы на п-к-п шахматная доска так, чтобы ни одна ферзь не могла атаковать друг друга (по горизонтали, вертикали или диагонали). Таким образом, формальный набор ограничений таков: «Королева 1 не может атаковать королеву 2», «Королева 1 не может атаковать королеву 3» и так далее для всех пар ферзей. Каждое ограничение в этой задаче является двоичным, поскольку учитывается только размещение двух отдельных ферзей.[1]
Линейные программы в котором все ограничения являются двоичными, можно решить в сильно полиномиальное время, результат, который, как известно, не верен для более общих линейных программ.[2]
Рекомендации
- ^ Marriott, Ким; Стаки, Питер Дж. (1998), Программирование с ограничениями: введение, MIT Press, стр. 282, г. ISBN 9780262133418.
- ^ Мегиддо, Нимрод (1983), «К подлинно полиномиальному алгоритму линейного программирования», SIAM Журнал по вычислениям, 12 (2): 347–353, CiteSeerX 10.1.1.76.5, Дои:10.1137/0212022, МИСТЕР 0697165.
 | Этот Прикладная математика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |