1

If we have a problem like the one in this image. We are in Arad, for example, and we want to go to Fagaras using a informed search algorithm (like A*) and the only information available is the one in the picture, is it possible to get a heuristics that is not trivial, but consistent and admissible?

Nuno Mendes
  • 11
  • 1
  • I don't understand your question completely but I assume that you are asking for shortest path problem: https://en.wikipedia.org/wiki/Shortest_path_problem And also take a look: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm – mertyildiran Oct 17 '15 at 00:14
  • Yes! But is it possible to use a* algorithm and explore less nodes than dijkstra? – Nuno Mendes Oct 17 '15 at 00:25
  • Then this is a possible duplicate of this question: http://stackoverflow.com/a/1332478/2104879 – mertyildiran Oct 17 '15 at 00:39
  • No, I'm sorry, maybe I didn't explain well the question. Finding an admissible heuristic for the mario problem is easier because you know the distance to the goal without obstacles, an ideal case. Here, you don't have a procedure for finding heuristic(node) without doing other search problem. – Nuno Mendes Oct 17 '15 at 00:57
  • As far as I know Dijkstra and A* et al only work on grid path problems. Your linked image needs something else entirely (look for _Route Inspection problem_ or _Rural postman problem_). If the nodes aren't positioned decently (direction + distance is a decent indicator), you'll just have to brute force it. – Rudie Oct 17 '15 at 21:30
  • No, Dijkstra's algorithm and A* are both designed to work on graph problems like this one. This issue is that A* tries to leverage information above and beyond the edge weights to solve the problem faster. You're saying you don't have any information above and beyond the edge weights, so A* isn't going to help. – seaotternerd Oct 31 '15 at 00:22

0 Answers0