精确覆盖问题学习笔记(五)――优化算法的实现代码 - c++编程基础

}
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;
}

//文件ExactCover.cpp
#include
#include
#include
using namespace std;
#include "ExactCover.h"
void CExactCover::CreateHead( const vector >& matrix )
{
m_master = new CColumnHead;
m_master->size = 0;
m_master->Left = m_master;
m_master->Right = m_master;

CColumnHead* prev = m_master;

const int elementNum = matrix[0].size();
for (int i = 0
; i < elementNum
;++i
)
{
CColumnHead* c=new CColumnHead;
c->name = i+1;
c->size = 0;

prev->Right = c;
c->Left = prev;

c->Right = m_master;
m_master->Left = c;

c->Up = c;
c->Down = c;

prev = c;
++m_master->size;
}
}

void CExactCover::CreateRows( const vector >& matrix )
{
const int subsetNum=matrix.size();
const int elementNum = matrix[0].size();

for (int i=0;i {
CGrid* head=NULL;
CGrid* prev=NULL;
int num=0;
for(int j=0;j {
if (matrix[i][j]==1)
{
++num;

CGrid* cell=new CGrid;
cell->name=i;

CColumnHead* c=const_cast(getColumn(j+1));
CGrid* lastCell = static_cast(c->Up);

lastCell->Down = cell;
cell->Up= lastCell;

c->Up = cell;
cell->Down = c;
cell->columnHead = c;

++c->size;

if (num==1)
{
head = cell;
prev = head;
}

cell->Left = prev;
cell->Right = head;

head->Left = cell;
prev->Right = cell;

prev = cell;
}
}
}
}

CExactCover::CExactCover(const vector >& matrix)
{
CreateHead(matrix);
CreateRows(matrix);

}

CExactCover::~CExactCover(void)
{

}
void CExactCover::cover(const CColumnHead *c )
{
//将第c列从列标题中删除
c->Right->Left = c->Left;
c->Left->Right = c->Right;
m_master->size--;

//依次处理和所有和本列相关的行
for (CNode* columnNode = c->Down
;columnNode != static_cast (c)
;columnNode = columnNode->Down
)
{

//依次向右遍历本行的除第c列以外的的每个节点
for (CGrid* rowNode=static_cast(columnNode->Right)
;rowNode!=columnNode
;rowNode=static_cast(rowNode->Right)
)
{

//将本行的当前节点从所在列中摘除
rowNode->Up->Down = rowNode->Down;
rowNode->Down->Up = rowNode->Up;

rowNode->columnHead->size--; //摘除完毕之后所在列的元素个数减1
}

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