NobleBlocks

Research indexJournal article

ÐвÑомаÑиÑеÑкий поиÑк заданной бÑлевой ÑÑ ÐµÐ¼Ñ

Каплин

Electronic Library of Peter the Great Polytechnic University1 Jan 2021Open access

NobleIDark:/48914/w1/20260525/0A171C13DOI10.18720/spbpu/3/2021/vr/vr21-100

Free to read at the publisher

You can read the abstract here, or the full text at the publisher.

Read at the publisher

Abstract

В данной работе рассматривается автоматический поиск Ð·Ð°Ð´Ð°Ð½Ð½Ñ‹Ñ Ð‘ÑƒÐ»ÐµÐ²Ñ‹Ñ ÑÑ ÐµÐ¼. Дано определение Булевой ÑÑ ÐµÐ¼Ñ‹, а также показано вычисление значений Ð‘ÑƒÐ»ÐµÐ²Ñ‹Ñ Ñ„ÑƒÐ½ÐºÑ†Ð¸Ð¹ ÑÑ ÐµÐ¼Ð°Ð¼Ð¸. Дано определение задачи выполнимости, а также обоснована ее практическая значимость. Приведено описание алгоритма CDCL, используемого для решения задачи SAT, а также показан Ð¿Ð¾Ð´Ñ Ð¾Ð´, позволяющий использовать преимущества многоядерной Ð°Ñ€Ñ Ð¸Ñ‚ÐµÐºÑ‚ÑƒÑ€Ñ‹ при решении задачи SAT. Дано описание формата DIMACS CNF. Описан способ сведения задач о существовании ÐºÐ¾Ð¼Ð±Ð¸Ð½Ð°Ñ‚Ð¾Ñ€Ð½Ñ‹Ñ Ð¾Ð±ÑŠÐµÐºÑ‚Ð¾Ð² к задаче выполнимости и приведен пример такого сведения для задачи поиска решения Шидоку. Описано сведение задачи поиска заданной булевой ÑÑ ÐµÐ¼Ñ‹, вычисляющей некоторую булеву функцию, к задаче выполнимости. Разработана программа, выполняющая построение КНФ, которая выполнима тогда и только тогда, когда: существует решение для заданного экземпляра Шидоку, существует заданная Булева ÑÑ ÐµÐ¼Ð°. Приведены примеры использования программы для поиска решения Шидоку и для поиска заданной Булевой ÑÑ ÐµÐ¼Ñ‹.

Discussion

Topics

More

Suggest a correction or report