精確覆蓋問題學習筆記(三)——算法的初步實現

一、類CExactCoverSolution的聲明

[cpp]
#include<vector>  
#include<string>  
#include <algorithm>  
#include <iostream>  
using namespace std; 
 
//類型的定義  
typedef int ELEMENT_TYPE; 
typedef char SUBSET_NAME;  
typedef vector<int> ROW; 
typedef vector<ROW> MATRIX; 
typedef vector<ELEMENT_TYPE> FULL_SET; 
typedef vector<SUBSET_NAME> SUBSET_NAMES; 
typedef SUBSET_NAMES SOLUTION; 
 
class CExactCoverSolution 
{ 
public: 
    CExactCoverSolution(const MATRIX& matrix 
        ,const SUBSET_NAMES& names 
        ); 
 
    ~CExactCoverSolution(void); 
 
    const MATRIX& m_matrix;    //0-1矩陣  
    SOLUTION  m_solution;      //當前可行解  
    const SUBSET_NAMES& m_subsetNames;   //子集的名字  
     
    const int m_elementNum;    //元素的個數  
    const int m_subsetNum;     //子集的數目  
 
     
    //計算某一列的和  
    int GetColumnCount(int columnIndex)const; 
    int  GetMinColumnIndex(int &sum)const; //找出含1個數最少的列號  
     
    //判斷某一行是否全1  
    bool isFullOneRow(int rowIndex) const; 
    int getFullOneRow()const; 
 
    //獲取和第c列相交或者不的所有行  
    void getRowNos(const int c,vector<int>& rows,int value=1)const; 
 
    //獲取和第r行相交或者不相交的所有列  
    void getColumnNos(const int r,vector<int>& columns,int value=1)const; 
 
    //獲取和第r行無公共元素的各行  
    void getOtherRows(const int r,vector<int>& otherrows)const;  
 
    //在舊矩陣中去掉所有和row相交的行和列，獲得新的矩陣，  
    void getNewMatrix(const vector<int>& rows,const vector<int>& columns,MATRIX& matrix)const; 
 
    void getNewNames(const vector<int>& rows,SUBSET_NAMES& names)const; 
 
public: 
    bool search();  //求解  
     
public: 
    void print(ostream&os=cout)const; 
     
}; 

#include<vector>
#include<string>
#include <algorithm>
#include <iostream>
using namespace std;

//類型的定義
typedef int ELEMENT_TYPE;
typedef char SUBSET_NAME;
typedef vector<int> ROW;
typedef vector<ROW> MATRIX;
typedef vector<ELEMENT_TYPE> FULL_SET;
typedef vector<SUBSET_NAME> SUBSET_NAMES;
typedef SUBSET_NAMES SOLUTION;

class CExactCoverSolution
{
public:
 CExactCoverSolution(const MATRIX& matrix
  ,const SUBSET_NAMES& names
  );

 ~CExactCoverSolution(void);

 const MATRIX& m_matrix;    //0-1矩陣
 SOLUTION  m_solution;      //當前可行解
 const SUBSET_NAMES& m_subsetNames;   //子集的名字
 
 const int m_elementNum;    //元素的個數
 const int m_subsetNum;     //子集的數目

 
 //計算某一列的和
 int GetColumnCount(int columnIndex)const;
 int  GetMinColumnIndex(int &sum)const; //找出含1個數最少的列號
 
 //判斷某一行是否全1
 bool isFullOneRow(int rowIndex) const;
 int getFullOneRow()const;

 //獲取和第c列相交或者不的所有行
 void getRowNos(const int c,vector<int>& rows,int value=1)const;

 //獲取和第r行相交或者不相交的所有列
 void getColumnNos(const int r,vector<int>& columns,int value=1)const;

 //獲取和第r行無公共元素的各行
 void getOtherRows(const int r,vector<int>& otherrows)const;

 //在舊矩陣中去掉所有和row相交的行和列，獲得新的矩陣，
 void getNewMatrix(const vector<int>& rows,const vector<int>& columns,MATRIX& matrix)const;

 void getNewNames(const vector<int>& rows,SUBSET_NAMES& names)const;

public:
 bool search();  //求解
 
public:
 void print(ostream&os=cout)const;
 
};
二、實現

[cpp]
#include "ExactCoverSolution.h"  
 
