Hardprob/Maximum Weighted Satisfiability With Bound — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор булевых переменных <em>U</em>, булевое выражение…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</em>) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение < | + | * Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <em>B ∈ N</em>, |
| − | ** для каждой переменной < | + | ** для каждой переменной <em>u ∈ U</em>, задан вес <m>w(u)∈ N</m>, такой что <m>B\le\sum\limits_{u∈ U} w(u)≤2\,B</m>. |
* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет | * Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет | ||
** либо <em>B</em>, если <em>F</em> ложно | ** либо <em>B</em>, если <em>F</em> ложно | ||
| − | ** либо <m>\displaystyle\sum\limits_{ | + | ** либо <m>\displaystyle\sum\limits_{v∈ U'} w(v)</m>, если <em>F</em> истинно. |
* Максимизировать <em>R</em>. | * Максимизировать <em>R</em>. | ||
Текущая версия на 22:05, 17 апреля 2023
- Набор булевых переменных U, булевое выражение F над U, неотрицательное число-ограничение B ∈ N,
- для каждой переменной u ∈ U, задан вес , такой что .
- Найти значения переменных для U, т.е. выбор подмножества U'⊆ U переменных которых выставили в «истину», а остальные U-U' соответственно выставлены в «ложь». Значение решения R будет
- либо B, если F ложно
- либо , если F истинно.
- Максимизировать R.
Задача в лаб22 (рид-онли просмотр)