This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.
Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, and there is a destination vertex which we do not know, until we reach that vertex. The task is to find out the destination, with in the smallest number of steps.
The brute force way will be traversing the entire graph which we must reach the destination as it is connected. However we want to improve this due to the following information: Each vertex has its own coordinates which is known. Upon reaching a vertex, including the starting vertex, we can know the relative direction of the destination from the current vertex, calculated by the coordinates differences. So we can use this information to eliminate some impossible vertexes and narrow down the target.
Is there any suggestion for the algorithm?
I can think of a naive way is to assume each possible vertex (given the hints obtained) are equally-likely, and I want to minimize the expected number of steps (i.e. each edge has equal weight). I can look for each of the neighboring vertex, and compute the distance between each possible destination to the neighboring vertex and sum them up (i.e. getting average). And we choose to move to the one with the lowest sum.
