精確覆蓋問題學習筆記(五)——優化算法的實現代碼

[cpp] /文件node.h  
#pragma once  
 
struct CNode 
{ 
    CNode* Left;      //左節點指針  
    CNode* Right;     //右節點指針  
 
    CNode* Up;        //上節點指針,對列節點，則為本列最後一個元素的指針  
    CNode* Down;      //下節點指針,對列節點，則為本列第一個元素的指針  
     
    int name;           //對普通節點，為所在子集的編號,即行號;  
                        //對列節點，為列編號  
}; 
 
struct CColumnHead:public CNode 
{ 
    int size;   //本列元素的個數  
}; 
 
 
 
struct CGrid:public CNode 
{ 
    CColumnHead* columnHead;   //列頭節點的指針  
 
}; 

//文件node.h
#pragma once

struct CNode
{
 CNode* Left;      //左節點指針
 CNode* Right;     //右節點指針

 CNode* Up;        //上節點指針,對列節點，則為本列最後一個元素的指針
 CNode* Down;      //下節點指針,對列節點，則為本列第一個元素的指針
 
 int name;   //對普通節點，為所在子集的編號,即行號;
      //對列節點，為列編號
};

struct CColumnHead:public CNode
{
 int size;   //本列元素的個數
};

struct CGrid:public CNode
{
 CColumnHead* columnHead;   //列頭節點的指針

};
[cpp]  //文件ExactCover.h  
#pragma once  
#include <vector>  
#include <set>  
#include <iostream>  
#include <fstream>  
using namespace std; 
#include "node.h"  
 
class CExactCover 
{ 
public: 
    CExactCover(const vector<vector <int> >& matrix); //從矩陣中讀入數據，建立鏈表  
    ~CExactCover(void); 
 
private: 
    const CColumnHead* getColumn(int name)const; 
    const CColumnHead* selectColumn()const;        //選擇含1個數最少的列        
    void cover(const CColumnHead *c);        //將某一列及其相關的節點從矩陣中刪除  
    void uncover(const CColumnHead *c);      //將某一列及其相關的節點重新加入到矩陣中  
    void CreateHead(const vector<vector <int> >& matrix); //建立頭節點鏈表  
    void CreateRows(const vector<vector <int> >& matrix);  //建立數據節點  
 
    bool search();   //求解算法  
    void print(const vector<vector <int> >& matrix,ostream &os) const; //輸出可行解private:set<int>m_solution; //解集  
    CColumnHead* m_master; //列頭鏈表的頭節點  
}; 

//文件ExactCover.h
#pragma once
#include <vector>
#include <set>
#include <iostream>
#include <fstream>
using namespace std;
#include "node.h"

class CExactCover
{
public:
 CExactCover(const vector<vector <int> >& matrix); //從矩陣中讀入數據，建立鏈表
 ~CExactCover(void);

private:
 const CColumnHead* getColumn(int name)const;
 const CColumnHead* selectColumn()const;        //選擇含1個數最少的列     
 void cover(const CColumnHead *c);        //將某一列及其相關的節點從矩陣中刪除
 void uncover(const CColumnHead *c);      //將某一列及其相關的節點重新加入到矩陣中
 void CreateHead(const vector<vector <int> >& matrix); //建立頭節點鏈表
 void CreateRows(const vector<vector <int> >& matrix);  //建立數據節點

