Участник:StasFomin/AA — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
---- | ---- | ||
| − | {{:Maximum D-Vector Covering}} | + | {{:Hardprob/Maximum D-Vector Covering}} |
---- | ---- | ||
Версия 22:03, 20 мая 2025
- Граф G=(V,E).
- Найти разбиение V на непересекающиеся множества V1 и V2.
- Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.
Код в «aa.ipynb» на гитлаб или живьем в лабе
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП. 📺видео📺
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND16»
- Набор X векторов из .
- Найти разбиение X на m подмножеств
- Максимизировать покрывающих подмножеств среди
s(a)∈ Z^+ , где «покрывающим» подмножество S векторов из
\begin{displaymath}
\sum_{i=1}^{K}\left(\sum_{a∈ A_i} s(a)\right)^2 → \min. \end{displaymath} , считается, если для всех i ≤ d сумма i-х компонент элементов из S будет не меньше 1.
Код в «aa.ipynb» на гитлаб или живьем в лабе
Всего страниц найдено: 4.
Задача «Minimum Test Collection»©
- Коллекция C подмножеств конечного множества S.
- Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) , есть некоторое подмножество , которое содержит точно один элемент из этой пары.
- Минимизировать мощность этой подколлекции |C'|.
Для понимания названия задачи, представим, что S — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней.
Код в «minimum-test-collection.ipynb» на гитлаб или живьем в лабе
- — есть тестовые данные и визуализация.
- — есть Pyomo-формулировка для ЦЛП.
-
— есть сведение на Python NP-полной задачи к данной.
- Вроде как все есть, но надо бы прорефакторить решение студента
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP6»
Задача зарезервирована: StasFomin 20:35, 21 мая 2025 (UTC)
Задача «Minimum Sum Of Squares»©
- Конечное множество A, задан размер для каждого a ∈ A, и целое K ≥ 2 .
- Найти разбиение A на множество из K непересекающихся множеств A1, A2, …, AK.
- Минимизировать сумму квадратов их размеров
Код в «minimum-sum-of-squares.ipynb» на гитлаб или живьем в лабе
- — есть тестовые данные и визуализация.
- — есть Pyomo-формулировка для ЦЛП.
- Но надо проверять и рефакторить.
Задача зарезервирована: StasFomin 20:22, 21 мая 2025 (UTC)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SP19»
Задача «Minimum Metric Traveling Salesperson Problem»©
- Набор C из m городов с заданными расстояниями между ними для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
- Найти тур C, т.е. перестановка .
- Минимизировать длину этого тура
Код в «minimum-metric-traveling-salesperson-problem.ipynb» на гитлаб или живьем в лабе
- — есть тестовые данные и визуализация.
- — есть Pyomo-формулировка для ЦЛП.
- StasFomin 17:00, 21 мая 2025 (UTC): но надо бы прорефакторить все.
Задача зарезервирована: StasFomin 17:01, 21 мая 2025 (UTC)
Задача «Minimum Local Register Allocation»©
- Набор инструкций, формирующих некий блок без переходов,
- N доступных регистров,
- стоимость чтения и записи в регистр i.
- Порядок резервирования регистров для этой последовательности инструкций.
- Минимизировать полную стоимость чтения-записи в регистры.
Код в «minimum-local-register-allocation.ipynb» на гитлаб или живьем в лабе
- — есть тестовые данные и визуализация.
- — есть Pyomo-формулировка для ЦЛП.
- Правда там две, студента и моя, надо прорефакторить и слить.