一文彻底理解zydg化简算法 写在前面背景算法第一步第二步第三步
本文基于Abdelrahman Elzedy的文章《A C++ Karnaugh Map Minimizer (Infinite Variables)》，在一些比较难懂的地方我加了一些自己的解释，原文链接：https://www.codeproject.com/Articles/649849/A-Cplusplus-Karnaugh-Map-Minimizer-Infinte-Variabl
大家可以在网站上可以下载exe文件和源代码
写在前面
这篇文章主要介绍了一种可以化简包含任意多个变量的zydg的算法。但是原文链接所提供的代码只实现了26个变量的zydg化简（与英文字母的个数相同）。
背景本文假设读者具有基本的布尔代数和zydg知识。（译者注：大家如果忘了zydg是啥可以参考百度百科）
程序运行的时候长这样：
程序的使用步骤如下：
算法主要有三步，在代码中，每一步都由一个类（class）实现。
按照用户的输入（值为1和不关心的位置）初始化zydg，并且将值为1和不关心的位置信息保存为二进制值（译者注：将位置值保存为二进制主要是为了方便后面的化简，因为使用二进制判断位置是否相邻比较方便，大家往后看就明白了~）比较所有值为1和不关心的位置，得到所有可能的最小项检查上一步得到的结果，去掉所有多余的最小项，得到最终的结果 （译者注：如果结果不唯一时程序会输出所有可能的结果）
一脸懵逼ing？当时我读这篇文章时到这里也是不知所云，只感觉不明觉厉。不过别担心，继续往下读，我会用栗子和图的方式让大家搞懂的（译者注）
第一步在这一步中，我们首先得到了用户输入的zydg的信息（变元个数，值为1与不关心的位置）。然后我们就将这些信息转化为二进制的形式。
举个栗子：
首先我们要知道zydg是怎么编号的，一个典型的四元zydg的编号方式如下：
从图中很容易看出zydg的编号方式：横纵坐标都是按照格雷码的方式编号（不知道格雷码的编号方式请点击这里）；处于横坐标的变量（图中的A、B）的值作为高位，处于纵坐标的变量（图中的C、D）的值作为低位，构成二进制数，这个二进制数所对应的十进制数就是该位置的编号。
如果我们需要输入一个如下图所示的zydg（其中空的位置都是0，X表示不关心的值）：
那我们首先应该输入4（zydg变量的个数），然后在下一行输入0 1 3 4 11 -1（其中-1表示这一行输入结束，0 1 3 4 11是值为1的位置编号），然后再另起一行，输入5 -1（5是X的位置编号，-1代表输入结束）。这样，用户的输入就完成了。
然后程序将用户输入的位置转化为二进制（因为有四个变量，所以转化为四位二进制）。值为1的位置二进制编号分别为0000，0001，0011，0100和1011；X的位置二进制编号为0101。
可能大家已经看出来了，zydg这样编号的好处就是将位置和二进制的编号联系在了一起。比如我们很容易推断，二进制编号为0000和0001的两个位置是相邻的。这样就为我们接下来zydg化简奠定了基础。
在这一步中，我们需要两两比较上一步保存的值为1和X的位置二进制编号。比较的步骤如下（设变元总个数为n）：
如果有两个二进制数在n-1位上都相同，只有一位不同，则将不同的那一位设为 -1 ，相同位置数字不变，生成一个新的二进制数。例如上面栗子中的0000和0001，只有第四位不同，则生成新数000(-1)将上面步骤中配过对的数字标记，在下一轮的比较中只加入新生成的数和未标记的数（即没有配对的数）。重复以上步骤n次。（考虑最坏的情况：如果我们处理的是一个全部位置都是1的zydg，那我们必须重复n次）如果有一个数重复多次，则只保留一个。
接着第一步的栗子。在第一步中，我们已经得到了值为1的位置和值为X的位置的二进制编号：0000，0001，0011，0100、1011、0101。我们按照上面叙述的步骤走一遍：
Step1: 将每两个编号都进行比较，生成新数
如下图所示，红笔表示新数生成的过程，红色的√标记此数已经与其他的数配过对。
Step2 将生成的新数加进序列，并剔除做过标记的数，得到第一次处理后的数列为：
000(-1), 0(-1)00, 00(-1)1, 0(-1)01, (-1)011 and 010(-1)
Step3: 重复以上步骤，得到的第二次处理后的数列为：
0(-1)0(-1), 0(-1)0(-1), 00(-1)1 and (-1)011
第三次处理后的数列为：
0(-1)0(-1), 0(-1)0(-1), 00(-1)1 and (-1)011
第四次处理后的数列为：
0(-1)0(-1), 0(-1)0(-1), 00(-1)1 and (-1)011
去掉重复的0(-1)0(-1)得到：
0(-1)0(-1), 00(-1)1 and (-1)011
其实这个过程模拟的就是我们化简zydg时画圈的过程。
处理完n次后，我们就可以将我们得到的二进制数列转化为字母表示，转化规则如下：
例如将上面的数列 0(-1)0(-1), 00(-1)1 and (-1)011 转化为字母形式应该为：
A’C’, A’B’D and B’CD（符号 ’ 表示取非，你懂的）
有两种特殊的情况需要考虑：
在这一步中，我们将上一步得到的所有最小项进行组合，如果组合能够覆盖zydg中所有值为1的位置，则保留这个组合，得到所有可能的结果。最后输出所有最小项最少的组合。
例如在文章开始在这个图中：
我们第二步结束后得到的结果应该是 B’D’, B’C, BD, AB’, AD and CD。当我们将这些项做排列组合时，B’D’+B’C+BD+AB’ 和B’D’+B’C+BD+AD+AB’都可以覆盖zydg中所有值为1的位置。但是因为前一个组合的最小项数为4，后一个为5，所以输出B’D’+B’C+BD+AB’ 而不输出B’D’+B’C+BD+AD+AB’。
以上就是zydg化简算法的全部内容。如果大家有什么不懂的地方，或者觉得算法有可以改进的地方，欢迎在评论区讨论~