 bool search();   //求解算法
 void print(const vector<vector <int> >& matrix,ostream &os) const; //輸出可行解private:set<int>m_solution; //解集
 CColumnHead* m_master; //列頭鏈表的頭節點
};
[cpp] //文件ExactCover.cpp  
#include <iomanip>  
#include <sstream>  
#include <map>  
using namespace std; 
#include "ExactCover.h"  
void CExactCover::CreateHead( const vector<vector <int> >& 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<vector <int> >& matrix ) 
{ 
    const int subsetNum=matrix.size(); 
    const int elementNum = matrix[0].size(); 
     
    for (int i=0;i<subsetNum;++i) 
    { 
        CGrid* head=NULL; 
        CGrid* prev=NULL; 
        int num=0; 
        for(int j=0;j<elementNum;++j) 
        { 
            if (matrix[i][j]==1) 
            { 
                ++num; 
 
                CGrid* cell=new CGrid; 
                cell->name=i; 
                 
                CColumnHead* c=const_cast<CColumnHead*>(getColumn(j+1)); 
                CGrid* lastCell = static_cast<CGrid*>(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<vector <int> >& 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<const CNode*> (c) 
        ;columnNode = columnNode->Down 
        ) 
    { 
 
        //依次向右遍歷本行的除第c列以外的的每個節點  
        for (CGrid* rowNode=static_cast<CGrid*>(columnNode->Right) 
            ;rowNode!=columnNode 
            ;rowNode=static_cast<CGrid*>(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<CGrid*>(columnNode->Right) 
            ;rowNode!=columnNode 
            ;rowNode=static_cast<CGrid*>(rowNode->Right) 
            ) 
        { 
            //將本行的當前節點加回到原來的列中  
            rowNode->Up->Down = rowNode; 
            rowNode->Down->Up = rowNode;  
 
            rowNode->columnHead->size++;     //恢復完畢之後所在列的元素個數加1  
        } 
    } 
     
    //把c列重新到加入列標題中  
    c->Left->Right=const_cast<CColumnHead*>(c); 
    c->Right->Left=const_cast<CColumnHead*>(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<CGrid*>(c->Down) 
            ; static_cast<CNode*>(row)!= static_cast<CNode*>(const_cast<CColumnHead*>(c)) 
            ;row=static_cast<CGrid*>(row->Down),++sublevel 
            ) 
        { 
            for(CGrid* cell=static_cast<CGrid*>(row->Right) 
                ;cell!=row 
                ;cell=static_cast<CGrid*>(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<CGrid*>(row->Left) 
                    ; cell!=row 
                    ; cell=static_cast<CGrid*>(cell->Left) 
                    ) 
                { 
                    uncover(cell->columnHead); 
                } 
            } 
 
 
        } 
        if (!flag) 
            uncover(c); 
    } 
    return flag; 
} 
 
const CColumnHead* CExactCover::selectColumn() const 
{ 
    CColumnHead *min=static_cast<CColumnHead*>(m_master->Right); 
     
    for (CColumnHead *c=min 
        ;c!=m_master 
        ;c=static_cast<CColumnHead*>(c->Right) 
        ) 
    { 
        if (c->size<min->size) 
            min=c; 
    } 
    return min; 
} 
 
void CExactCover::print 
     (const vector<vector <int> >& matrix 
      ,ostream& os/*=log*/  
     )const 
{ 
    const int elementNum = matrix[0].size(); 
    for(set<int>::const_iterator it = m_solution.begin() 
        ;it != m_solution.end()  
        ;++it 
        ) 
    { 
                os << (char)('A'+*it)<<"={"; 
        int i=*it; 
        for(int j=0;j<elementNum;++j) 
            os << matrix[i][j] << ' '; 
        os << "}"<<endl; 
    } 
} 
 
const CColumnHead* CExactCover::getColumn( int name ) const 
{ 
    CColumnHead* c=static_cast<CColumnHead*>(m_master->Right); 
    for (  
        ; c!= m_master 
        ; c=static_cast<CColumnHead*>(c->Right) 
        ) 
    { 
        if (c->name==name) 
            break; 
    } 
 
    return c; 
} 

//文件ExactCover.cpp
#include <iomanip>
#include <sstream>
#include <map>
using namespace std;
#include "ExactCover.h"
void CExactCover::CreateHead( const vector<vector <int> >& 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<vector <int> >& matrix )
{
 const int subsetNum=matrix.size();
 const int elementNum = matrix[0].size();
 
 for (int i=0;i<subsetNum;++i)
 {
  CGrid* head=NULL;
  CGrid* prev=NULL;
  int num=0;
  for(int j=0;j<elementNum;++j)
  {
   if (matrix[i][j]==1)
   {
    ++num;

    CGrid* cell=new CGrid;
    cell->name=i;
    
    CColumnHead* c=const_cast<CColumnHead*>(getColumn(j+1));
    CGrid* lastCell = static_cast<CGrid*>(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<vector <int> >& 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<const CNode*> (c)
  ;columnNode = columnNode->Down
  )
 {

  //依次向右遍歷本行的除第c列以外的的每個節點
  for (CGrid* rowNode=static_cast<CGrid*>(columnNode->Right)
   ;rowNode!=columnNode
   ;rowNode=static_cast<CGrid*>(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<CGrid*>(columnNode->Right)
   ;rowNode!=columnNode
   ;rowNode=static_cast<CGrid*>(rowNode->Right)
   )
  {
   //將本行的當前節點加回到原來的列中
   rowNode->Up->Down = rowNode;
   rowNode->Down->Up = rowNode;

   rowNode->columnHead->size++;     //恢復完畢之後所在列的元素個數加1
  }
 }
 
 //把c列重新到加入列標題中
 c->Left->Right=const_cast<CColumnHead*>(c);
 c->Right->Left=const_cast<CColumnHead*>(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<CGrid*>(c->Down)
   ; static_cast<CNode*>(row)!= static_cast<CNode*>(const_cast<CColumnHead*>(c))
   ;row=static_cast<CGrid*>(row->Down),++sublevel
   )
  {
   for(CGrid* cell=static_cast<CGrid*>(row->Right)
    ;cell!=row
    ;cell=static_cast<CGrid*>(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<CGrid*>(row->Left)
     ; cell!=row
     ; cell=static_cast<CGrid*>(cell->Left)
     )
    {
     uncover(cell->columnHead);
    }
   }

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

const CColumnHead* CExactCover::selectColumn() const
{
 CColumnHead *min=static_cast<CColumnHead*>(m_master->Right);
 
 for (CColumnHead *c=min
  ;c!=m_master
  ;c=static_cast<CColumnHead*>(c->Right)
  )
 {
  if (c->size<min->size)
   min=c;
 }
 return min;
}

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

const CColumnHead* CExactCover::getColumn( int name ) const
{
 CColumnHead* c=static_cast<CColumnHead*>(m_master->Right);
 for (
  ; c!= m_master
  ; c=static_cast<CColumnHead*>(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<vector <int> > M(SUBSET_NUM, vector<int>(ELEMENT_NUM)); 
    for(int i=0;i<SUBSET_NUM;++i) 
        for(int j=0;j<ELEMENT_NUM;++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<vector <int> > M(SUBSET_NUM, vector<int>(ELEMENT_NUM));
 for(int i=0;i<SUBSET_NUM;++i)
  for(int j=0;j<ELEMENT_NUM;++j)
   M[i][j] = Matrix[i][j];

 CExactCover s(M);

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

 system("pause");

 return 0;
}

運行結果:

[cpp]
B={1 0 0 1 0 0 0 } 
D={0 0 1 0 1 1 0 } 
F={0 1 0 0 0 0 1 }