football.w

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

% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

\def\title{FOOTBALL}

\prerequisite{GB\_\,GAMES}
@* Introduction. This demonstration program uses graphs
constructed by the {\sc GB\_\,GAMES} module to produce
an interactive program called \.{football}, which finds preposterously
long chains of scores to ``prove'' that one given team might outrank another
by a huge margin.

\def\<#1>{$\langle${\rm#1}$\rangle$}
The program prompts you for a starting team. If you simply type \<return>,
it exits; otherwise you should enter a team name (e.g., `\.{Stanford}')
before typing \<return>.

Then the program prompts you for another team. If you simply type
\<return> at this point, it will go back and ask for a new starting team;
otherwise you should specify another name (e.g., `\.{Harvard}').

Then the program finds and displays a chain from the starting team
to the other one. For example, you might see the following:
$$\vbox{\halign{\tt#\hfil\cr
 Oct 06: Stanford Cardinal 36, Notre Dame Fighting Irish 31 (+5)\cr
 Oct 20: Notre Dame Fighting Irish 29, Miami Hurricanes 20 (+14)\cr
 Jan 01: Miami Hurricanes 46, Texas Longhorns 3 (+57)\cr
 Nov 03: Texas Longhorns 41, Texas Tech Red Raiders 22 (+76)\cr
 Nov 17: Texas Tech Red Raiders 62, Southern Methodist Mustangs 7 (+131)\cr
 Sep 08: Southern Methodist Mustangs 44, Vanderbilt Commodores 7 (+168)\cr
\omit\qquad\vdots\cr
 Nov 10: Cornell Big Red 41, Columbia Lions 0 (+2188)\cr
 Sep 15: Columbia Lions 6, Harvard Crimson 9 (+2185)\cr}}$$
The chain isn't necessarily optimal; it's just this particular
program's best guess. Another chain, which establishes a victory margin
of $+2279$ points, can in fact be produced by modifying this
program to search back from Harvard instead of forward from Stanford.
Algorithms that find even better chains should be fun to invent.

Actually this program has two variants. If you invoke it by saying simply
`\.{football}', you get chains found by a simple ``greedy algorithm.''
But if you invoke it by saying `\.{football} \<number>', assuming \UNIX/
command-line conventions, the program works harder. Higher values of
\<number> do more calculation and tend to find better chains. For
example, the simple greedy algorithm favors Stanford over Harvard by
only 781; \.{football}~\.{10} raises this to 1895; the
example above corresponds to \.{football}~\.{4000}.

@ Here is the general program layout, as seen by the \CEE/ compiler:
@^UNIX dependencies@>

@p
#include "gb_graph.h" /* the standard GraphBase data structures */
#include "gb_games.h" /* the routine that sets up the graph of scores */
#include "gb_flip.h" /* random number generator */
@h@#
@<Type declarations@>@;
@<Global variables@>@;
@<Subroutines@>@;
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{
  @<Scan the command-line options@>;
  @<Set up the graph@>;
  while(1) {
    @<Prompt for starting team and goal team; |break| if none given@>;
    @<Find a chain from |start| to |goal|, and print it@>;
  }
  return 0; /* normal exit */
}

@ Let's deal with \UNIX/-dependent stuff first. The rest of this program
should work without change on any operating system.
@^UNIX dependencies@>

@<Scan the command-line options@>=
if (argc==3 && strcmp(argv[2],"-v")==0) verbose=argc=2; /* secret option */
if (argc==1) width=0;
else if (argc==2 && sscanf(argv[1],"%ld",&width)==1) {
  if (width<0) width=-width; /* a \UNIX/ user might have used a hyphen */
}@+else {
  fprintf(stderr,"Usage: %s [searchwidth]\n",argv[0]);
  return -2;
}

@ @<Glob...@>=
long width; /* number of cases examined per stratum */
Graph *g; /* the graph containing score information */
Vertex *u,*v; /* vertices of current interest */
Arc *a; /* arc of current interest */
Vertex *start,*goal; /* teams specified by the user */
long mm; /* counter used only in |verbose| mode */

@ An arc from |u| to |v| in the graph generated by |games| has a |len| field
equal to the number of points scored by |u| against |v|.
For our purposes we want also a |del| field, which gives the difference
between the number of points scored by |u| and the number of points
scored by~|v| in that game.

@d del a.I /* |del| info appears in utility field |a| of an |Arc| record */

@<Set up the graph@>=
g=games(0L,0L,0L,0L,0L,0L,0L,0L);
 /* this default graph has the data for the entire 1990 season */
if (g==NULL) {
  fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
            panic_code);
  return -1;
}
for (v=g->vertices;v<g->vertices+g->n;v++)
  for (a=v->arcs;a;a=a->next)
    if (a->tip>v) { /* arc |a+1| is the mate of arc |a| iff |a->tip>v| */
      a->del=a->len-(a+1)->len;
      (a+1)->del=-a->del;
    }