CExactCoverSolution 
     ::CExactCoverSolution(const MATRIX& matrix 
                    ,const SUBSET_NAMES& names 
                    ) 
        :m_matrix(matrix) 
        ,m_subsetNames(names) 
        ,m_elementNum(matrix[0].size()) 
        ,m_subsetNum(matrix.size()) 
{ 
     
} 
 
CExactCoverSolution::~CExactCoverSolution(void) 
{ 
} 
 
int CExactCoverSolution::GetMinColumnIndex( int &sum ) const 
{ 
    int ColumnIndex=0; 
    sum=GetColumnCount(ColumnIndex); 
 
    for(int i=1;i<m_elementNum;++i) 
    { 
        int newSum=0; 
        if ((newSum=GetColumnCount(i))<sum) 
        { 
            sum=newSum; 
            ColumnIndex = i; 
        } 
    } 
    return ColumnIndex; 
} 
 
 
 
bool CExactCoverSolution::search()  
{ 
    bool flag = false; 
    int rowIndex=-1; 
         
    //如果矩陣為空，則說明所有元素已經被得到已經得到可行解。  
    if (m_matrix.size()==0)  
        flag=true; 
 
    //如果有全1的行，則將該行加入到可行解中，並返回真  
    else if ((rowIndex=getFullOneRow())>=0) 
    { 
        m_solution.push_back(m_subsetNames[rowIndex]); 
        flag =true; 
    } 
     
    else  
    { 
        int sum=0; 
        int c =GetMinColumnIndex(sum); 
         
        if (sum==0) 
            flag =false; //如果有全0的列，則說明此時一定無解  
        else 
        { 
            //得到和第c列相交的所有行列表  
            vector<int> rows; 
            getRowNos(c,rows); 
 
            for(int i=0;i<rows.size();++i) 
            { 
                int r=rows[i]; 
                                                                 
                //得到和本行不相交的所有列  
                vector<int > columns; 
                getColumnNos(r,columns,0); 
 
 
                vector<int > other; 
                getOtherRows(r,other); 
 
                SUBSET_NAMES names; 
                getNewNames(other,names); 
 
                MATRIX matrix; 
                getNewMatrix(other,columns,matrix); 
 
                CExactCoverSolution s(matrix,names); 
                flag = s.search(); 
                if (flag) 
                { 
                    m_solution.push_back(m_subsetNames[r]); 
                    m_solution.insert(m_solution.end(),s.m_solution.begin(),s.m_solution.end()); 
                    break; 
                } 
            } 
        } 
    } 
    return flag; 
} 
 
 
 
 
//判斷某一行是否全1  
bool CExactCoverSolution::isFullOneRow(int rowIndex) const 
{ 
    bool flag =true; 
    for (int i=0;i<m_elementNum;++i) 
        if (m_matrix[rowIndex][i]==0) 
        { 
            flag=false; 
            break; 
        } 
    return flag; 
} 
 
int CExactCoverSolution::getFullOneRow() const 
{ 
    bool flag =false; 
    int rowIndex = -1; 
    for (int i=0;i<m_subsetNum && !flag;++i) 
    { 
        if (isFullOneRow(i)) 
        { 
            rowIndex = i; 
            break; 
        } 
    } 
    return rowIndex; 
} 
 
 
int CExactCoverSolution::GetColumnCount( int columnIndex ) const 
{ 
    int sum=0; 
    for(int i=0;i<m_subsetNum;++i) 
        sum += m_matrix[i][columnIndex]; 
     
    return sum; 
} 
 
void CExactCoverSolution::getRowNos( const int c,vector<int>& rows,int value) const 
{ 
    for (int i=0;i<m_subsetNum;++i) 
        if (m_matrix[i][c]==value) 
            rows.push_back(i); 
} 
 
void CExactCoverSolution::getColumnNos( const int r,vector<int>& columns,int value) const 
{ 
    for (int i=0;i<m_elementNum;++i) 
        if (m_matrix[r][i]==value) 
                columns.push_back(i); 
} 
 
void CExactCoverSolution::getOtherRows( const int r,vector<int>& otherrows )const 
{ 
    for(int i=0;i<m_subsetNum;++i) 
    { 
        bool flag=true; 
        for(int j=0;j<m_elementNum;++j) 
            if (m_matrix[i][j]==m_matrix[r][j] && m_matrix[r][j]==1) 
            { 
                flag=false; 
                break; 
            } 
        if (flag) 
            otherrows.push_back(i); 
    } 
} 
 
