@x an experimental change file for SSXCC-BINARY (the new version of 25 Aug!)
those heuristics were designed with binary branching in mind.
@y
those heuristics were designed with binary branching in mind.
The ``{\mc FRB} heuristic'' implemented here is motivated by the paper
of Li, Yin, and Li in
@^Li, Hongbo@>
@^Yin, Minghao@>
@^Li, Zhanshan@>
{\sl Leibniz International Proceedings in Informatics\/ \bf210}
(2021), 9:1--9:10
[the proceedings of the 27th International Conference on Principles and
Practice of Constraint Programming, CP~2021].
When the option chosen for branching on some primary item~$i$ causes
another primary item~$i'$ to be wiped out, we say that a failure has
occurred with respect to~$i$. We branch on an item
that has a small number of options and a relatively high failure rate.
Details are discussed below.
@z
@x
@d show_weight_bumps 32 /* |vbose| code to show new weights */
@d show_final_weights 64 /* |vbose| code to display weights at the end */
@y
@d show_final_stats 64 /* |vbose| code to display item stats at the end */
@z
@x
 if (vbose&show_final_weights) {
 fprintf(stderr,"Final weights:\n");
 print_weights();
 }
@y
 if (vbose&show_final_stats) {
 fprintf(stderr,"Final primary item stats:\n");
 print_item_stats();
 }
@z
@x
`\.w$\langle,円$float$,円\rangle$' is the initial increment |dw| added to
an item's weight (default 1.0);
\item{$\bullet$}
`\.W$\langle,円$float$,円\rangle$' is the factor by which |dw| changes
dynamically (default 1.0);
@y
@z
@x
case 'w': k|=(sscanf(argv[j]+1,""O"f",&dw)-1);@+break;
case 'W': k|=(sscanf(argv[j]+1,""O"f",&dwfactor)-1);@+break;
@y
@z
@x
 " [c<n>] [C<n>] [l<n>] [t<n>] [T<n>] [w<f>] [W<f>] [S<bar>] < foo.dlx\n", @y " [c<n>] [C<n>] [l<n>] [t<n>] [T<n>] [S<bar>] < foo.dlx\n", @z @x A primary item $x$ also has a &#124;wt&#124; field, &#124;set[x-5]&#124;, initially~1. The weight is increased by &#124;dw&#124; whenever we backtrack because &#124;x&#124; cannot be covered. (Weights aren't actually {\it used} in the present program; that will come in extensions to be written later. But it will be convenient to have space ready for them in our data structures, so that those extensions will be easy to write.) @y A primary item $x$ also has two special fields called &#124;assigns&#124; and &#124;failrate&#124;, used in the {\mc FRB} heuristic. Their significance is described below. @z @x @d wt(x) set[(x)-5].f /* the current floating-point ``weight'' of &#124;x&#124; */ @d primextra 5 /* this many extra entries of &#124;set&#124; for each primary item */ @d secondextra 4 /* and this many for each secondary item */ @d maxextra 5 /* maximum of &#124;primextra&#124; and &#124;secondextra&#124; */ @y @d assigns(x) set[(x)-5].f /* number of assignments tried so far for &#124;x&#124; */ @d failrate(x) set[(x)-6].f /* the current ``failure rate'' of &#124;x&#124; */ @d primextra 6 /* this many extra entries of &#124;set&#124; for each primary item */ @d secondextra 4 /* and this many for each secondary item */ @d maxextra 6 /* maximum of &#124;primextra&#124; and &#124;secondextra&#124; */ @z @x fprintf(stderr," ("O"d of "O"d), length "O"d, weight "O".1f:\n", pos(c)+1,active,size(c),wt(c)); @y fprintf(stderr, " ("O"d of "O"d), length "O"d, failrate "O".1f of "O"g:\n", pos(c)+1,active,size(c),failrate(c),assigns(c)); @z @x if (k<=osecond) o,wt(j)=w0; @y if (k<=osecond) oo,assigns(j)=1.0,failrate(j)=0.5; @z @x if (!include_option(cur_choice)) goto tryagain; @<increase &#124;stage&#124;@>;@+@<increase &#124;level&#124;@>;
 goto forward;
@y
 if (!include_option(cur_choice)) goto abort;
 @<take account of a nonfailure for &#124;best_itm&#124;@>;
 @<increase &#124;stage&#124;@>;@+@<increase &#124;level&#124;@>;
 goto forward;
