Hardprob/Minimum Sum Of Squares — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)+\s*≥\s*(\w)+\s*</m> на <em>\1 ≥ \2</em>) |
StasFomin (обсуждение | вклад) (тотальный сброс резервирования) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 11: | Строка 11: | ||
---- | ---- | ||
{{hard-problem-on-lab17|{{PAGENAME}}}} | {{hard-problem-on-lab17|{{PAGENAME}}}} | ||
| − | + | * {{has-testdata-and-visualization}} | |
| − | + | * {{has-pyomo-model}} | |
| + | ** Но надо проверять и рефакторить. | ||
<!-- * {{has-npc-reduction}} --> | <!-- * {{has-npc-reduction}} --> | ||
<!-- * {{add-random-fuzzing-tests}} --> | <!-- * {{add-random-fuzzing-tests}} --> | ||
---- | ---- | ||
<small> | <small> | ||
| + | |||
{{ViggoCode|node155}} | {{ViggoCode|node155}} | ||
Текущая версия на 12:58, 25 сентября 2025
- Конечное множество A, задан размер для каждого a ∈ A, и целое K ≥ 2 .
- Найти разбиение A на множество из K непересекающихся множеств A1, A2, …, AK.
- Минимизировать сумму квадратов их размеров
Код в «minimum-sum-of-squares.ipynb» на гитлаб или живьем в лабе
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП.
- Но надо проверять и рефакторить.
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP19»