帐号 自动登录 找回密码 密码 欢迎注册
 搜索

# [求助] 果树问题讨论:这两个问题等价么？

 Now let's summarize the progress on orchard planting problem with 4 trees per row. And the latest version of C++ code used to solve the problem is provided in the next two posts: 102# and 103# We know that optimal packing of \$K_4\$'s into a \$K_n\$ is an upbound for the orchard planting problem, and \$u(n)=[{[{n-1}/3]n}/4]\$ is upbound for both of the two problems. First, A C++ program is written to try to enumerate all non-equivalent method to packing at least u(n)-"MAX_FREEDOM" \$K_4\$ into \$K_n\$ in attachment file at 11#, the result for \$12<=n<=14\$ with MAX_FREEDOM=3 is first privided. Next in 33#, the result for n=11 with 6 rows is transformed into equations and WxMaxima used to solve the correspondent equations. We could find a solution for planting 6 rows with total 11 trees (4 trees per row) . Also WxMaxima helped to verify that for n=12, we could plant 6 rows of trees; but we could not plant 8 rows of trees. But WxMaxima complains that those equations for 7 rows are too complex so that it gives up. In 38# I found that if we project one row of trees into line at infinity (so that there'll be four infinity points and four groups of parallel straight lines in the result), it could greatly reduce the complexity of the equations. We could even manually solve all those equations for n=13 with at least 11 rows trees. With the help of WxMaxima, it is proved that we could plant at most 9 rows of trees (4 trees per row) when there're total 13 trees in 42# And at the sametime, we could find a solution to plant total 13 trees in 9 rows. (It is used to check the correctness of the C++ code used to find all method to packing \$K_4\$ into \$K_n\$ too). After projecting one rows of trees into infinity line and select another two lines as axises in the affine plane, the equations are 2 order multivariate polynomial (each variable is x or y coordinate of a tree) And we could know in advance that all of those variables are non-zero since the coordinate of all trees in X or Y axises is known in advance and they're not used as variables in the equations. So if we could find a linear combination of those equations and each non-zero term of the linear combination contains a given variable, we could divide the given variable from the linear combination to form a linear relationship among those variables. In 51# an algorithm is designed to use the idea to simplify/prove no solution/solve those nonlinear equations [But it may fail in some times]. and in 82# it is used to prove that we could plant at most 9 rows with 13 trees and at most 10 rows with 14 trees. And in 83# an example to plant10 rows with 14 trees is found by the program (used to verify correctness of the code). And in 84# it is proved that we could plant at most 12 rows with 15 trees. In 67# the C++ source code to enumerate all non-equivalent method to pack at leat u(n)-"MAX_FREEDOM" \$K_4\$ into \$K_n\$ is attached. A C++ template class node_edge_set is defined to generate a unique representation for a method to pack \$K_4\$ into \$K_n\$:     i)First we will classify all nodes in the graph into mulitiple groups according degrees of the node and attach all those nodes with the correspondent group id (in the ascedent order of degrees)     ii)We could classify all those \$K_4\$ in the graph according to the group id of nodes in the \$K_4\$ and sorting those groups by lexicographic ordering of group id's in the \$K_4\$     iii)We could classify all nodes in the graph by group id of \$K_4\$ using the node and sorting those gropus by lexicographic ordering of group id of \$K_4\$ too     iv) repeat step ii) and iii) until the number of groups remains unchanged.     v) If the multiple nodes are assign with same group id, select a group with mulitple nodes (heristic method to select the one with minimal group id)           for each node in the group, attach a special feature to the node(let the node uses a unique group id) and repeat step iii)-V) until each node is assigned with a unique group id.           For each choice of the node, we could result in a representation of the packing \$K_4\$ into \$K_n\$ configuration. (Each node is represented by the group id)           Select the one which is minimal in lexicographic ordering as the unique representation of the method to packing \$K_4\$ into \$K_n\$. The C++ program could search for the problem up to15 trees. But it will fail when there're more trees because a temp file generated by the program will be more than 2G. In 93# the program is improved so that it will use multiple files to keep those temp data. and in 96# the program is successfully generate all method to pack at least 16 \$K_4\$ into \$K_16\$. (And it will generate temp files up to 10G) and the C++ equation simplifer(the 2nd program) proved that none of them could form a correspondent solution to plant no less than 16 rows with 16 trees. So we have proved that we could plant at most 15 rows with 16 trees. According to the result in wolfram, we could result in that the 13 to 16 items of A006065 are 9,10,12,15. A bug in source found at Ot 23, 2008. After the bug fix, the new code verified that the items 13 to 16 remains unchanged. In 167#, a result of planting 15 trees in 12 rows provided. In 171#and 172#, 2 result of planting 16 trees in 15 rows provided. And the coordinates of another two solutions are provided. And all solutions for planting 16 treesin 15 rows are here if result under projection is treated as same result.

 The C++ source code to enumerate all non-equivalent method to packing at least u(n)-"MAX_FREEDOM" \$K_4\$ into \$K_n\$ Changing macro NUM_NODES to other value to search result for differrent 'n'. Make sure you have enough free hard disk space to run the code with larger n or MAX_FREEDOM. I have only tested the code with NODES_PER_EDGE equal to 4. #include #include #include #include #include #include #include #include #include #include using namespace std; template class node_edge_set{     public:         static const int max_edges_per_node = (TNODES-1)/(NODES_PER_EDGE-1);         static const int max_total_edges = (((TNODES-1)/(NODES_PER_EDGE-1))*TNODES)/NODES_PER_EDGE;         struct final_edge_set{             static int num_edges;             char edges[max_total_edges][NODES_PER_EDGE];             static void set_curr_num_edges(int n){num_edges=n;}             bool operator<(const final_edge_set& s)const{                 int i,j;                 for(i=0;is.edges[i][j])return false;                 }                 return false;             }             bool operator==(const final_edge_set& s)const{                 int i,j;                 for(i=0;in.tedges)return false;                 for(i=0;in.eids[i])return false;                 }                 return false;             }             bool operator==(const node_group_type& n)const{                 int i;                 if(tedgesn.tedges)return false;                 for(i=0;in.eids[i])return false;                 }                 return true;             }             void show()const{                 int i;                 printf("%d*{ ",group_counter);                 if(eids[0]==-1){                     printf("D=%d ",tedges);                 }else{                     for(i=0;ie.nids[i])return false;                 }                 return false;             }             bool operator==(const edge_group_type& e)const{                 int i;                 for(i=0;ie.nids[i])return false;                 }                 return true;             }             void show()const{                 int i;                 printf("%d*{ ",group_counter);                 for(i=0;inum_of_edges;i++){                         printf("%d ",edge_group_id[i]);                     }                     printf("}\n");                 }                 bool simple_case(int node_id)const{                      int i,j;                     if(node_edges->nodes_degree[node_id]==0)                         return true;                     if(node_edges->nodes_degree[node_id]>1)                         return false;                     int ngid=node_group_id[node_id];                     int e=node_edges->nodes_info[node_id][0];                     for(j=0;jedges_info[e][j];                         if(node_group_id[n]==ngid)continue;                         if(node_groups[node_group_id[n]].group_counter>1)                             break;                     }                     return j==NODES_PER_EDGE;                 }                 void show_nodes()const{                     int i;                     for(i=0;inum_of_edges;i++)edge_group_id[i]=g.edge_group_id[i];                 }                 int get_edge_groups_count()const{return edge_groups_count;}                 int get_node_groups_count()const{return node_groups_count;}                 int get_node_group_id(int nid)const{                     return node_group_id[nid];                 }                 int get_edge_group_id(int eid)const{                     return edge_group_id[eid];                 }                 int get_edge_group_counter(int gid)const{                     return edge_groups[gid].group_counter;                 }                 void assign_node_edge_id(char new_node_id[TNODES], int& next_node_id){                     int i;                     for(i=0;i0&&node_groups[i].group_counter>1){                             if(node_groups[i].group_counternum_of_edges;i++)edge_group_id[i]=tmp2[edge_group_id[i]];                 }                 void set_edge_group()///reset edge group according to node group                 {                     int i,j;                     edge_groups_count=0;                     for(i=0;inum_of_edges;i++){                         edge_group_type eg;                         for(j=0;jedges_info[i][j]];                         }                         sort(&eg.nids[0],&eg.nids[NODES_PER_EDGE]);                         for(j=0;jnodes_degree[i];                         for(j=0;jnodes_info[i][j]];                         }                         sort(&ng.eids[0],&ng.eids[ng.tedges]);                         for(j=0;jnodes_degree[i])                                 break;                         }                         if(jnodes_degree[i];                             node_groups[node_groups_count].eids[0]=-1;                             node_group_id[i]=node_groups_count++;                         }                     }                     int searched_groups=node_groups_count;                     for(;inodes_degree[i])                                 break;                         }                         if(jnodes_degree[i];                             node_groups[node_groups_count].eids[0]=-1;                             node_group_id[i]=node_groups_count++;                         }                     }                     sort_node_group(); #ifdef OUTPUT                     printf("Init node info:\n");                     show_nodes(); #endif                     int old_node_group;                     do{                         old_node_group=node_groups_count;                         set_edge_group(); #ifdef OUTPUT                         printf("edge info:\n");                         show_edges(); #endif                         set_node_group(); #ifdef OUTPUT                         printf("node info:\n");                         show_nodes(); #endif                     }while(node_groups_count!=old_node_group); #ifdef OUTPUT                     printf("end init\n"); #endif                 }                 bool unique_in_group(int nid){                     int group=node_group_id[nid];                     return (node_groups[group].group_counter==1);                 }                 void split_node(int nid){                     int old_group=node_group_id[nid];                     int i;                     node_groups[old_group].group_counter--;                     node_groups[node_groups_count].group_counter=1;                     node_groups[node_groups_count].tedges=node_groups[old_group].tedges;                     for(i=0;i0){                     ng.promote_searched(searched);                 }                 add_result(final_edges,ng);             }else{                 int i;                 for(i=0;i int node_edge_set::final_edge_set::num_edges; #if 0 #define NUM_EDGES 23 #define NUM_NODES 25 char init_value[NUM_EDGES][5]={     "BIFS","BOLG","BMPH","BQNJ","EBCD",     "AIET","EMOF","EQPS","EKNH","CKMA",     "CQOT","CNPG","CJHS","DQMI","DNOA",     "DPLF","DJGT","MRGS","NRFT","IORH",     "JPRA","AFGH","KQRL" }; char init_v2[NUM_EDGES][4]; typedef node_edge_set NESET; int main() {     int i,j;     for(i=0;i NESET; void reorder_node(int orig_node, int new_node) {     int i,j;     char tmp;     if(orig_node==new_node)return;     for(i=0;iused[step-1])             return;     }     if(last_line_count!=line_count){         changed=1;     }     last_line_count=line_count;     {         NESET nes(line_count, line_buf);         NESET::final_edge_set e=nes.normalize(step);         if(!changed&&e==last_e)             return;         last_e=e;         e.show(step);     } } void init() {     int i,j;     line_count=0;     for(i=0;i=1;i--){         if((MAX_EDGES_PER_NODE-i)*NUM_NODES>MAX_FREE_EDGES)             break;         for(j=0;j=cur_max_degree)return;     for(v=u+1;v=cur_max_degree)continue;         if(chessboard[u][v])continue;         for(w=v+1;w=cur_max_degree)continue;             if(chessboard[u][w]||chessboard[v][w])continue;             for(z=w+1;z=cur_max_degree)continue;                 if(chessboard[u][z]||chessboard[v][z]||chessboard[w][z])                     continue;                 setv(u,v,w,z);                 search(u);                 unsetv(u,v,w,z);             }         }     } } void process_one_line(int step, char *input) {     int i;     init();     for(i=0;;i++){         char c=input[i*4];         if(c>='A'&&c<='Z'){             setv(input[i*4]-'A',input[i*4+1]-'A',input[i*4+2]-'A',input[i*4+3]-'A');         }else{             break;         }     }     cur_free_edge=0;     cur_max_degree=0;     for(i=0;icur_max_degree)             return;     }     cur_free_edge = MAX_FREE_EDGES - cur_free_edge;     if(cur_free_edge<0){         fprintf(stderr,"Warning, invalid input\n");         return;     }     char group[NUM_NODES];     for(i=0;i0){             reorder_node(i,step-1);             search(step-1);             reorder_node(i,step-1);         }     } } void sort_step(int step) {     char tname[100];     char cmdline[200];     sprintf(tname,"data/t%d",step);     DIR *dirs=opendir(tname);     if(dirs==NULL){         fprintf(stderr,"Failed to open dir %s\n",tname);         return;     }     struct dirent *flist;     while(flist=readdir(dirs)){         if(flist->d_name[0]<'0'||flist->d_name[0]>'9')             continue;         sprintf(cmdline,"sort -u data/t%d/%s -o data/s%d/%s",step,flist->d_name, step, flist->d_name);         system(cmdline);     }     closedir(dirs);     sprintf(cmdline,"rm -rf data/t%d",step);     system(cmdline); } #define LINE_BUF_SIZE (MAX_TOTAL_EDGES*(NODES_PER_EDGE+1)+20) void create_step(int step) {     char sname[100];     char line[LINE_BUF_SIZE];     FILE *pRead, *pWrite;     sprintf(sname,"data/t%d",step);     mkdir(sname,-1);     sprintf(sname,"data/s%d",step);     mkdir(sname,-1);     sprintf(sname,"data/s%d",step-1);     DIR *dirs=opendir(sname);     if(dirs==NULL){         fprintf(stderr,"Failed to open dir %s\n",sname);         return;     }     struct dirent *flist;     while(flist=readdir(dirs)){         if(flist->d_name[0]<'0'||flist->d_name[0]>'9')             continue;         sprintf(sname,"data/s%d/%s",step-1,flist->d_name);         pRead=fopen(sname,"r");         if(pRead==NULL){             fprintf(stderr,"Cannot read input file %s\n",sname);             exit(-1);         }         while(fgets(line,LINE_BUF_SIZE,pRead)){             process_one_line(step,line);         }         fclose(pRead);     }     closedir(dirs);     sort_step(step); } int main(char argc, char *argv[]) {     int step=atoi(argv[1]);     if(step<1){         fprintf(stderr,"step should be no less than 1\n");         return -1;     }     if(step==1){         mkdir("data",-1);         create_step_one();     }else{         create_step(step);     }     return 0; } 复制代码 And a perl script is used to repeat the code by NUM_NODES times. Let's assuming that the binary file name is pm #!/usr/bin/perl \\$NUM_NODES=16 for(\\$i=1;\\$i<=\\$NUM_NODES;\\$i++){    system("./pm \\$i"); } system("cat data/s\\$NUM_NODES/* > data/output.all"); 复制代码 BUGS found on Sep 10,2008, #define MAX_FREE_EDGES   (MAX_FREEDOM*NODES_PER_EDGE) should be changed to #define MAX_FREE_EDGES   (MAX_FREEDOM*NODES_PER_EDGE+MAX_EDGES_PER_NODE*NUM_NODES-MAX_TOTAL_EDGES*NODES_PER_EDGE) and it is lucky that the two macro generate same values for n between 12 and 16

