минимизация эвристики булевой функции для алгоритма A *

Question

Мне нужно написать программу на python, которая минимизирует булеву функцию, но суть в том, что мне нужно использовать алгоритмы поиска, например A * или более простой алгоритм BFS или что-то в этом роде.Я написал программу с использованием итеративного углубления, она решает все проблемы, но она слишком медленная (ограничение составляет 20 с для каждой проблемы).

Итак, я написал другую программу с использованием алгоритма A * (нам сказали, что если мы хотим получить более высокую оценку, мы должны использовать этот), но мне удалось сделать его в 10 раз медленнее, чем тот, который использует итеративное углублениеи это потому, что я не могу понять правильную эвристику для алгоритма.Я не могу понять, каковы критерии эффективного минимизации (хорошая эвристика).

ПРОБЛЕМА:

Вам дан список списков ([[0,1,0,1],[...], [...], [....], ...]), представляющие таблицу истинности (последний элемент во внутреннем списке представляет значение функции).Напишите программу, которая находит минимальную дизъюнктивную форму булевой функции, используя только алгоритмы поиска (пример A *, BFS, IDA *, DFS, ..).Для решения каждой проблемы у вас есть 20 секунд.

Answer 1

Я собираюсь предположить, что ваши состояния являются действительными наборами конъюнктов. Вот простая допустимая эвристика. Пусть U будет набором входов функций, сопоставляемых с 1, которые не соответствуют ни одному из конъюнктов в текущем состоянии. Пока U не пусто, выберите вход x в U. Удалите из U все входы y так, чтобы существовал действительный конъюнкт, совпадающий с x и y. Вернуть количество элементов, выбранных из U.

На самом деле, эту проблему можно рассматривать как пример установленного покрытия , и эта эвристика жадно строит решение двойственной релаксации LP. Если у вас есть доступ к решателю LP, вы можете получить более качественную (но, возможно, более медленную) эвристику, решив двойную LP до оптимальности.