Hardprob/Minimum Exact Cover
Материал из DISCOPAL
Версия от 12:55, 25 апреля 2023; Анна Савчук (обсуждение | вклад)
- Коллекция C подмножеств конечного множества S.
- Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
- Минимизировать суммарных объем покрывающих подмножеств, т.е.
Задача в лаб22 (рид-онли просмотр)
- — есть тестовые данные и визуализация.
- — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹
- — есть сведение на Python NP-полной задачи к данной. Аналогично Hardprob/Minimum Set Cover, см. 📹 видео 📹, хотя возможно надо доработать (метрика в элементах покрытия, не в множествах).
- Можно доработать — сделать Вероятностное тестирование NPC-сведения!
Задача зарезервирована: Анна Савчук 12:55, 25 апреля 2023 (UTC)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.