Path: utzoo!mnetor!uunet!littlei!ogcvax!pase From: pase@ogcvax.UUCP (Douglas M. Pase) Newsgroups: comp.theory Subject: Re: Maze searching problem Message-ID: <1613@ogcvax.UUCP> Date: 7 Apr 88 23:19:14 GMT References: Reply-To: pase@ogcvax.UUCP (Douglas M. Pase) Organization: Oregon Graduate Center, Beaverton, OR Lines: 22 In article 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)