楼主| 发表于 2008-8-21 10:37:59 | 显示全部楼层
 mathe可以发表论文了

楼主| 发表于 2008-8-21 10:48:50 | 显示全部楼层
 为什么不允许游客访问呢，禁止他们回复和发帖还不行么

 原帖由 0→∞ 于 2008-8-21 10:48 发表 为什么不允许游客访问呢，禁止他们回复和发帖还不行么 游客，如果您要查看本帖隐藏内容请回复 发表论文我兴趣不大，比较花时间，网络上发表结果就可以了。

 不过现在都只是证明了一些人家找出来的结果已经是最优结果，没有找出更好的结果。如果能够对n=17找出16条直线或者n=20找出24条直线的，那就更加好了。 另外zgg和没一一问题有没有试一试用我那个解方程的程序过滤一下你们关于问题二找出来的一些候选解？

楼主| 发表于 2008-8-21 12:00:38 | 显示全部楼层
 关于问题2，能否算出在20点24线时共有多少种不同类的解？

 连存在都不能证明 不可能给出20点4点共线的24直线解的数量的

 他说的是问题2的数量。这个关于17点不少于17条边情况的求解在我的计算机上产生几十G数据以后好像让我的Linux机器崩溃了，现在我不能远程登录了

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖后跳转到最后一页

GMT+8, 2021-7-29 17:57 , Processed in 0.068369 second(s), 15 queries .