Интересная проблема алгоритма

Question

У меня есть интересная проблема с алгоритмом здесь.Эта проблема в некотором роде связана с моделированием электронных конструкций.

Скажем, например, у меня есть структура, содержащая некоторые ворота.скажем, 3 входа и ворота.Есть 8 возможных входов, т.е.

000
001
...
111

Из этих 8 входов, если я только подаю на два входа (000) и (111), я получу оба возможных выхода, т.е. 0 и 1.

Итак, минимальный набор входных векторов, который выдает на выходе состояния «0» и «1», равен {000, 111}.

Проблема заключается в том, что некоторыерасположение вентилей, дать алгоритм, чтобы найти минимальный набор входных векторов, который создает оба состояния (то есть 0 и 1) на конечном выходе.

Answer 1

Ваша задача эквивалентна решению проблемы логического выполнимости . Поэтому он NP-завершен.

Чтобы получить один из входов, вы можете выбрать произвольный вход и посмотреть, дает ли он 0 или 1. Чтобы найти вход, который дает другой выход, вам нужен SAT-решатель.

Википедия предлагает несколько алгоритмов , которые можно использовать:

• алгоритм DPLL
• Алгоритм Чеффа
• ГРАСП
• WalkSAT
• и т.д ...

Если вы не хотите его реализовывать, есть инструменты, готовые к использованию SAT-решателей:

• CVC3 (LGPL с открытым исходным кодом)
• Yices (бесплатно для некоммерческого использования)

Answer 2

Это решается с помощью алгоритма Куайна МакКласки. Есть также некоторые JavaScripts и инструменты, которые могут решить вашу проблему.