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

Минимальное покрытие предметов с помощью 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

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

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

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

Архив рубрики ~Обо всем~ Физик производит расчеты «маневра Пикарда» из «Звездного пути». Новости робототехники Ультразвук предлагает масштабируемый путь к тактильному интеллекту для физического ИИ Архив рубрики ~Полезное~ Как скачать треки из SUNO без лимитов Архив рубрики ~Полезное~ Spotify показала плагины, которые режут расход токенов Claude Code на… Архив рубрики ~Коротко из Telegram~ Россия выделяется плотной связкой университетов и компаний в ИИ-исследованиях Наукометрический… Архив рубрики ~Коротко из Telegram~ Россияне начали прокачивать резюме мемами — и ИИ-рекрутеры ведутся Кандидаты… Архив рубрики ~Коротко из Telegram~ Suno выпустила V6 — теперь с лицензированной музыкой и точечным… Архив рубрики ~Полезное~ Личный финансовый советник в кармане: 7 промптов для ChatGPT Если… Архив рубрики ~Коротко из Telegram~ DeepSeek выпустила V4.1-Flash — и «Flash» здесь не значит «слабая»… Архив рубрики ~Коротко из Telegram~ Один вопрос вместо трёх переделок Стандартный сценарий: пишете задачу… Архив рубрики ~Коротко из Telegram~ Gemini прямо с рабочего стола: Alt + Space и… Архив рубрики ~Обо всем~ Единая наука. Часть 2: Объекты, паттерны и абстракции Архив рубрики ~Обо всем~ Что нового на Peacock в сентябре 2026 года? Новые сезоны сериалов «Предатели», «Газета», премия «Эмми» и многое другое. Новости робототехники Компания Mecka AI приблизилась к оценке в 500 миллионов долларов в рамках сделки, инициированной Sequoia, на фоне ажиотажа вокруг данных для обучения роботов. Архив рубрики ~Обо всем~ Физик производит расчеты «маневра Пикарда» из «Звездного пути». Новости робототехники Ультразвук предлагает масштабируемый путь к тактильному интеллекту для физического ИИ Архив рубрики ~Полезное~ Как скачать треки из SUNO без лимитов Архив рубрики ~Полезное~ Spotify показала плагины, которые режут расход токенов Claude Code на… Архив рубрики ~Коротко из Telegram~ Россия выделяется плотной связкой университетов и компаний в ИИ-исследованиях Наукометрический… Архив рубрики ~Коротко из Telegram~ Россияне начали прокачивать резюме мемами — и ИИ-рекрутеры ведутся Кандидаты… Архив рубрики ~Коротко из Telegram~ Suno выпустила V6 — теперь с лицензированной музыкой и точечным… Архив рубрики ~Полезное~ Личный финансовый советник в кармане: 7 промптов для ChatGPT Если… Архив рубрики ~Коротко из Telegram~ DeepSeek выпустила V4.1-Flash — и «Flash» здесь не значит «слабая»… Архив рубрики ~Коротко из Telegram~ Один вопрос вместо трёх переделок Стандартный сценарий: пишете задачу… Архив рубрики ~Коротко из Telegram~ Gemini прямо с рабочего стола: Alt + Space и… Архив рубрики ~Обо всем~ Единая наука. Часть 2: Объекты, паттерны и абстракции Архив рубрики ~Обо всем~ Что нового на Peacock в сентябре 2026 года? Новые сезоны сериалов «Предатели», «Газета», премия «Эмми» и многое другое. Новости робототехники Компания Mecka AI приблизилась к оценке в 500 миллионов долларов в рамках сделки, инициированной Sequoia, на фоне ажиотажа вокруг данных для обучения роботов.

🤖 Нельсон AI

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

Готов помочь

ГАЙДЫ 48