Author: Stan Eisenstat
Subject: Re: [Cs223] Hwk5 algorithm
Date: Friday, 17 Apr 2020, 15:16:21

    > Message Posted By: Unknown
    >
    > In the spec, you say "let N be the number of moves associated with P in
    > the search table." Do we find this by searching for P in the search table,
    > finding its reachedFrom, searching for its reachedFrom in the search
    > table, and so on until we find the initial triple (indicated by a null
    > reachedFrom) and counting the number of triples we come across? If so, do
    > we count P in N?

No.  As stated in the specification:

  For efficiency and to avoid infinite loops when there is no solution, Nine20
  only tries to extend the first sequence of moves reaching a given position.
  This requires a search table that contains (POSITION, REACHED-FROM, NSTEPS)
  triples, where POSITION is a position that has been reached; REACHED-FROM is
  the position from which it was first reached by a single move (or NULL for
  the INITIAL position); and NSTEPS is the number of moves required to get to
  POSITION from the INITIAL position.  Thus POSITION is the key for the search
  table, while REACHED-FROM and NSTEPS are its attributes.

Thus you can find NSTEPS by looking up P in the hash table.

--Stan-