== Дискретная оптимизация ==
# Берётся из {{Скачать|Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu}}, а также из {{Скачать|Алексеев - лекции по сложности комбинаторных алгоритмов.djvu}}. === Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений)=== * '''Опр.''' задача ЦЛП (ЛП + x {{in}} Z), унимодулярность матрицы (|det|=1).* К ней можно многое свести (коммивояжера, расписание, выполнимость КНФ), а вот решать округлением лучше не надо :) также к ней сводятся «нелинейности» — барьер, дихотомия, дискретные переменные.* '''Т.''' A унимод. ⇒ для целых b угловые точки целочисленны.* Метод отсечений Гомори — добавляем ограничения, не отсекающие целочисленных точек — целая часть i-ой строки с = заменённым на ≥. # === Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования) === * Идея — разбиваем задачу на две взаимодополняющих задачи (либо нецелая x<sub>i</sub> ≤ целой части, либо ≥ целой части + 1).# * Вторая идея — при ветвлениях можно не идти во всю глубину, так как меньше чем найденное не-целочисленное решение уже не будет. Если есть другое решение, дающее лучший результат — стоп.* Ещё пример — [[rupedia:Алгоритм Дейкстры|алгоритм Дейкстры]]. ЦЛП здесь не важно. === Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'')=== * '''Опр.''' f полиномиально сводится к g, P, NP, NP-полные (NPC). # === ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера)=== * Можно также почитать [[rupedia:Задача о ранце]], [[rupedia:Задача коммивояжёра]].* ЗР: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.* ЗК: отыскание самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
== Теория функциональных систем ==
