本文主要是介绍【算法概论】贪心算法：Horn公式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Horn公式，又称霍恩公式。
Horn公式中最基本的对象是取值为true或false的布尔变量。
在Horn公式中，关于变量的知识通过两类子句表达：
① 蕴含式：其左侧为任意肯定变量的并，右侧为一个单独的肯定变量。如：(z /\ w) → u。
② 纯否定子句：包含任意多个否定文字的或。如：()。
问题描述：
给定某个由以上两类子句构成的集合，我们需要判断是否存在一个一致的解释，也即一组使得所有子句都满足的变量赋值。该解释通常也称为该Horn公式的一个可满足赋值。
❗算法描述❗：
从所有变量为 false 开始（使得刚开始纯否定子句一定满足）， 一个接一个地将其中的部分变量置为 true，置为 true 的前提简单地就是说：“只需且不得不”这样做以使得某个蕴含式满足；而一旦所有的蕴含式得到了满足，再回头检查是否所有否定子句仍然满足。
那具体如何实现呢：
首先读取所有的蕴含式，利用它们构造一个有向图。
式子的右边的字母，是箭头最终的指向，该箭头的从式子左边的字母分别出发，一同指向一个结点（式子左边字母的个数），由该数字结点指向结果。<
这篇关于【算法概论】贪心算法：Horn公式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
