首页 > 代码库 > Dancing Links
Dancing Links
Dancing Links用来解决如下精确匹配的问题:
选择若干行使得每一列恰好有一个1。Dancing Links通过对非零元素建立双向十字循环链表。上面的例子建立的链表如下所示：
计算的时候使用搜索的策略。每次选出1最少的一列，比如c，然后选择这一列中的某一行，比如r，(r,c)=1,然后r中所有1所在的列，那些其他行这些列有1的都删掉（这些行不会在r算入答案后也在答案里，否则就有某些列多于一个1出现）。然后这就变成一个规模更小的问题，继续搜索。无解时要回溯。
1 class CDancingLinks 2 { 3 protected: 4 struct DancingLinksNode 5 { 6 DancingLinksNode* left; 7 DancingLinksNode* right; 8 DancingLinksNode* down; 9 DancingLinksNode* up; 10 int col; 11 int row; 12 }; 13 14 typedef DancingLinksNode Node; 15 16 int *m_columnEleNumbers; 17 int m_colNumber; 18 int m_rowNumber; 19 Node* m_pool; 20 Node** m_head; 21 int m_curUsePoolIndex; 22 23 24 25 26 27 void _Remove(Node* cur) 28 { 29 --m_columnEleNumbers[cur->col]; 30 for(Node* p=cur->down;p!=cur;p=p->down) 31 { 32 p->left->right=p->right; 33 p->right->left=p->left; 34 } 35 } 36 37 void _Resume(Node* cur) 38 { 39 ++m_columnEleNumbers[cur->col]; 40 for(Node* p=cur->up;p!=cur;p=p->up) 41 { 42 p->left->right=p; 43 p->right->left=p; 44 } 45 } 46 47 48 49 bool _SearchSolution(const int depth,std::vector<int> &solution) 50 { 51 Node* p=_GetNode(0); 52 if(p->left==p) return true; 53 54 int Min=m_rowNumber+1; 55 int MinColumnIndex=0; 56 for(Node* q=p->left;q!=p;q=q->left) 57 { 58 if(m_columnEleNumbers[q->col]<Min) 59 { 60 Min=m_columnEleNumbers[q->col]; 61 MinColumnIndex=q->col; 62 } 63 } 64 65 66 for(Node* q=_GetNode(MinColumnIndex)->down;q!=_GetNode(MinColumnIndex);q=q->down) 67 { 68 _Remove(q); 69 solution.push_back(q->row); 70 for(Node* rr=q->right;rr!=q;rr=rr->right) _Remove(rr); 71 if(_SearchSolution(depth+1,solution)) return true; 72 for(Node* rr=q->left;rr!=q;rr=rr->left) _Resume(rr); 73 solution.pop_back(); 74 _Resume(q); 75 } 76 77 return false; 78 } 79 80 Node* _GetNode(int id) { return m_pool+id; } 81 82 void _ReleaseMemory() 83 { 84 if(m_columnEleNumbers) 85 { 86 delete[] m_columnEleNumbers; 87 m_columnEleNumbers=nullptr; 88 } 89 90 if(m_pool) 91 { 92 delete[] m_pool; 93 m_pool=nullptr; 94 } 95 if(m_head) 96 { 97 delete[] m_head; 98 m_head=nullptr; 99 }100 }101 102 public:103 104 CDancingLinks():m_colNumber(-1),m_rowNumber(-1),105 m_columnEleNumbers(nullptr),m_pool(nullptr),m_head(nullptr) {}106 107 /***108 列下标为[1,Column]109 ***/110 CDancingLinks(const int Column,const int Row):111 m_columnEleNumbers(nullptr),m_pool(nullptr),m_head(nullptr)112 {113 SetSize(Column,Row);114 }115 116 /***117 列下标为[1,Column]118 ***/119 void SetSize(const int Column,const int Row)120 {121 m_colNumber=Column;122 m_rowNumber=Row;123 124 _ReleaseMemory();125 126 m_columnEleNumbers=new int[m_colNumber+1];127 m_pool=new Node[m_colNumber*(m_rowNumber+1)+1];128 m_head=new Node*[m_rowNumber+1];129 Clear();130 }131 132 void Clear()133 {134 for(int i=0;i<=m_colNumber;++i)135 {136 Node* cur=_GetNode(i);137 cur->left=((i==m_colNumber)?_GetNode(0):_GetNode(i+1));138 cur->right=((0==i)?_GetNode(m_colNumber):_GetNode(i-1));139 m_columnEleNumbers[i]=0;140 141 cur->up=cur->down=_GetNode(i);142 cur->col=i;143 cur->row=0;144 }145 for(int i=1;i<=m_rowNumber;++i) m_head[i]=NULL;146 m_curUsePoolIndex=m_colNumber+1;147 }148 149 ~CDancingLinks()150 {151 _ReleaseMemory();152 }153 154 void AddElement(const int row,const int col)155 {156 157 Node* cur=m_pool+(m_curUsePoolIndex++);158 159 cur->up=_GetNode(col);160 cur->down=_GetNode(col)->down;161 m_pool[col].down->up=cur;162 m_pool[col].down=cur;163 164 165 if(m_head[row]==NULL)166 {167 m_head[row]=cur->left=cur->right=cur;168 }169 else170 {171 cur->left=m_head[row]->left;172 cur->right=m_head[row];173 m_head[row]->left->right=cur;174 m_head[row]->left=cur;175 }176 ++m_columnEleNumbers[col];177 cur->col=col;178 cur->row=row;179 }180 181 bool GetSolution(std::vector<int> &Solution)182 {183 return _SearchSolution(0,Solution);184 }185 };
Dancing Links
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。