@x
@ After this program finds all solutions, it normally prints their total
@y
This version of {\mc XCCDC} uses a dynamic weighting scheme, inspired by
the paper of Boussemart, Hemery, Lecoutre, and Sais in {\sl Proc.\ 16th
European Conference on Artificial Intelligence} (2004), 146--150: We increase
the weight of a primary item when its current set of options becomes null.
Items are chosen for branching based on the size of their set divided by their
current weight, unless the choice is forced.
@^Boussemart, Fr\'ed\'eric@>
@^H\'emery, Fred@>
@^Lecoutre, Christophe@>
@^Sa{\"\i}s, Lakhdar@>
@ After this program finds all solutions, it normally prints their total
@z
@x
@d show_max_deg 2048 /* |vbose| code for reporting maximum branching degree */
@y
@d show_max_deg 2048 /* |vbose| code for reporting maximum branching degree */
@d show_final_weights 4096 /* |vbose| code to display weights at the end */
@d show_weight_bumps 8192 /* |vbose| code to show new weights */
@z
@x
if (vbose&show_profile) @<print the profile@>;
@y
if (vbose&show_profile) @<print the profile@>;
if (vbose&show_final_weights) {
 fprintf(stderr,"Final weights:\n");
 print_weights();
}
@z
@x
(The &#124;match&#124; field is present only in secondary items.)
@y
(The &#124;match&#124; field is present only in secondary items.)
Finally, the &#124;set&#124; array contains a &#124;wt&#124; field for each primary item;
&#124;wt(x)&#124; occupies the position of &#124;match(x)&#124; in a secondary item.
This weight, initially~1, is increased by 1 whenever we run into a
situation where &#124;x&#124; cannot be supported.
@z
@x
@d match(x) set[(x)-6] /* a required color in compatibility tests */
@d primextra 5 /* this many extra entries of &#124;set&#124; for each primary item */
@y
@d match(x) set[(x)-6] /* a required color in compatibility tests */
@d wt(x) set[(x)-6] /* the current weight of item &#124;x&#124; */
@d primextra 6 /* this many extra entries of &#124;set&#124; for each primary item */
@z
@x
 if (c<second) fprintf(stderr," ("O"d of "O"d), length "O"d:\n", pos(c)+1,active,size(c)); @y if (c<second) fprintf(stderr," ("O"d of "O"d), weight "O"d, length "O"d:\n", pos(c)+1,active,wt(c),size(c)); @z @x o,mark(j)=0; @y o,mark(j)=0; if (k<=osecond) o,wt(j)=1;@+else o,match(j)=0; @z @x fprintf(stderr," can't cover"); print_item_name(ii,stderr); fprintf(stderr,"\n"); } @<clear the queue and &#124;return 0&#124;@>;
@y
 if (!(vbose&show_weight_bumps)) {
 fprintf(stderr," can't cover");
 print_item_name(ii,stderr);
 fprintf(stderr,"\n");
 }
 }
 tough_itm=ii;
 @<clear the queue and &#124;return 0&#124;@>;
@z
@x
 if (!include_option(cur_choice)) {
 nmems+=mems-tmems;
 goto tryagain;
 }
 if (!empty_the_queue()) {
 nmems+=mems-tmems;
 goto tryagain;
 }
@y
 if (!include_option(cur_choice)) {
 nmems+=mems-tmems;
 @<increase the weight of &#124;tough_itm&#124;@>;
 goto tryagain;
 }
 if (!empty_the_queue()) {
 nmems+=mems-tmems;
 @<increase the weight of &#124;tough_itm&#124;@>;
 goto tryagain;
 }
@z
@x
 if (!(o,purge_the_option(choice[level],active,"removing"))) {
 pmems+=mems-tmems;
 goto backup;
 }
 if (!empty_the_queue()) {
 pmems+=mems-tmems;
 goto backup;
 }
@y
 if (!(o,purge_the_option(choice[level],active,"removing"))) {
 pmems+=mems-tmems;
 @<increase the weight of &#124;tough_itm&#124;@>;
 goto backup;
 }
 if (!empty_the_queue()) {
 pmems+=mems-tmems;
 @<increase the weight of &#124;tough_itm&#124;@>;
 goto backup;
 }
@z
@x
int saveptr; /* current size of &#124;savestack&#124; */
@y
int saveptr; /* current size of &#124;savestack&#124; */
int tough_itm; /* an item that led to difficulty */
@z
@x
@ The ``best item'' is considered to be an item that minimizes the
number of remaining choices. If there are several candidates, we
choose the first one that we encounter.
Each primary item should have at least one valid choice, because
of domain consistency.
@d infty 0x7fffffff
@<set &#124;best_itm&#124; to the best item for branching...@>=
t=infty;
if ((vbose&show_details) &&
 level<show_choices_max && level>=maxl-show_choices_gap)
 fprintf(stderr,"Stage "O"d,",stage);
for (k=0;t>1 && 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<=t) { if (s==0) fprintf(stderr,"I'm confused.\n"); /* &#124;hide&#124; missed this */ if (s<t) best_itm=item[k],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) {
 if (t==infty) fprintf(stderr," solution\n");
 else {
 fprintf(stderr," branching on");
 print_item_name(best_itm,stderr);
 fprintf(stderr,"("O"d)\n",t);
 }
}
if (t>maxdeg && t<infty) maxdeg=t; @y @ @<increase the weight of &#124;tough_itm&#124;@>=
bmems+=2,oo,wt(tough_itm)++;
if (wt(tough_itm)<=0) { fprintf(stderr,"Weight overflow (2^31)!\n"); exit(-6); } if (vbose&show_weight_bumps) { print_item_name(tough_itm,stderr); fprintf(stderr," wt "O"d\n",wt(tough_itm)); } @ @<sub...@>=
void print_weights(void) {
 register int k;
 for (k=0;k<itemlength;k++) if (item[k]<second && wt(item[k])!=1) { print_item_name(item[k],stderr); fprintf(stderr," wt "O"d\n",wt(item[k])); } } @ The ``best item'' is considered to be an item that minimizes the number of remaining choices, divided by the item's weight. If there are several candidates with the same minimum, we choose the first one that we encounter. Each primary item should have at least one valid choice, because of domain consistency. When an item has at most one option left, we consider it to be forced (regardless of any weights). In other words, an item with one option and small weight is preferred to an item with two options and huge weight. @d dangerous 1e32f @d infty 0x7fffffff @d finfty 2e32f /* twice &#124;dangerous&#124; */ @<set &#124;best_itm&#124; to the best item for branching...@>=
{
 register float score,tscore,w;
 register int force;
 score=finfty,t=infty;
 if ((vbose&show_details) &&
 level<show_choices_max && level>=maxl-show_choices_gap)
 fprintf(stderr,"Level "O"d:",level);
 for (k=0;t>1 && 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 */ t=1,best_itm=item[k]; }@+else { o,w=wt(item[k]); tscore=s/w; if (tscore>=finfty) tscore=dangerous;
 if (tscore<score) best_itm=item[k],score=tscore,t=s; } if ((vbose&show_details) && level<show_choices_max && level>=maxl-show_choices_gap) {
 print_item_name(item[k],stderr);@+
 if (t==1) fprintf(stderr,"(1)");
 else fprintf(stderr,"("O"d,"O"d)",s,wt(item[k]));
 }
 }
 if ((vbose&show_details) &&
 level<show_choices_max && level>=maxl-show_choices_gap) {
 if (t==infty) fprintf(stderr," solution\n");
 else {
 fprintf(stderr," branching on");
 print_item_name(best_itm,stderr);@+
 if (t==1) fprintf(stderr,"(forced)\n");
 else fprintf(stderr,"("O"d), score "O".4f\n",t,score);
 }
 }
 if (t>maxdeg && t<infty) maxdeg=t;
}
@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/xccdc-wtd.ch">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://cs.stanford.edu/~knuth/programs/xccdc-wtd.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>