Hardprob/Maximum Set Splitting — различия между версиями

Текущая версия на 12:23, 22 сентября 2023

• Коллекция C подмножеств конечного множества S.
• Найти разбиение S, на непересекающиеся множества S₁ и S₂.
• Максимизировать число подмножеств C, которые «разделены» между S₁ и S₂, т.е. не лежат полностью в S₁ или S₂.

Задача в лаб22 (рид-онли просмотр)

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП. 📺 видео 📺
• — есть сведение на Python NP-полной задачи к данной. 📺 видео 📺
• Можно доработать — сделать Вероятностное тестирование NPC-сведения!