精确覆盖问题学习笔记(五)――优化算法的实现代码 (五)

void CExactCover::uncover(const CColumnHead *c){

//将本列的各相关行加入到矩阵中
for (CNode* columnNode=c->Up
;columnNode != c
;columnNode = columnNode->Up
)
{
for (CGrid* rowNode=static_cast(columnNode->Right)
;rowNode!=columnNode
;rowNode=static_cast(rowNode->Right)
)
{
//将本行的当前节点加回到原来的列中
rowNode->Up->Down = rowNode;
rowNode->Down->Up = rowNode;

rowNode->columnHead->size++; //恢复完毕之后所在列的元素个数加1
}
}

//把c列重新到加入列标题中
c->Left->Right=const_cast(c);
c->Right->Left=const_cast(c);
m_master->size++;
}

bool CExactCover::search(int k)
{
bool flag = false;

//矩阵为空时问题已经解决，返回true
if (m_master->Right==m_master)
flag =true;
else
{
cover(c);

for ( CGrid* row=static_cast(c->Down)
; static_cast(row)!= static_cast(const_cast(c))
;row=static_cast(row->Down),++sublevel
)
{
for(CGrid* cell=static_cast(row->Right)
;cell!=row
;cell=static_cast(cell->Right)
)
{
cover(cell->columnHead);
}

flag =search(k+1);

if (flag)
{
m_solution.insert(row->name);
flag = true;
break;
}
else
{
for ( CGrid* cell=static_cast(row->Left)
; cell!=row
; cell=static_cast(cell->Left)
)
{
uncover(cell->columnHead);
}
}

}
if (!flag)
uncover(c);
}
return flag;
}

const CColumnHead* CExactCover::selectColumn() const
{
CColumnHead *min=static_cast(m_master->Right);

for (CColumnHead *c=min
;c!=m_master
;c=static_cast(c->Right)
)
{
if (c->sizesize)
min=c;
}
return min;
}

void CExactCover::print
(const vector >& matrix
,ostream& os/*=log*/
)const
{
const int elementNum = matrix[0].size();
for(set::const_iterator it = m_solution.begin()
;it != m_solution.end()
;++it
)
{
os << (char)('A'+*it)<<"={";
int i=*it;
for(int j=0;j os << matrix[i][j] << ' ';
os << "}"< }
}

const CColumnHead* CExactCover::getColumn( int name ) const
{
CColumnHead* c=static_cast(m_master->Right);
for (
; c!= m_master
; c=static_cast(c->Right)
)
{
if (c->name==name)
break;
}

return c;
}
[cpp] /文件main.cpp
#include "ExactCover.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,1}
,{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 > M(SUBSET_NUM, vector(ELEMENT_NUM));
for(int i=0;i for(int j=0;j M[i][j] = Matrix[i][j];

CExactCover s(M);

if (s.search())
s.print(M,cout);

system("pause");

return 0;
}

//文件main.cpp
#include "ExactCover.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,1}
,{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 > M(SUBSET_NUM, vector(ELEMENT_NUM));
for(int i=0;i for(int j=0;j M[i][j] = Matrix[i][j];

CExactCover s(M);

if (s.search())
s.print(M,cout);

system("pause"