Hardprob/Maximum Directed Cut — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
---- | ---- | ||
{{hard-problem-on-lab17|{{PAGENAME}}}} | {{hard-problem-on-lab17|{{PAGENAME}}}} | ||
| − | * {{has-testdata-and-visualization}} | + | * {{has-testdata-and-visualization}} |
| − | * {{has-pyomo-model}} | + | * {{has-pyomo-model}} {{vim|819189350}} |
<!-- * {{has-npc-reduction}} --> | <!-- * {{has-npc-reduction}} --> | ||
<!-- * {{add-random-fuzzing-tests}} --> | <!-- * {{add-random-fuzzing-tests}} --> | ||
Текущая версия на 16:38, 19 апреля 2023
- Направленный граф G=(V,A).
- Найти разбиение V на непересекающиеся множества V1 и V2.
- Максимизировать размер разреза, т.е. число дуг, которые стартуют в V1, и заканчиваются в V2.
Задача в лаб17 (рид-онли просмотр)
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП. 📹 видео 📹
- «Ориентированная» версия Hardprob/Maximum Cut.
- Задача в базе NP-полных задач Вигго Кана