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

#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 newSum=0;
if ((newSum=GetColumnCount(i)) {
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 rows;
getRowNos(c,rows);

for(int i=0;i {
int r=rows[i];

//得到和本行不相交的所有列
vector columns;
getColumnNos(r,columns,0);

vector 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 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 {
if (isFullOneRow(i))
{
rowIndex = i;
break;
}
}
return rowIndex;
}

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

return sum;
}

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

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

void CExactCoverSolution::getOtherRows( const int r,vector& otherrows )const
{
for(int i=0;i {
bool flag=true;
for(int j=0;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& rows,SUBSET_NAMES& names ) const
{
for(int i=0;i names.push_back(m_subsetNames[rows[i]]);
}

void CExactCoverSolution::getNewMatrix( const vector& rows,const vector& columns,MATRIX& matrix ) const
{
matrix=MATRIX(rows.size(),vector(columns.size()));
for(int i=0;i for(int