football.w

模拟器提供了一个简单易用的平台

    if (a->tip->blocked==0 && a->tip->valid!=v) {
      a->tip->valid=v; /* mark |a->tip| reachable from |goal| */
      a->tip->link=u;
      u=a->tip; /* push it on the stack, so that its successors
                   will be marked too */
    }
}@+while (u);

@*Stratified greed.  One approach to better chains is the following
algorithm, motivated by similar ideas of Pang Chen [Ph.D. thesis,
Stanford University, 1989]: @^Chen, Pang-Chieh@> Suppose the nodes of
a (possibly huge) backtrack tree are classified into a (fairly small)
number of strata, by a function $h$ with the property that $h({\rm
child})<h({\rm parent})$ and $h({\rm goal})=0$. Suppose further that
we want to find a node $x$ that maximizes a given function~$f(x)$,
where it is reasonable to believe that $f$(child) will be relatively
large among nodes in a child's stratum only if $f$(parent) is
relatively large in the parent's stratum. Then it makes sense to
restrict backtracking to, say, the top $w$ nodes of each stratum,
ranked by their $f$ values.

The greedy algorithm already described is a special case of this general
approach, with $w=1$ and with $h(x)=-($length of chain leading to~$x)$.
The refined algorithm we are about to describe uses a general value of $w$
and a somewhat more relevant stratification function: Given a node~$x$
of the backtrack tree for longest paths, corresponding to a path from
|start| to a certain vertex~$u=u(x)$, we will let $h(x)$ be the number of
vertices that lie between |u| and |goal| (in the sense that the simple
path from |start| to~|u| can be extended until it passes through such
a vertex and then all the way to~|goal|).

Here is the top level of the stratified greedy algorithm. We maintain
a linked list of nodes for each stratum, that is, for each possible value
of~$h$. The number of nodes required is bounded by $w$ times the
number of strata.

@<Use a strat...@>=
{
  @<Make |list[0]| through |list[n-1]| empty@>;
  cur_node=NULL; /* |NULL| represents the root of the backtrack tree */
  m=g->n-1; /* the highest stratum not yet fully explored */
  do@+{
    @<Place each child~|x| of |cur_node| into |list[h(x)]|, retaining
      at most |width| nodes of maximum |tot_len| on each list@>;
    while (list[m]==NULL)
      @<Decrease |m| and get ready to explore another list@>;
    cur_node=list[m];
    list[m]=cur_node->next; /* remove a node from highest remaining stratum */
    if (verbose) @<Print ``verbose'' info about |cur_node|@>;
  }@+while (m>0); /* exactly one node should be in |list[0]| (see below) */
}

@ The calculation of $h(x)$ is somewhat delicate, and we will defer it
for a moment. But the list manipulation is easy, so we can finish it
quickly while it's fresh in our minds.

@d MAX_N 120 /* the number of teams in \.{games.dat} */

@<Glob...@>=
node *list[MAX_N]; /* the best nodes known in given strata */
long size[MAX_N]; /* the number of elements in a given |list| */
long m,h; /* current lists of interest */
node *x; /* a child of |cur_node| */

@ @<Make |list[0]|...@>=
for (m=0;m<g->n;m++) list[m]=NULL,size[m]=0;

@ The lists are maintained in order by |tot_len|, with the largest
|tot_len| value at the end so that we can easily delete the smallest.

When |h=0|, we retain only one node instead of~|width| different nodes,
because we are interested in only one solution.

@<Place node~|x| into |list[h]|, retaining
    at most |width| nodes of maximum |tot_len|@>=
if ((h>0 && size[h]==width) || (h==0 && size[0]>0)) {
  if (x->tot_len<=list[h]->tot_len) goto done; /* drop node |x| */
  list[h]=list[h]->next; /* drop one node from |list[h]| */
}@+else size[h]++;
{@+register node *p,*q; /* node in list and its predecessor */
  for (p=list[h],q=NULL; p; q=p,p=p->next)@+
    if (x->tot_len<=p->tot_len) break;
  x->next=p;
  if (q) q->next=x;@+ else list[h]=x;
}
done:;

@ We reverse the list so that large entries will tend to go in first.

@<Decrease |m| and get ready to explore another list@>=
{@+register node *r=NULL, *s=list[--m], *t;
  while (s) t=s->next, s->next=r, r=s, s=t;
  list[m]=r;
  mm=0; /* |mm| is an index for ``verbose'' printing */
}

@ @<Print ``verbose'' info...@>=
{
  cur_node->next=(node*)((++mm<<8)+m); /* pack an ID for this node */
  printf("[%lu,%lu]=[%lu,%lu]&%s (%+ld)\n",m,mm,@|
    cur_node->prev?((unsigned long)cur_node->prev->next)&0xff:0L,@|
    cur_node->prev?((unsigned long)cur_node->prev->next)>>8:0L,@|
    cur_node->game->tip->name, cur_node->tot_len);
}

