search

citiususc / hipster

Hipster4j is a lightweight and powerful heuristic search library for Java and Android. It contains common, fully customizable algorithms such as Dijkstra, A* (A-Star), DFS, BFS, Bellman-Ford and more.
http://hipster4j.github.io
Apache License 2.0
326 stars 89 forks source link

Depth First Search for Romain Travel Problem #185

Closed dlaertius closed 6 years ago

dlaertius commented 6 years ago

Hi guys, forgive me if I'm wrong, but I tried a thousand time and cannot found the correct solution for dept-first-search problem related to Romain problem, from Arad to Bucharest.

This is my code: SearchProblem problem = GraphSearchProblem.startingFrom(RomanianProblem.City.Arad).in(RomanianProblem.graph()).takeCostsFromEdges().build(); System.out.println(Hipster.createDepthFirstSearch(problem).search(RomanianProblem.City.Bucharest));

My output is: [Arad, Zerind, Oradea, Sibiu, Fagaras, Bucharest] but I'm my opinion the correct must be [Arad, Sibiu, Fagaras, Bucharest] cause DFS explore each node before the backtracking preserving lexicographic order, am I right?

gonzalezsieira commented 6 years ago

Hi @dlaertius . Sorry for the big, big, big, big delay in taking a look to this issue. You're right.

It seems that the problem is in HashBasedHipsterDirectedGraph, which returns the cities not in lexicographical order, so DFS explores them not in the order you expect. For most problems this don't really matter, but for the Romania search problem it has to be done this way to get a comprehensive solution.

I'll take a look into this when I have some time. Thanks for your feedback.