void CExactCoverSolution::getNewNames( const vector<int>& rows,SUBSET_NAMES& names ) const 
{ 
    for(int i=0;i<rows.size();++i) 
        names.push_back(m_subsetNames[rows[i]]); 
} 
 
void CExactCoverSolution::getNewMatrix( const vector<int>& rows,const vector<int>& columns,MATRIX& matrix ) const 
{ 
    matrix=MATRIX(rows.size(),vector<int>(columns.size())); 
    for(int i=0;i<rows.size();++i) 
        for(int j=0;j<columns.size();++j) 
            matrix[i][j]=m_matrix[rows[i]][columns[j]]; 
} 
 
void CExactCoverSolution::print(ostream&os ) const 
{ 
    os << m_solution[0]; 
    for (int i=1;i<m_solution.size();++i) 
    { 
        os << ","<<m_solution[i]; 
    } 
} 

#include "ExactCoverSolution.h"

CExactCoverSolution
  ::CExactCoverSolution(const MATRIX& matrix
     ,const SUBSET_NAMES& names
     )
  :m_matrix(matrix)
  ,m_subsetNames(names)
  ,m_elementNum(matrix[0].size())
  ,m_subsetNum(matrix.size())
{
 
}

CExactCoverSolution::~CExactCoverSolution(void)
{
}

int CExactCoverSolution::GetMinColumnIndex( int &sum ) const
{
 int ColumnIndex=0;
 sum=GetColumnCount(ColumnIndex);

 for(int i=1;i<m_elementNum;++i)
 {
  int newSum=0;
  if ((newSum=GetColumnCount(i))<sum)
  {
   sum=newSum;
   ColumnIndex = i;
  }
 }
 return ColumnIndex;
}

bool CExactCoverSolution::search()
{
 bool flag = false;
 int rowIndex=-1;
  
 //如果矩陣為空，則說明所有元素已經被得到已經得到可行解。
 if (m_matrix.size()==0)
  flag=true;

 //如果有全1的行，則將該行加入到可行解中，並返回真
 else if ((rowIndex=getFullOneRow())>=0)
 {
  m_solution.push_back(m_subsetNames[rowIndex]);
  flag =true;
 }
 
 else
 {
  int sum=0;
  int c =GetMinColumnIndex(sum);
  
  if (sum==0)
   flag =false; //如果有全0的列，則說明此時一定無解
  else
  {
   //得到和第c列相交的所有行列表
   vector<int> rows;
   getRowNos(c,rows);

   for(int i=0;i<rows.size();++i)
   {
    int r=rows[i];
                
    //得到和本行不相交的所有列
    vector<int > columns;
    getColumnNos(r,columns,0);

    vector<int > other;
    getOtherRows(r,other);

    SUBSET_NAMES names;
    getNewNames(other,names);

    MATRIX matrix;
    getNewMatrix(other,columns,matrix);

    CExactCoverSolution s(matrix,names);
    flag = s.search();
    if (flag)
    {
     m_solution.push_back(m_subsetNames[r]);
     m_solution.insert(m_solution.end(),s.m_solution.begin(),s.m_solution.end());
     break;
    }
   }
  }
 }
 return flag;
}

//判斷某一行是否全1
bool CExactCoverSolution::isFullOneRow(int rowIndex) const
{
 bool flag =true;
 for (int i=0;i<m_elementNum;++i)
  if (m_matrix[rowIndex][i]==0)
  {
   flag=false;
   break;
  }
 return flag;
}

int CExactCoverSolution::getFullOneRow() const
{
 bool flag =false;
 int rowIndex = -1;
 for (int i=0;i<m_subsetNum && !flag;++i)
 {
  if (isFullOneRow(i))
  {
   rowIndex = i;
   break;
  }
 }
 return rowIndex;
}

int CExactCoverSolution::GetColumnCount( int columnIndex ) const
{
 int sum=0;
 for(int i=0;i<m_subsetNum;++i)
  sum += m_matrix[i][columnIndex];
 
 return sum;
}

void CExactCoverSolution::getRowNos( const int c,vector<int>& rows,int value) const
{
 for (int i=0;i<m_subsetNum;++i)
  if (m_matrix[i][c]==value)
   rows.push_back(i);
}

