🚀 go-pugleaf

In article <svax.2119> siegel@svax.cs.cornell.edu (Alexander Siegel) writes:
 You are given a graph.  Each graph in the maze is labelled with a name
 of size O(log n).  The graph has the following properties:
 	1. Each edge is labelled with an arrow but it can be traversed
 		either direction.
 	2. The directed graph formed by the arrows is acyclic, and the
 		in and out-degree if each vertex is at most 2.
 	3. One vertex is the start and one is the goal.
 
 The problem is determine whether the goal is reachable from the start
 within an O(log n) space bound and no time bound.

--------------------------
It seems a simple dynamic programming approach would solve this easily.
It also seems that it would solve it in time proportional to n times the
distance between the start and the goal.  What's more, it would be independent
of any cycles, no matter how contorted.  I suppose whether this is true might
depend *how* the graph is represented.  If it is represented by a transition
matrix then a dynamic programming approach would certainly be more than
adequate.
-- 
Doug Pase  --  ...ucbvax!tektronix!ogcvax!pase  or  pase@cse.ogc.edu (CSNet)