Содержание
11 отношения: Квадратичная задача о назначениях, Класс NP, Класс P, Комбинаторная оптимизация, Обобщённая задача о назначениях, Целочисленное программирование, Метод ветвей и границ, Задача о соседях по комнате, Задача о марьяже, Задача о назначениях, Линейная задача о назначениях в узких местах.
- Комбинаторная оптимизация
- Паросочетания
Квадратичная задача о назначениях
Квадрати́чная зада́ча о назначе́ниях (КЗН, Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Посмотреть Задача о назначении целей и Квадратичная задача о назначениях
Класс NP
В теории алгоритмов классом NP (от non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).
Посмотреть Задача о назначении целей и Класс NP
Класс P
В теории алгоритмов классом P (от polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).
Посмотреть Задача о назначении целей и Класс P
Комбинаторная оптимизация
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.
Посмотреть Задача о назначении целей и Комбинаторная оптимизация
Обобщённая задача о назначениях
В прикладной математике под обобщённой задачей о назначениях понимается задача комбинаторной оптимизации, являющаяся обобщением задачи о назначениях, в которой множество исполнителей имеет размер, не обязательно равный размеру множества работ.
Посмотреть Задача о назначении целей и Обобщённая задача о назначениях
Целочисленное программирование
Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами.
Посмотреть Задача о назначении целей и Целочисленное программирование
Метод ветвей и границ
Метод ветвей и границ (branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации.
Посмотреть Задача о назначении целей и Метод ветвей и границ
Задача о соседях по комнате
Задача о соседях по комнате — математическая задача кооперативных игр (теории игр и комбинаторики) нахождения устойчивого (стабильного) соответствия, при котором никакая другая пара не предпочитала бы друг друга более чем в текущем распределении.
Посмотреть Задача о назначении целей и Задача о соседях по комнате
Задача о марьяже
Задача о свадьбе — математическая задача из области кооперативных игр.
Посмотреть Задача о назначении целей и Задача о марьяже
Задача о назначениях
Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций.
Посмотреть Задача о назначении целей и Задача о назначениях
Линейная задача о назначениях в узких местах
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях, Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009, глава 6.2 "" (стр.
Посмотреть Задача о назначении целей и Линейная задача о назначениях в узких местах
См. также
Комбинаторная оптимизация
- A*
- Алгоритм Дейкстры
- Венгерский алгоритм
- Весовая функция
- Задача коммивояжёра
- Задача о 1-центре
- Задача о назначении целей
- Задача о назначениях
- Задача о наименьшей окружности
- Задача о рюкзаке
- Задача раскроя
- Квадратичная задача о назначениях
- Комбинаторная оптимизация
- Линейная задача о назначениях в узких местах
- Максимальный разрез графа
- Метод ветвей и границ
- Метод эллипсоидов
- Наименьший k-разрез
- Обобщённая задача о назначениях
- Паросочетание
- Теорема Форда — Фалкерсона
- Целочисленное программирование
Паросочетания
- Алгоритм Хопкрофта — Карпа
- Алгоритм сжатия цветков
- Венгерский алгоритм
- Граф без клешней
- Задача о назначении целей
- Задача о назначениях
- Задача о разборчивой невесте
- Индекс Хосойи
- Многочлен паросочетаний
- Мозаика домино
- Паросочетание
- Теорема Кёнига (комбинаторика)
- Теорема о свадьбах
- Транспортная задача
- Фактор-критический граф