void CExactCoverSolution::getColumnNos( const int r,vector<int>& columns,int value) const
{
 for (int i=0;i<m_elementNum;++i)
  if (m_matrix[r][i]==value)
    columns.push_back(i);
}

void CExactCoverSolution::getOtherRows( const int r,vector<int>& otherrows )const
{
 for(int i=0;i<m_subsetNum;++i)
 {
  bool flag=true;
  for(int j=0;j<m_elementNum;++j)
   if (m_matrix[i][j]==m_matrix[r][j] && m_matrix[r][j]==1)
   {
    flag=false;
    break;
   }
  if (flag)
   otherrows.push_back(i);
 }
}

void CExactCoverSolution::getNewNames( const vector<int>& rows,SUBSET_NAMES& names ) const
{
 for(int i=0;i<rows.size();++i)
  names.push_back(m_subsetNames[rows[i]]);
}

void CExactCoverSolution::getNewMatrix( const vector<int>& rows,const vector<int>& columns,MATRIX& matrix ) const
{
 matrix=MATRIX(rows.size(),vector<int>(columns.size()));
 for(int i=0;i<rows.size();++i)
  for(int j=0;j<columns.size();++j)
   matrix[i][j]=m_matrix[rows[i]][columns[j]];
}

void CExactCoverSolution::print(ostream&os ) const
{
 os << m_solution[0];
 for (int i=1;i<m_solution.size();++i)
 {
  os << ","<<m_solution[i];
 }
}

三、測試代碼

[csharp]
#include <cstdlib> 
#include <iostream> 
#include <fstream> 
#include <vector>  
using namespace std; 
 
#include "ExactCoverSolution.h"  
 
const int ELEMENT_NUM=7 ; //元素的個數  
const int SUBSET_NUM=6;   //子集的個數  
 
const int U[ELEMENT_NUM]={1,2,3,4,5,6,7};  //全集  
const char NAMES[SUBSET_NUM]={'A','B','C','D','E','F'};  //各子集的名字  
//0-1矩陣  
const int Matrix[SUBSET_NUM][ELEMENT_NUM]={ 
     {1,0,0,1,0,0,1} 
    ,{1,0,0,1,0,0,0} 
    ,{0,0,0,1,1,0,0} 
    ,{0,0,1,0,1,1,0} 
    ,{0,1,1,0,0,1,1} 
    ,{0,1,0,0,0,0,1} 
}; 
 
 
 
int main(int argc,char* argv[]) 
{ 
    vector<vector<int> > M(SUBSET_NUM,vector<int>(ELEMENT_NUM)); 
    for (int i=0;i<SUBSET_NUM;++i) 
        for (int j=0;j<ELEMENT_NUM;++j) 
            M[i][j]=Matrix[i][j]; 
 
    FULL_SET values(U,U+ELEMENT_NUM); 
    SUBSET_NAMES names(NAMES,NAMES+SUBSET_NUM); 
    CExactCoverSolution s(M,names); 
     
    if (s.search()) 
        s.print(); 
    cout<<endl; 
     
    system("pause"); 
    return 0; 
} 

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#include "ExactCoverSolution.h"

const int ELEMENT_NUM=7 ; //元素的個數
const int SUBSET_NUM=6;   //子集的個數

const int U[ELEMENT_NUM]={1,2,3,4,5,6,7};  //全集
const char NAMES[SUBSET_NUM]={'A','B','C','D','E','F'};  //各子集的名字
//0-1矩陣
const int Matrix[SUBSET_NUM][ELEMENT_NUM]={
  {1,0,0,1,0,0,1}
 ,{1,0,0,1,0,0,0}
 ,{0,0,0,1,1,0,0}
 ,{0,0,1,0,1,1,0}
 ,{0,1,1,0,0,1,1}
 ,{0,1,0,0,0,0,1}
};

int main(int argc,char* argv[])
{
 vector<vector<int> > M(SUBSET_NUM,vector<int>(ELEMENT_NUM));
 for (int i=0;i<SUBSET_NUM;++i)
  for (int j=0;j<ELEMENT_NUM;++j)
   M[i][j]=Matrix[i][j];

 FULL_SET values(U,U+ELEMENT_NUM);
 SUBSET_NAMES names(NAMES,NAMES+SUBSET_NUM);
 CExactCoverSolution s(M,names);
 
 if (s.search())
  s.print();
 cout<<endl;
 
 system("pause");
 return 0;
}

四、運行結果