@* Terminal interaction. While we're getting trivialities out of the way,
we might as well take care of the simple dialog that transpires
between this program and the user.

@<Prompt for...@>=
putchar('\n'); /* make a blank line for visual punctuation */
restart: /* if we avoid this label, the |break| command will be broken */
if ((start=prompt_for_team("Starting"))==NULL) break;
if ((goal=prompt_for_team("   Other"))==NULL) goto restart;
if (start==goal) {
  printf(" (Um, please give me the names of two DISTINCT teams.)\n");
  goto restart;
}

@ The user must spell team names exactly as they appear in the file
\.{games.dat}. Thus, for example, `\.{Berkeley}' and `\.{Cal}' don't
work; it has to be `\.{California}'. Similarly, a person must type
`\.{Pennsylvania}' instead of `\.{Penn}', `\.{Nevada-Las} \.{Vegas}'
instead of `\.{UNLV}'. A backslash is necessary in `\.{Texas} \.{A\\\&M}'.

@<Sub...@>=
Vertex *prompt_for_team(s)
  char *s; /* string used in prompt message */
{@+register char *q; /* current position in |buffer| */
  register Vertex *v; /* current vertex being examined in sequential search */
  char buffer[30]; /* a line of input */
  while (1) {
    printf("%s team: ",s);
    fflush(stdout); /* make sure the user sees the prompt */
    fgets(buffer,30,stdin);
    if (buffer[0]=='\n') return NULL; /* the user just hit \<return> */
    buffer[29]='\n';
    for (q=buffer;*q!='\n';q++) ; /* scan to end of input */
    *q='\0';
    for (v=g->vertices;v<g->vertices+g->n;v++)
      if (strcmp(buffer,v->name)==0) return v; /* aha, we found it */
    printf(" (Sorry, I don't know any team by that name.)\n");
    printf(" (One team I do know is %s...)\n",
             (g->vertices+gb_unif_rand(g->n))->name);
  }
}

@*Greed. This program's primary task is to find the longest possible
simple path from |start| to |goal|, using |del| as the length of each
arc in the path. This is an NP-complete problem, and the number of
possibilities is pretty huge, so the present program is content to
use heuristics that are reasonably easy to compute. (Researchers are hereby
challenged to come up with better heuristics. Does simulated annealing
give good results? How about genetic algorithms?)

Perhaps the first approach that comes to mind is a simple ``greedy'' approach
in which each step takes the largest possible |del| that doesn't prevent
us from eventually getting to |goal|. So that's the method we will
implement first.

@ @<Find a chain from |start| to |goal|, and print it@>=
@<Initialize the allocation of auxiliary memory@>;
if (width==0) @<Use a simple-minded
  greedy algorithm to find a chain from |start| to |goal|@>@;
else @<Use a stratified heuristic to find a chain from |start| to |goal|@>;
@<Print the solution corresponding to |cur_node|@>;
@<Recycle the auxiliary memory used@>;

@ We might as well use data structures that are more general than we need,
in anticipation of a more complex heuristic that will be implemented later.
The set of all possible solutions can be viewed as a backtrack tree
in which the branches from each node are the games that can possibly
follow that node. We will examine a small part of that gigantic tree.

@<Type declarations@>=
typedef struct node_struct {
  Arc *game; /* game from the current team to the next team */
  long tot_len; /* accumulated length from |start| to here */
  struct node_struct *prev; /* node that gave us the current team */
  struct node_struct *next;
    /* list pointer to node in same stratum (see below) */
} node;

@ @<Glob...@>=
Area node_storage; /* working storage for heuristic calculations */
node *next_node; /* where the next node is slated to go */
node *bad_node; /* end of current allocation block */
node *cur_node; /* current node of particular interest */