@ Incidentally, it is plausible to conjecture that the stratified algorithm
always beats the simple greedy algorithm, but that conjecture is false.
For example, the greedy algorithm is able to rank Harvard over Stanford
by 1529, while the stratified algorithm achieves only 1527 when
|width=1|. On the other hand, the greedy algorithm often fails
miserably; when comparing two Ivy League teams, it doesn't find a
way to break out of the Ivy and Patriot Leagues.

@*Bicomponents revisited.
How difficult is it to compute the function $h$? Given a connected graph~$G$
with two distinguished vertices $u$ and~$v$, we want to count the number
of vertices that might appear on a simple path from $u$ to~$v$.
(This is {\sl not\/} the same as the number of vertices reachable from both
$u$ and~$v$. For example, consider a ``claw'' graph with four vertices
$\{u,v,w,x\}$ and with edges only from $x$ to the other three vertices;
in this graph $w$ is reachable from $u$ and~$v$, but it is not on any simple
path between them.)

The best way to solve this problem is probably to compute the bicomponents
of~$G$, or least to compute some of them. Another demo program,
{\sc BOOK\_\kern.05emCOMPONENTS}, explains the relevant theory in some
detail, and we will assume familiarity with that algorithm in the present
discussion.

Let us imagine extending $G$ to a slightly larger graph $G^+$ by
adding a dummy vertex~$o$ that is adjacent only to $v$. Suppose we determine
the bicomponents of $G^+$ by depth-first search starting at~$o$.
These bicomponents form a tree rooted at the bicomponent that contains
just $o$ and~$v$. The number of vertices on paths between $u$ and~$v$,
not counting $v$ itself, is then the number of vertices in the bicomponent
containing~$u$ and in any other bicomponents between that one and the root.

Strictly speaking, each articulation point belongs
to two or more bicomponents. But we will assign each articulation point
to its bicomponent that is nearest the root of the tree; then the vertices
of each bicomponent are precisely the vertices output in bursts by the
depth-first procedure. The bicomponents we want to enumerate are $B_1$, $B_2$,
\dots,~$B_k$, where $B_1$ is the bicomponent containing~$u$ and
$B_{j+1}$ is the bicomponent containing the articulation point associated
with~$B_j$; we stop at~$B_k$ when its associated articulation point is~$v$.
(Often $k=1$.)

The ``children'' of a given graph~$G$ are obtained by removing vertex~$u$
and by considering paths from $u'$ to~$v$, where $u'$ is a vertex
formerly adjacent to~$u$; thus $u'$ is either in~$B_1$ or it is $B_1$'s
associated articulation point. Removing $u$ will, in general, split
$B_1$ into a tree of smaller bicomponents, but $B_2,\ldots,B_k$ will be
unaffected. The implementation below does not take full advantage of this
observation, because the amount of memory required to avoid recomputation
would probably be prohibitive.

@ The following program is copied almost verbatim from
{\sc BOOK\_\kern.05emCOMPONENTS}.
Instead of repeating the commentary that appears there, we will mention
only the significant differences. One difference is that we start
the depth-first search at a definite place, the |goal|.

@<Place each child~|x| of |cur_node| into |list[h(x)]|, retaining
    at most |width| nodes of maximum |tot_len| on each list@>=
@<Make all vertices unseen and all arcs untagged, except for vertices
  that have already been used in steps leading up to |cur_node|@>;
@<Perform a depth-first search with |goal| as the root, finding
  bicomponents and determining the number of vertices accessible
  between any given vertex and |goal|@>;
for (a=(cur_node? cur_node->game->tip: start)->arcs; a; a=a->next)
  if ((u=a->tip)->untagged==NULL) { /* |goal| is reachable from |u| */
    x=new_node(cur_node,a->del);
    if (x==NULL) {
      fprintf(stderr,"Oops, there isn't enough memory!\n");@+return -3;
    }
    x->game=a;
    @<Set |h| to the number of vertices on paths between |u| and |goal|@>;
    @<Place node...@>;
  }

@ Setting the |rank| field of a vertex to infinity before beginning
a depth-first search is tantamount to removing that vertex from
the graph, because it tells the algorithm not to look further at
such a vertex.

@d rank z.I /* when was this vertex first seen? */
@d parent u.V /* who told me about this vertex? */
@d untagged x.A /* what is its first untagged arc? */
@d min v.V /* how low in the tree can we jump from its mature descendants? */

@<Make all vertices unseen and all arcs untagged, except for vertices
  that have already been used in steps leading up to |cur_node|@>=
