Graph search algorithm

Question

I was blocked on the following question, can you please share your light on it?

one more: how to avoid the loop?

Answer 1

I believe the only sensible solution, assuming you don't have any information on the number of nodes in the network, is to take random left/right decisions at each node. Your route will form a random walk over the network and will eventually (after enough time steps) visit all nodes including the one with the hotel.

The number of steps required to get to the hotel will obviously depend on the size of the network but I believe it will be polynomial in the N, where N is the initial (but unknown) shortest path length between your starting point and the hotel. Without proof, I suggest teh average number of steps to solve for a network will scale as N^2.

Any deterministic path may run the risk of failing to visit one or more nodes.

Answer 2

Just found a counter example so the guess below is wrong.

I just tried a few examples - and did not try to explicitly construct a counter example - but it looks like alternating between going left and going right will visit all nodes without getting stuck in a loop. This may be the consequence of the graph being finite, 3-regular and planar. But I am very skeptic because I was unable to find this property mentioned anywhere and a handful of examples is far from a proof.