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="">
最後輸出結果即可，全部代碼就不貼上來了。
（若您發現了任何問題，或有什麼好的建議，煩請您告知我，十分感謝）
