Author: Stan Eisenstat
Subject: Re: [Cs223] Depth first search vs Breadth first search
Date: Monday, 20 Apr 2020, 22:42:49

    > Message Posted By: Unknown
    >
    > I was trying to prove that all paths from the INITIAL string to GOAL from
    > Nine20 must have the same length given there is at least one path, but it
    > doesn't appear to be true, correct?

No.  For example, for

  % ./Nine20 100 1234-5678 123-45678

here are two solutions that do not revisit a position:

  1234-5678
  123-45678

and

  1234-5678
  1-3425678
  -13425678
  413-25678
  4132-5678
  4-3215678
  -43215678
  243-15678
  2431-5678
  2-3145678
  -23145678
  123-45678
=====

    > Is this why we had to use breadth first search when trying to find a
    > solution since depth-first search could have resulted in a  solution that
    > is longer than the shortest one but still less than MAXSTEPS?

That is one reason.  Another is to avoid paths that
visit the same position more than once (which allows
infinitely many solutions).
=====

    > Is there an upper bound as to how different the lengths any two paths from
    > INITIAL to GOAL can be by the way? That is, of course, assuming there is a
    > path.

Not if positions can be revisited, since then a path
can be arbitrarily long.  Yes otherwise, since there
is an upper bound on the number of moves needed to
reach any position (which you can find by remembering
the largest NSTEPS seen when solving a problem with
no solution).

--Stan-