一、算法的主要流程
有了子集的矩阵表达形式之后,我们就可以用Knuth发明的X算法来求出精确覆盖问题的解。(如果你在研究算法,但是没听过knuth的名字并且你又不是计算机的天才的话,请在阅读完本文后立刻去拜读Knuth的大作,呵呵)。
这个递归算法(设算法函数的名字为search)的主要流程是
1、设置一个子集编号集合S,用来存储本次得到的部分解。开始时S为空。
2、判断当前矩阵M是否为空,为空的话表示已经没有待处理子集和元素,此时求解成功,返回true.
3、判断当前矩阵M中是否有全1的行,有的话则则该行是一个当前的可行解,将其加入到S中,函数返回true。
4、判断当前矩阵M中是否有全0的列,有的话则代表该列的所对应的元素一定不在剩下的所有子集里,此时当前问题无解,函数返回false。
5、从M中找出含1个数最少的列,设选出这个的列号为c。如果有多个列的含1个数都相同,则取最左边的那一列。
6、找出所有满足M(r,c)=1的行. 即所有含元素c的子集。 用一个循环来处理这些行,当处理完某一行之后如果得到了一个可行解,则算法结束。具体的处理过程是
a、设当前待处理的行为r
b、找出本行所有为1的列,然后用一个循环处理这些列,循环体的处理过程是
b.1 设j为当前待处理的列号
b.2 遍历矩阵M,将所有满足M(i,j)=1的行i从M中删除, 这一步的目的将所有和子集r有共同元素的子集从矩阵中删掉。
b.3 将列j从矩阵M中删除, 这意味着本列所对应的元素已经被处理过了,已经属于A的并集了。以后再加入的子集中不需要再含有这些元素了。
总体来说,步骤b的目的就是在矩阵中删除所有和r相交的行和列,得到一个新的子矩阵M'。
c. 对新的矩阵M',继续调用函数search(这是一个递归过程),设递归调用的结果为flag。
d.如果上一步得到的flag为真,意味着得到了一个可行解,此时在上一步得到的局部可行解s'中加入行号r,就是本次函数调用的可行解。本次函数调用结束,函数返回true。
7、当步骤6中的循环结束后仍未找到一个可行解,则函数结束,返回false.
二、一个运行实例
对我们所举的例子,矩阵M的初始状态为
1 2 3 4 5 6 7
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
1、找出含1个数最少的列,即找出在子集中出现次数最少的那个元素。显然,元素1、2、3、5、6的总出现次数都为2,而我们是从左到右遍历的,故这一步的选择列号为1.
2、找出所有含有元素1的子集,即A和B,也就是第一行和第二行。现在S={}
3、我们先考虑子集A、先尝试将子集A加入到解集S中。现在S={A},
4、现在将所有和A有交集的子集从矩阵中删除。具体做法是,子集A对应3个列1,4,7。那么从矩阵中把所有在这3列中含1的行删掉。
比如对第1列,含1的行有A,B;对第4列,含1的行有A,B,C;对第7列,含1的行有A,C,E,F。 因此删除的就是A 、B、 C、 E 、F等5行
5、删除所有和A有交集的列,即第1、4、7列。
现在矩阵的状态为
2 3 5 6
D 0 1 1 1
6、由于现在的矩阵只剩下1行,且第2列为0,这意味着,当前解S={A,D}的并集中肯定不含元素2,
所以S={A,D}不是一个可行解,因此要回退到第2步的状态,然后从子集B开始求解
7、回退到步骤2将子集B加入到S中,S={B}
8、将所有和B有交集的行和列从矩阵中删除。即删除行A,B,C和列1,4,删除之后,矩阵M的新状态为
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
9、找出目前M中含1最少的列,显然这一步得到的列号为5.
10、和第5列有交集的行(即含元素5的子集)只有D。
11、将D加入到解集中,现在S={B,D}
12、删除所有和D相交的行和列,于是删除了列3,5,6和行D、E,现在矩阵的状态为
2 7
F 1 1
13、由于现在剩下的是全1行,因此把F加入到解集中,S={B,D,F},现在,容易验证这是一个可行解,算法结束