@ @<Initialize the allocation of auxiliary memory@>=
next_node=bad_node=NULL;

@ @<Subroutines@>=
node *new_node(x,d)
  node *x; /* an old node that the new node will call |prev| */
  long d; /* incremental change to |tot_len| */
{
  if (next_node==bad_node) {
    next_node=gb_typed_alloc(1000,node,node_storage);
    if (next_node==NULL) return NULL; /* we're out of space */
    bad_node=next_node+1000;
  }
  next_node->prev=x;
  next_node->tot_len=(x?x->tot_len:0)+d;
  return next_node++;
}

@ @<Recycle the auxiliary memory used@>=
gb_free(node_storage);

@ When we're done, |cur_node->game->tip| will be the |goal| vertex, and
we can get back to the |start| vertex by following |prev| links
from |cur_node|. It looks better to print the answers from |start| to
|goal|, so maybe we should have changed our algorithm to go the
other way.

But let's not worry over trifles. It's easy to change
the order of a linked list. The secret is simply to think of the list
as a stack, from which we pop all the elements off to another stack;
the new stack has the elements in reverse order.

@<Print the solution corresponding to |cur_node|@>=
next_node=NULL; /* now we'll use |next_node| as top of temporary stack */
do@+{@+register node*t;
  t=cur_node;
  cur_node=t->prev; /* pop */
  t->prev=next_node;
  next_node=t; /* push */
}@+while (cur_node);
for (v=start;v!=goal;v=u,next_node=next_node->prev) {
  a=next_node->game;
  u=a->tip;
  @<Print the score of game |a| between |v| and |u|@>;
  printf(" (%+ld)\n",next_node->tot_len);
}

@ @<Print the score of game |a| between |v| and |u|@>=
{@+register long d=a->date; /* date of the game, 0 means Aug 26 */
  if (d<=5) printf(" Aug %02ld",d+26);
  else if (d<=35) printf(" Sep %02ld",d-5);
  else if (d<=66) printf(" Oct %02ld",d-35);
  else if (d<=96) printf(" Nov %02ld",d-66);
  else if (d<=127) printf(" Dec %02ld",d-96);
  else printf(" Jan 01"); /* |d=128| */
  printf(": %s %s %ld, %s %s %ld",v->name,v->nickname,a->len,
                                u->name,u->nickname,a->len-a->del);
}

@ We can't just move from |v| to any adjacent vertex; we can go only
to a vertex from which |goal| can be reached without touching |v|
or any other vertex already used on the path from |start|.

Furthermore, if the locally best move from |v| is directly to |goal|,
we don't want to make that move unless it's our last chance; we can
probably do better by making the chain longer. Otherwise, for example,
a chain between a team and its worst opponent would consist of
only a single game.

To keep track of untouchable vertices, we use a utility field
called |blocked| in each vertex record. Another utility field,
|valid|, will be set to a validation code in each vertex that
still leads to the goal.

@d blocked u.I
@d valid v.V

@<Use a simple-minded greedy algorithm to find a chain...@>=
{
  for (v=g->vertices;v<g->vertices+g->n;v++) v->blocked=0,v->valid=NULL;
  cur_node=NULL;
  for (v=start;v!=goal;v=cur_node->game->tip) {@+register long d=-10000;
    register Arc *best_arc; /* arc that achieves |del=d| */
    register Arc *last_arc; /* arc that goes directly to |goal| */
    v->blocked=1;
    cur_node=new_node(cur_node,0L);
    if (cur_node==NULL) {
      fprintf(stderr,"Oops, there isn't enough memory!\n");@+return -2;
    }
    @<Set |u->valid=v| for all |u| to which |v| might now move@>;
    for (a=v->arcs;a;a=a->next)
      if (a->del>d && a->tip->valid==v)
        if (a->tip==goal) last_arc=a;
        else best_arc=a,d=a->del;
    cur_node->game=(d==-10000?last_arc:best_arc);
                 /* use |last_arc| as a last resort */
    cur_node->tot_len+=cur_node->game->del;
  }
}

@ A standard marking algorithm supplies the final missing link in
our algorithm.

@d link w.V

@<Set |u->valid=v| for all |u| to which |v| might now move@>=
u=goal; /* |u| will be the top of a stack of nodes to be explored */
u->link=NULL;
u->valid=v;
do@+{
  for (a=u->arcs,u=u->link;a;a=a->next)