Thursday, June 18, 2009

O(N) for Bunker visiting Problem

Actually, I figured out how to prove my algorithm is O(N) (informally). (see earlier post)

If x is a starting point, then any point y prior to x where each point y .. x contains a surplus will also be a valid starting point. So, the algorithm finds a locally optimal starting point initially, in that it first looks for the first element in a sequence of surpluses.

Now, in the tryLoop sequence, it then attempts to find a way around the loop from this locally optimal starting point. Since it always arrives at the next node with a surplus (else it would return the failed node), then if it arrived at a valid starting point with a surplus then it would be able to complete the circuit, because it is possible to complete the circuit from a valid starting point with no surplus.

So, the starting point cannot be anywhere between the attempted starting point and the point where the algorithm returns a failed node.

Further, by the optimality shown above, skipping nodes that have a deficit will never skip over a valid starting point.

So, the algorithm does not skip over any valid starting points, and either visits every node in the tryloop method, or skipping over deficit nodes. Thus, it will visit at most N + (N - 1) nodes (N to try each node, and N-1 to verify the circuit from the attempted node).

So, the algorithm is worst case O(2N -1) = O(N).

-Larry
http://www.google.com/profiles/larrywatanabe ,
http://stackoverflow.com/users/118860/larry-watanabe ,
http://larrywatanabe.blogspot.com ,
http://portal.acm.org/citation.cfm?id=125337 ,
http://www.programmersheaven.com/user/larrywatanabe/ ,
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html ,
http://portal.acm.org/citation.cfm?id=211243 ,
http://www.interaction-design.org/references/authors/larry_watanabe.html

No comments:

Post a Comment