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