Архив рубрики ~Лента новостей~

Минимальное покрытие предметов с помощью SAT-солвера

01.10.2025 ideipro.ru

Студенты пришли в библиотеку, чтобы подготовиться к экзаменам. Всего у них предметов. Каждая из книг покрывает некоторое множество предметов. Нужно выбрать минимальное число книг, которые покроют все предметы.

Сведение к проблеме выполнимости КНФ

Для предметов используем индекс , для книг — индекс . Предикат «книга покрывает предмет » обозначаем .

Поставим задачу ответить для заданного числа на вопрос, можно ли, используя не более книг, покрыть все предметы.

Для решения задачи выберем книг в определенном порядке. Определим булевы переменные $x_{b,i}$ , обозначающие истинность высказывания «книга выбрана -й по порядку», . Всего переменных.

На переменные $x_{b,i}$ наложим ограничения:

Для каждой книги порядок может быть только один:

$x_{b,i}toneg x_{b,j}text{ для любой пары } (i,j), text{ где } ineq j$

Запишем эти условия в виде КНФ:

$bigwedge_{b=1}^Nbigwedge_{substack{i,j=1..k\i < j}} (neg x_{b,i} vee neg x_{b,j})$

2. Каждому порядку может соответствовать только одна книга:

$x_{b_1,i}toneg x_{b_2,i}text{ для любой пары } (b_1,b_2), text{ где } b_1neq b_2$

Запишем эти условия в виде КНФ:

$bigwedge_{i=1}^kbigwedge_{substack{b_1,b_2=1..N\b_1 < b_2}} (neg x_{b_1,i} vee neg x_{b_2,i})$

3. Каждый предмет покрывается хотя бы одной из выбранных книг:

для всех : $x_{b,1}vee x_{b,2} vee ldots vee x_{b,k}$ хотя бы для одной книги , такой, что

Запишем эти условия в виде КНФ:

$bigwedge_{s=1}^M bigvee_{substack{b=1\g(b,s)=1}}^N bigvee_{i=1}^k x_{b,i}$

Теперь, умея для каждого решать вопрос выполнимости КНФ, искомое минимальное покрытие находится бинарным поиском по .

Заметим, что условие 1 является необязательным.

Реализация с помощью SAT-солвера

Таким образом, имея на входе информацию о том, какие предметы какими книгами покрываются, для каждого значения формируется КНФ.

Полученную КНФ нетрудно ввести в любой SAT-солвер (например: онлайн, офлайн) в подходящем формате (например, DIMACS CNF).

Источник: habr.com

❌ Нет похожих статей с такими тегами

Оцените материал:

Читайте также

Новости робототехники Новая система искусственного интеллекта поможет машинам более детально понимать трехмерное пространство. Новости робототехники Ростех показал кобота с «умным» зрением Новости робототехники ДНК-роботы могли бы доставлять лекарства и выслеживать вирусы внутри вашего тела. Новости робототехники Человекоподобные роботы, играющие в футбол, забили важный гол в области робототехники, продемонстрировав высокую координацию движений. Архив рубрики ~Коротко из Telegram~ Здравствуйте! Предлагаю участие в совместном конкурсе в Telegram, где вы… Новости робототехники Специалист по робототехнике утверждает, что безопасность человекоподобных роботов должна быть первостепенной задачей. Новости робототехники Приводимый в движение мышечными клетками, тончайший, как бумага, робот плывет по водному лабиринту. Архив рубрики ~Коротко из Telegram~ Поселил ИИ‑агента в чёлку макбука: он слушает мой день и… Архив рубрики ~Коротко из Telegram~ Немой парень впервые признался в любви СИЛОЙ МЫСЛИ — его………… Новости робототехники GM делает ставку на вычислительные технологии и искусственный интеллект, которые, по её мнению, помогут ей конкурировать с китайскими автопроизводителями. Архив рубрики ~Коротко из Telegram~ В легендарный Need for Speed: Underground 2 теперь можно поиграть… Архив рубрики ~Коротко из Telegram~ ИИ придумал пистолет, и его напечатали на 3D-принтере Однозарядный пистолет… Архив рубрики ~Коротко из Telegram~ В Швейцарии с помощью бактерий разработали печатный материал, похожий на бетон Архив рубрики ~Коротко из Telegram~ Модели искусственного интеллекта позволили России применять технологии для лучших крылатых… Новости робототехники Новая система искусственного интеллекта поможет машинам более детально понимать трехмерное пространство. Новости робототехники Ростех показал кобота с «умным» зрением Новости робототехники ДНК-роботы могли бы доставлять лекарства и выслеживать вирусы внутри вашего тела. Новости робототехники Человекоподобные роботы, играющие в футбол, забили важный гол в области робототехники, продемонстрировав высокую координацию движений. Архив рубрики ~Коротко из Telegram~ Здравствуйте! Предлагаю участие в совместном конкурсе в Telegram, где вы… Новости робототехники Специалист по робототехнике утверждает, что безопасность человекоподобных роботов должна быть первостепенной задачей. Новости робототехники Приводимый в движение мышечными клетками, тончайший, как бумага, робот плывет по водному лабиринту. Архив рубрики ~Коротко из Telegram~ Поселил ИИ‑агента в чёлку макбука: он слушает мой день и… Архив рубрики ~Коротко из Telegram~ Немой парень впервые признался в любви СИЛОЙ МЫСЛИ — его………… Новости робототехники GM делает ставку на вычислительные технологии и искусственный интеллект, которые, по её мнению, помогут ей конкурировать с китайскими автопроизводителями. Архив рубрики ~Коротко из Telegram~ В легендарный Need for Speed: Underground 2 теперь можно поиграть… Архив рубрики ~Коротко из Telegram~ ИИ придумал пистолет, и его напечатали на 3D-принтере Однозарядный пистолет… Архив рубрики ~Коротко из Telegram~ В Швейцарии с помощью бактерий разработали печатный материал, похожий на бетон Архив рубрики ~Коротко из Telegram~ Модели искусственного интеллекта позволили России применять технологии для лучших крылатых…

🤖 Нельсон AI

✍️ Печатает...

Готов помочь

ГАЙДЫ 48