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

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

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;

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