abort:@+@<take account of a failure for &#124;best_itm&#124;@>;
@z
@x
@ If a weight becomes dangerously large, we rescale all the weights.
(That will happen only when &#124;dwfactor&#124; isn't 1.0. Adding a constant
eventually ``converges'': For example, if the constant is 1, we have convergence
to 2ドル^{17}$ after 2ドル^{17}-1=16777215$ steps.
If the constant~&#124;dw&#124; is .250001, convergence
to \.{8.38861e+06} occurs after 25165819 steps!)
(Note: I threw in the parameters &#124;dw&#124; and &#124;dwfactor&#124; only to do experiments.
My preliminary experiments didn't turn up any noteworthy results.
But I didn't have time to do a careful study; hence there might
be some settings that work unexpectedly well. The code for rescaling
might be flaky, since it hasn't been tested very thoroughly at all.)
@d dangerous 1e32f
@d wmin 1e-30f
@<increase the weight of &#124;tough_itm&#124;@>=
cmems+=2,oo,wt(tough_itm)+=dw;
if (vbose&show_record_weights && wt(tough_itm)>maxwt) {
 maxwt=wt(tough_itm);
 fprintf(stderr,""O"8.1f ",maxwt);
 print_item_name(tough_itm,stderr);
 fprintf(stderr," "O"lld\n",nodes);
}
if (vbose&show_weight_bumps) {
 print_item_name(tough_itm,stderr);
 fprintf(stderr," wt "O".1f\n",wt(tough_itm));
}
dw*=dwfactor;
if (wt(tough_itm)>=dangerous) {
 register int k;
 register float t;
 tmems=mems;
 for (k=0;k<itemlength;k++) if (o,item[k]<second) { o,t=wt(item[k])*1e-20f; o,wt(item[k])=(t<wmin?wmin:t); } dw*=1e-20f; if (dw<wmin) dw=wmin; w0*=1e-20f; if (w0<wmin) w0=wmin; cmems+=mems-tmems; } @ @<maybe do a forced move@>=
while (forced) {
 o,best_itm=force[--forced];
 if (o,pos(best_itm)<active) { @<do a forced move and &#124;goto advance&#124;@>;
 }
}
@ @<sub...@>=
void print_weights(void) {
 register int k;
 for (k=0;k<itemlength;k++) if (item[k]<second && wt(item[k])!=w0) { print_item_name(item[k],stderr); fprintf(stderr," wt "O".1f\n",wt(item[k])); } } @y @ The heuristics used in this program are based on the special fields &#124;assigns&#124; and &#124;failrate&#124; of each primary item~&#124;i&#124;. The &#124;assigns&#124; field simply counts the number of assignments made to~&#124;i&#124; so far, namely the number of times we've branched on~&#124;i&#124; by trying to include one of its options. It's a \&{float}, so it starts at 1.0 and increases to 2ドル^{24}=16777216.0,ドル after which it remains constant. An assignment {\it fails\/} if it wipes out the options for some other primary variable that it doesn't cover. The &#124;failrate&#124; field is the most interesting. It basically represents the number of failed assignments to~&#124;i&#124; divided by &#124;assigns(i)&#124;. However, &#124;failrate(i)&#124; is initialized to 0.5, and &#124;assigns(i)&#124; is initialized to 1.0, according to the definition introduced by Li, Yin, and Li in their paper cited above. @^Li, Hongbo@>
@^Yin, Minghao@>
@^Li, Zhanshan@>
After the first assignment, &#124;assigns(i)&#124; will be~2.0, and
&#124;failrate(i)&#124; will be either 0.75 or 0.25, depending on whether
or not that assignment led to failure. After $k$ assignments,
the possible values of &#124;failrate(i)&#124; are 1ドル/(2k+2),ドル
3ドル/(2k+2),ドル \dots,~$(2k+1)/(2k+2)$.
@<take account of a nonfailure for &#124;best_itm&#124;@>=
oo,assigns(best_itm)+=1.0;
oo,failrate(best_itm)-=failrate(best_itm)/assigns(best_itm);
@ @<take account of a failure for &#124;best_itm&#124;@>=
oo,assigns(best_itm)+=1.0;
oo,failrate(best_itm)+=(1.0-failrate(best_itm))/assigns(best_itm);
@ @<maybe do a forced move@>=
while (forced) {
 o,best_itm=force[--forced];
 if (o,pos(best_itm)<active) { @<do a forced move and &#124;goto advance&#124;@>;
 }
}
@ @<sub...@>=
void print_item_stats(void) {
 register int k;
 for (k=0;k<itemlength;k++) if (item[k]<second && assigns(item[k])!=1.0) { print_item_name(item[k],stderr); fprintf(stderr," fr "O".4f of "O"g\n", failrate(item[k]),assigns(item[k])); } } @z @x @d inf_size 0x7fffffff @<set &#124;best_itm&#124; to the best item for branching...@>=
{
 t=inf_size,tmems=mems;
@y
@d inf_size 0x7fffffff
@d dangerous 1e32f
@d infty 2e32f /* twice &#124;dangerous&#124; */
@<set &#124;best_itm&#124; to the best item for branching...@>=
{
 register float score,tscore,w;
 t=inf_size,tmems=mems,score=infty;
@z
@x
 for (k=0;k<active;k++) if (o,item[k]<second) { o,s=size(item[k]); if ((vbose&show_details) && level<show_choices_max && level>=maxl-show_choices_gap) {
 print_item_name(item[k],stderr);
 fprintf(stderr,"("O"d)",s);
 }
 if (s<=1) { if (s==0) fprintf(stderr,"I'm confused.\n"); /* &#124;include_option&#124; missed this */ else o,force[forced++]=item[k]; }@+else if (s<=t) { if (s<t) best_itm=item[k],t=s; else if (item[k]<best_itm) best_itm=item[k]; /* suggested by P. Weigel */ } } @y for (k=0;k<active;k++) if (o,item[k]<second) { o,s=size(item[k]); if (s<=1) { if (s==0) fprintf(stderr,"I'm confused.\n"); /* &#124;include_option&#124; missed this */ else o,force[forced++]=item[k]; }@+else { o,w=failrate(item[k]); tscore=s/w; if (tscore>=infty) tscore=dangerous;
 if (tscore<=score) { if (tscore<score) best_itm=item[k],score=tscore,t=s; else if (item[k]<best_itm) best_itm=item[k]; } } if ((vbose&show_details) && level<show_choices_max && level>=maxl-show_choices_gap) {
 print_item_name(item[k],stderr);@+
 if (s==1) fprintf(stderr,"(1)");
 else fprintf(stderr,"("O"d,"O".1f)",s,w);
 }
 }
@z
@x
 fprintf(stderr,"("O"d)\n",t);
@y
 fprintf(stderr,"("O"d), score "O".4f\n",t,score);
@z
</div><div class="naked_ctrl">
<form action="/index.cgi/speech" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://cs.stanford.edu/~knuth/programs/ssxcc-frb.ch">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://cs.stanford.edu/~knuth/programs/ssxcc-frb.ch" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech" selected="selected">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>