精确覆盖问题学习笔记(三)――算法的初步实现 (一)

一、类CExactCoverSolution的声明

[cpp]
#include
#include
#include
#include
using namespace std;

//类型的定义
typedef int ELEMENT_TYPE;
typedef char SUBSET_NAME;
typedef vector ROW;
typedef vector MATRIX;
typedef vector FULL_SET;
typedef vector 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& rows,int value=1)const;

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

//获取和第r行无公共元素的各行
void getOtherRows(const int r,vector& otherrows)const;

//在旧矩阵中去掉所有和row相交的行和列，获得新的矩阵，
void getNewMatrix(const vector& rows,const vector& columns,MATRIX& matrix)const;

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

public:
bool search(); //求解

public:
void print(ostream&os=cout)const;

};

#include
#include
#include
#include
using namespace std;

//类型的定义
typedef int ELEMENT_TYPE;
typedef char SUBSET_NAME;
typedef vector ROW;
typedef vector MATRIX;
typedef vector FULL_SET;
typedef vector 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& rows,int value=1)const;

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

//获取和第r行无公共元素的各行
void getOtherRows(const int r,vector& otherrows)const;

//在旧矩阵中去掉所有和row相交的行和列，获得新的矩阵，
void getNewMatrix(const vector& rows,const vector& columns,MATRIX& matrix)const;

void getNewNames(const vector& 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 {
int