C++实现QM算法

QM算法是用来最小化卡诺图的一个算法，其大概思路是，对蕴含项中1的个数进行分组，只有1的个数相差为1的蕴含项才可能相邻，所以可以通过循环来穷举出所有的主蕴含项。再建立主蕴含项和最小项的列表，找到质蕴涵项，再从剩下的主蕴含项中找到最小覆盖，输出结果。（算法原理比较简单，不详细说明了）

下面来看代码实现。

第一部分是先生成一个主蕴含项的链表。

在这里我们考虑一下链表节点，我们需要存储的信息有（1）代表该蕴含项的01串 （2）代表该蕴含项中哪些变量被消去，哪些变量存在 （3）该蕴含项是否被覆盖 （4）指向下一个节点的指针。另外，在这里我们还实现了一个计算该蕴含项中1的个数的函数。

 

struct ListNode{
	int zo;														//01串
	int mask;													//1代表该位被消去，为"_"
	int checked;												//该项是否被覆盖
	ListNode* next;
	ListNode() : zo(0),mask(0),checked(0),next(NULL) {}
	ListNode(int n) : zo(n),mask(0),checked(0),next(NULL){}
	//计算01串中1的个数
	int CalNumOne()
	{
		int num = 0;
		for(int i=1;i!=0;i<<=1)
			if(zo&i)
				num++;
		return num;
	}
};

现在我们可以输入最小项编号来读入最小项，接下来就是应该将其分组。

 

 

	ListNode Array[MAX_N];
	int caseNum;
	cout << "请输入变量个数" << endl;
	cin >> maxLen;							//全局变量
	cout << "请输入最小项个数" << endl;
	cin >> caseNum;
	int* minImplicant = new int[caseNum];
	cout << "请依次输入最小项" << endl;
	for(int i=0;i> tmpValue;
		minImplicant[i] = tmpValue;
		ListNode* tmpPtr = new ListNode(tmpValue);
		int tmpID = tmpPtr->CalNumOne();
		tmpPtr->next = Array[tmpID].next;
		Array[tmpID].next = tmpPtr;
	}

由于我们01串是用int型表示，故最多出现32个变量，也就是分组最多有33组，这就是MAX_N的值。那接下来我们要做的事情就是对相邻两组最小项的合并，

 

我们用一个Union函数来实现。

Union函数中我们调用了另外三个函数，此处只介绍其作用

1.HammiingClose()，输入两个ListNode*，判断两个蕴含项是否相邻，亦即能否合并

2.IsNotExisted()，输入一个链表头指针以及一个ListNode*，判断该链表中是否存在该蕴含项，若存在则返回0，不存在返回1

3.Dispose()，输入一个链表头指针，销毁该链表

Union函数的实现的主要思路是，

1. 如果该组没有元素，则什么都不做，返回

2. 如果该组的下一组为空，则将此时仍未被覆盖的蕴含项，也就是主蕴含项，添加到主蕴含项链表的前端

3. 如果该组的下一组不空，则先将该组的主蕴含项链表脱离该组，遍历所有组合，若能合并，则生成新的蕴含项，添加到该组；若不能，则将该蕴含项，也就是

主蕴含项，添加到主蕴含项链表中。

也就是说，该组执行完Union后，该组中的主蕴含项将被添加到主蕴含项链表中，和下一组生成的新的蕴含项将成为该组新的元素。执行完Union后，该组中只有“更大”的

蕴含项。值得注意的是，检查原组中未被覆盖的蕴含项并加入到主蕴含项链表前端的代码可以复用，所以我们采取了代码中的结构。另外值得注意的是，由于我们的添加

策略，主蕴含项链表中，“大”的主蕴含项始终会在链表前端，这对最后的覆盖最小集将有帮助。

 

