- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 38556
- 在线时间
- 小时
|
楼主 |
发表于 2018-3-1 10:42:50
|
显示全部楼层
9个人的问题，我开始使用BLISS库来过滤重复的搜索，但是后来发现BLISS库有严重的内存泄漏问题
后来改成使用nauty库: http://pallini.di.uniroma1.it/
这个库编译以后可以有多个不同版本，比如 nauty.a nautyL.a nautyL1.a nautyW.a 等
对于人数比较少时，如果人的数目加酒的数目不超过64，可以使用nautyL1.a会有比较好的效率
下面代码可以完成这个穷举工作，其中K=8(8个人）的代码很快可以运行完，但是9个人就需要运行1天多了
而10个人估计就要很长时间了。
代码会输出一些中间结果，如果将那些中间结果作为输入，代码可以自动从这些中间结果处继续开始
- #include <set>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #define MAXN 64
- #include "nauty/nauty.h"
- typedef unsigned int dtype;
- typedef std::set<dtype> UnionState;
- typedef std::vector<dtype> DataState;
- int bestn;
- #define UB 65
- #ifndef K
- #define K 9
- #endif
- #if K==8
- #define HK 3
- #define DUMP_RANGE 12
- #endif
- #if K == 9
- #define HK 4
- #define DUMP_RANGE 16
- #endif
- #if K == 10
- #define HK 5
- #define DUMP_RANGE 20
- #endif
- typedef struct _TGRAPH{
- graph data[MAXN];
- bool operator<(const struct _TGRAPH& g)const{
- int i;
- for(i=0;i<MAXN;i++){
- if(data[i]<g.data[i])return true;
- if(data[i]>g.data[i])return false;
- }
- return false;
- }
- bool operator==(const struct _TGRAPH& g)const{
- int i;
- for(i=0;i<MAXN;i++){
- if(data[i]!=g.data[i])return false;
- }
- return true;
- }
- _TGRAPH(){memset(data,0,sizeof(data));}
- _TGRAPH(const graph g[MAXN]){memcpy(data,g,sizeof(data));}
- }TGRAPH;
- int compg(const void *p, const void *q)
- {
- const TGRAPH *g1=(const TGRAPH *)p;
- const TGRAPH *g2=(const TGRAPH *)q;
- int i;
- for(i=0;i<MAXN;i++){
- if(g1->data[i]<g2->data[i])return -1;
- if(g1->data[i]>g2->data[i])return 1;
- }
- return 0;
- }
- UnionState us[UB];
- DataState ds;
- int curlevel;
- int curbest;
- #define tus us[curlevel]
- graph allg[UB][MAXN];
- graph normg[UB][MAXN];
- std::set<TGRAPH> usedg[UB];
- void graph_remove_node(graph g[MAXN], graph ng[MAXN], int node, int n)
- {
- int i;
- graph lm,rm;
- if(node>0){
- memcpy(ng, g, sizeof(g[0])*node);
- }
- if(node<n-1){
- memcpy(&ng[node],&g[node+1], sizeof(g[0])*(n-1-node));
- }
- memset(&ng[n-1], 0, sizeof(g[0])*(MAXN-n+1));
- if(node == 0){
- for(i=0;i<n-1;i++){
- ng[i]<<=1;
- }
- }else{
- lm=(1ULL<<node)-1;
- lm<<=64-node;
- rm=(1ULL<<(63-node))-1;
- for(i=0;i<n-1;i++){
- graph h=ng[i];
- ng[i] = (h&lm)|((h&rm)<<1);
- }
- }
- }
- void dump_normalized(graph g[MAXN],graph ng[MAXN], int orbits[MAXN], int n)
- {
- int i,j,e;
- int lab[MAXN], ptn[MAXN];
- static DEFAULTOPTIONS_GRAPH(options);
- statsblk stats;
- int m,v;
- memset(ng,0,sizeof(ng[0])*MAXN);
- m=SETWORDSNEEDED(n);
- nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
- options.getcanon = TRUE;
- options.defaultptn = FALSE;
- for(i=0;i<n;++i){
- lab[i]=i;
- }
- for(i=0;i<n;++i){
- ptn[i]=1;
- }
- ptn[K-1]=0;
- ptn[n-1]=0;
- densenauty(g, lab, ptn, orbits, &options, &stats, m, n, ng);
- }
- void init()
- {
- curlevel = 0;
- ds.clear();
- us[0].clear();
- }
- int bitcount(dtype d);
- int test_add(dtype d)
- {
- UnionState ls;
- if(bitcount(d)>HK)return -1;
- #ifdef STRICT
- if(tus.find(d)!=tus.end()){
- return -1;
- }
- ls.insert(d);
- #endif
- int i;
- for(i=0;i<ds.size();++i){
- if(ds[i]==d)return -1;
- dtype u=d|ds[i];
- if(tus.find(u)!=tus.end()){
- return -1;
- }
- if(ls.find(u)!=ls.end()){
- return -1;
- }
- ls.insert(u);
- }
- return 0;
- }
- int bitcount(dtype d){
- int i,b=0;
- for(i=0;i<K;i++){
- if(d&(1<<i))b++;
- }
- return b;
- }
- void do_add(dtype d){
- int i;
- #ifdef STRICT
- tus.insert(d);
- #endif
- for(i=0;i<ds.size();++i){
- dtype u=d|ds[i];
- tus.insert(u);
- }
- ds.push_back(d);
- }
- void pop()
- {
- ds.pop_back();
- curlevel--;
- }
- void dumpg(int n, int is_best)
- {
- int i;
- if(is_best){
- printf("Best edge %d\n\t",n-K);
- }else{
- printf("More edge %d\n\t",n-K);
- }
- for(i=K;i<n;i++){
- printf("%llx ",allg[curlevel][i]>>(64-K));
- }
- printf("\n");
- fflush(stdout);
- }
- FILE *fout;
- void search(int n, dtype initvalue[UB], int nextstep, int& maxstep)
- {
- int i,j;
- int orbits[MAXN],orbits2[MAXN];
- usedg[curlevel].clear();
- graph g[MAXN], ng[MAXN];
- memset(g,0,sizeof(g));
- memset(ng,0,sizeof(ng));
- if(bestn<n-1){
- bestn=n-1;
- dumpg(bestn,1);
- }else if(n-1>=DUMP_RANGE+K){
- dumpg(n-1, 0);
- }
- for(i=1;i<1<<K;++i){
- if(test_add(i)==0){
- memcpy(allg[curlevel+1],allg[curlevel],sizeof(allg[0]));
- for(j=0;j<K;j++){
- if(i&(1<<j)){
- ADDONEEDGE(allg[curlevel+1],K-1-j,n-1,1);
- }
- }
- dump_normalized(allg[curlevel+1],normg[curlevel+1],orbits,n);
- TGRAPH t(normg[curlevel+1]);
- if(usedg[curlevel].find(t)!=usedg[curlevel].end()){
- continue;
- }
- for(j=K;j<n-1;j++){
- if(orbits[j]==j && orbits[n-1]!=j){
- graph_remove_node(allg[curlevel+1], g, j, n);
- dump_normalized(g, ng, orbits2, n-1);
- int c=compg(ng, normg[curlevel]);
- if(c<0)break;
- }
- }
- if(j<n-1)continue;
- usedg[curlevel].insert(t);
- if(maxstep>0){
- if(allg[curlevel+1][K+nextstep]>>(64-K) != initvalue[nextstep]){
- continue;
- }
- }
- us[curlevel+1]=us[curlevel];
- curlevel++;
- do_add(i);
- if(nextstep+1==maxstep)maxstep=0;
- search(n+1, initvalue, nextstep+1, maxstep);
- pop();
- }
- }
- }
- int main(int argc, const char *argv[])
- {
- int i,j,n;
- int cc=argc-1;
- dtype initvalue[UB];
- for(i=1;i<argc;i++){
- char *endp=NULL;
- initvalue[i-1]=strtol(argv[i],&endp, 16);
- }
- int orbits[MAXN];
- if(cc>=1){
- dtype r=0;
- for(j=K-1;j>=0;j--){
- if((initvalue[0]&(1<<j))==0)break;
- r|=1<<j;
- }
- if(r!=initvalue[0]||r==0){
- fprintf(stderr,"Invalid start value\n");
- return -1;
- }
- if(cc==1)cc=0;
- }else{
- j=K-2;
- cc=0;
- }
- for(i=K-1-j;i<=HK;i++){
- fprintf(stderr, "searh for i=%d\n",i);
- dtype d=0;
- n=K+1;
- EMPTYGRAPH(allg[0],1,n);
- for(j=0;j<i;j++){
- ADDONEEDGE(allg[0], j, K, 1);
- }
- init();
- dump_normalized(allg[0], normg[0], orbits, n);
- d=allg[0][K]>>(64-K);
- do_add(d);
- search(n+1, initvalue, 1, cc);
- }
- return 0;
- }
|
|
楼主: mathe
IP卡
狗仔卡
显身卡
发表于 2018-3-17 08:10:40