for (v=g->vertices; v<g->vertices+g->n; v++) {
  v->rank=0;
  v->untagged=v->arcs;
}
for (x=cur_node;x;x=x->prev)
  x->game->tip->rank=g->n; /* ``infinite'' rank (or close enough) */
start->rank=g->n;
nn=0;
active_stack=settled_stack=NULL;

@ @<Glob...@>=
Vertex * active_stack; /* the top of the stack of active vertices */
Vertex *settled_stack; /* the top of the stack of bicomponents found */
long nn; /* the number of vertices that have been seen */
Vertex dummy; /* imaginary parent of |goal|; its |rank| is zero */

@ The |settled_stack| will contain a list of all bicomponents in
the opposite order from which they are discovered. This is the order
we'll need later for computing the |h| function in each bicomponent.

@<Perform a depth-first search...@>=
{
  v=goal;
  v->parent=&dummy;
  @<Make vertex |v| active@>;
  do @<Explore one step from the current vertex~|v|, possibly moving
        to another current vertex and calling~it~|v|@>@;
  while (v!=&dummy);
  @<Use |settled_stack| to put the mutual reachability count for
     each vertex |u| in |u->parent->rank|@>;
}

@ @<Make vertex |v| active@>=
v->rank=++nn;
v->link=active_stack;
active_stack=v;
v->min=v->parent;

@ @<Explore one step from the current vertex~|v|, possibly moving
        to another current vertex and calling~it~|v|@>=
{@+register Vertex *u; /* a vertex adjacent to |v| */
  register Arc *a=v->untagged; /* |v|'s first remaining untagged arc, if any */
  if (a) {
    u=a->tip;
    v->untagged = a->next; /* tag the arc from |v| to |u| */
    if (u->rank) { /* we've seen |u| already */
      if (u->rank < v->min->rank)
        v->min=u; /* non-tree arc, just update |v->min| */
    }@+else { /* |u| is presently unseen */
      u->parent = v; /* the arc from |v| to |u| is a new tree arc */
      v = u; /* |u| will now be the current vertex */
      @<Make vertex |v| active@>;
    }
  }@+else { /* all arcs from |v| are tagged, so |v| matures */
    u=v->parent; /* prepare to backtrack in the tree */
    if (v->min==u) @<Remove |v| and all its successors on the active stack
         from the tree, and report them as a bicomponent of the graph
         together with~|u|@>@;
    else  /* the arc from |u| to |v| has just matured,
             making |v->min| visible from |u| */@,
      if (v->min->rank < u->min->rank)
        u->min=v->min;
    v=u; /* the former parent of |v| is the new current vertex |v| */
  }
}

@ When a bicomponent is found, we reset the |parent| field of each vertex
so that, afterwards, two vertices will belong to the same bicomponent
if and only if they have the same |parent|. (This trick was not used in
{\sc BOOK\_\kern.05emCOMPONENTS}, but it does appear in the similar algorithm
of {\sc ROGET\_\,COMPONENTS}.) The new parent, |v|, will represent that
bicomponent in subsequent computation; we put it onto |settled_stack|.
We also reset |v->rank| to be the bicomponent's size, plus a constant
large enough to keep the algorithm from getting confused. (Vertex~|u|
might still have untagged arcs leading into this bicomponent; we need to
keep the ranks at least as big as the rank of |u->min|.) Notice that
|v->min| is |u|, the articulation point associated with this bicomponent.
Later the |rank| field will
contain the sum of all counts between here and the root.

We don't have to do anything when |v==goal|; the trivial root bicomponent
always comes out last.

@<Remove |v| and all its successors on the active stack...@>=
{@+if (v!=goal) {@+register Vertex *t; /* runs through the vertices of the
                          new bicomponent */
    long c=0; /* the number of vertices removed */
    t=active_stack;
    while (t!=v) {
      c++;
      t->parent=v;
      t=t->link;
    }
    active_stack=v->link;
    v->parent=v;
    v->rank=c+g->n; /* the true component size is |c+1| */
    v->link=settled_stack;
    settled_stack=v;
  }
}

@ So here's how we sum the ranks. When we get to this step, the \\{settled}
stack contains all bicomponent representatives except |goal| itself.

@<Use |settled_stack| to put the mutual reachability count for
     each vertex |u| in |u->parent->rank|@>=
while (settled_stack) {
  v=settled_stack;
  settled_stack=v->link;
  v->rank+=v->min->parent->rank+1-g->n;
} /* note that |goal->parent->rank=0| */

@ And here's the last piece of the puzzle.

@<Set |h| to the number of vertices on paths between |u| and |goal|@>=
h=u->parent->rank;

@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.