void Union(ListNode* Array,int id)
{
	if(Array[id].next==NULL)
		return;
	ListNode TmpCell;
	TmpCell.next = Array[id].next;
	Array[id].next = NULL;
	if(id!=maxLen && Array[id+1].next!=NULL)
	{
		ListNode *ptr1, *ptr2;
		for(ptr1=TmpCell.next;ptr1;ptr1=ptr1->next)
			for(ptr2=Array[id+1].next;ptr2;ptr2=ptr2->next)
			{
				int pos = HammingClose(ptr1,ptr2);
				if(pos==-1) continue;
				ListNode* TmpCell = new ListNode(ptr1->zo);
				TmpCell->mask = ptr1->mask | pos;
				if(!IsNotExisted(&Array[id],TmpCell))
					delete TmpCell;
				else
				{
					ListNode* tmpPtr = Array[id].next;
					Array[id].next = TmpCell;
					TmpCell->next = tmpPtr;
				}
				ptr1->checked = 1;
				ptr2->checked = 1;
			}
	}
	ListNode* ptr = &TmpCell;
	while(ptr->next)
		if(!ptr->next->checked)
		{
			ListNode* tmpPrime = PrimList.next;
			ListNode* tmpPtr = ptr->next;
			ptr->next = ptr->next->next;
			PrimList.next = tmpPtr;
			tmpPtr->next = tmpPrime;
		}
		else	ptr = ptr->next;
	Dispose(TmpCell.next);
}

到这里我们只需要对原组进行循环，就可以得到所有的主蕴含项所构成的链表，且“大的”蕴含项将在链表前部。之后我们再将该链表转换成数组，便于建立图表及之后搜索的索引。CalculNum()和Transfer2Array()函数的细节在此不表，其功能分别是计算链表元素数目 和 将链表转换为数组。

 

 

	/*
	**循环相邻组的合并，主蕴含项去重加入到PrimList中
	*/
	
	for(int i=0;i<=maxLen;i++)
		for(int j=0;j<=maxLen;j++)
			Union(Array,j);

	/*
	**将PrimList转换成为数组,便于索引
	*/

	int primeNum = CalculNum(PrimList.next);
	ListNode** primeImplicant = Transfer2Array(PrimList.next,primeNum);

这之后就是建立最小项和主蕴含项的图表了，细节不表，matrix是一个全局的二级指针，采用全局变量的意义是为了之后的搜索

	/*
	**建表
	*/
	
	matrix = BuildMap(primeImplicant,primeNum,minImplicant,caseNum);

接下来我们重点讲讲搜索。

 

这里采用的是深度优先搜索。为了记录主蕴含项的选择情况以及最终的答案，我们申明两个数组visPr[]以及minPr[]，为了记录对最小项的覆盖情况，我们申明数组visMi[]，这里值得注意的是visMi[]中，我们记录的是该项被覆盖“次数”，这样做的原因是便于回溯。

在搜索之前我们先要找到质蕴涵项，并做好标记。

 

	/*
	**初始化深度优先搜索需要的几个数组和变量
	*/

	minNum = primeNum;
	visPr = new int[primeNum];
	minPr = new int[primeNum];
	for(int i=0;i 接下来就是开始搜索了，其思想就是（1）该元素在或者不在 （2）回溯，不详细展开了
 
思想如下： 
 （1）当所有元素都判断过时，返回。
 （2）当包含的主蕴含项已经和最小蕴含项想同，即该选择方法一定不会是最小集
  （3）若选择主蕴含项少于之前的最小数目，且已经覆盖所有最小项，则更新最小数目和对应的选择，返回
  （4）选择该元素，并改变相应的选择状态记录。返回时，回到选择之前的状态记录。
 （5）不选择该元素
值得注意的是，当出现相同的最小选择数目方案时，我们选择的是靠前出现的方案，根据我们的主蕴含项链表的规律，“越大的”主蕴含项越会被先访问，故我们可以保证，
得到的最小数目的覆盖方案，包含的变量数也一定是该数目下方案中最少的。
 
void DFS(int id,int curNum,int row,int col)
{
	if(id==row)									//若主蕴含项数组越界，退出
		return;
	if(curNum==minNum)							//若已经达到最小步数，即不可能能达到更小覆盖时，退出
		return;
	
	/*
	**检验此时是否完全覆盖最小项,注意此时的主蕴含项数目一定小于之前的最小值
	*/
	
	int flag = 1;
	for(int i=0;i<col;i++) flag="" minnum="curNum;" int="" i="0;i<row;i++)" -="matrix[id][i];" pre="">
;i++)>

最后输出结果即可，全部代码就不贴上来了。

（若您发现了任何问题，或有什么好的建议，烦请您告知我，十分感谢）