1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you have to explore adjacent nodes (as if you were moving in this "map") or you can jump to any node at each new step ? Do you know in advance the map dimension and all nodes coordinates or you have to explore it before ? $\endgroup$ – Vince Jan 29 at 8:18
  • $\begingroup$ I can only reach the adjacent vertex in the next step. All map dimensions and coordinates are known. $\endgroup$ – BGM Jan 29 at 8:23
  • $\begingroup$ So if you take a bad path and have to come back to start, you have to count again all nodes you cross ? $\endgroup$ – Vince Jan 29 at 13:13
  • $\begingroup$ Yes if you go to a dead end, then you may need to go back. All the steps are counted $\endgroup$ – BGM Jan 29 at 17:26
  • $\begingroup$ Not really sure I entirely understood the question but it seems to me as you are saying that you have a heuristic function which is indeed known as the Manhattan distance (i.e., the sum of the differences in $x$ and $y$). From here, any heuristic algorithm such as A$^*$, IDA$^*$, RBFS, DFBnB, etc. would actually work, wouldn't it. This is not about "narrowing down" the target, but simply delaying the exploration of those areas that are more unlikely to get to the target unless proven otherwise. $\endgroup$ – Carlos Linares López Jan 30 at 9:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.