2
$\begingroup$

I have an assignment in my university where I have to implement Uniform Cost Search and A* Search.

We have an input which includes a map and queries.

The map is weighted, directed graph, represented by an adjacency matrix. The queries include Uniform Cost Search and A* Search queries (Ex: Uniform(or A*) + initial location + goal location)

I cannot use heuristic functions based on physical distance because we have no knowledge and extra information about this graph except distances between vertices.

Is there any way to find a heuristic function in this case ?

(Is it possible to use prior results from Uniform Cost Search in the queries to extract information from the graph?)

$\endgroup$

migrated from stackoverflow.com Aug 16 '16 at 17:37

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 16 '16 at 22:30
  • $\begingroup$ Just as a quick, obvious note: It suffices that you implement A* and use it with a zero heuristic function to get UCS behavior "for free". $\endgroup$ – Omar Dec 11 '17 at 5:54
  • $\begingroup$ @Omar And, conversely, it suffices to implement UCS because, then, you can claim to have implemented A* with the zero heuristic. :-) $\endgroup$ – David Richerby Dec 11 '17 at 11:44
0
$\begingroup$

You can use the depth as the heuristic function I guess. The start node is at depth 0, the ones adjacent to it will be at depth 1 and so on! As the function will explore nodes, the heuristic function value will gradually increase with depth and that will make the function to choose next node with more caution, so that overall cost (distance to next node + heuristic value) is least affected.

Edit: You can use powers of 2 where the exponent term will be the depth. So the start node has heuristic value 2^0 = 1, the nodes adjacent to it have heuristic value 2^1 = 2 and so on.

$\endgroup$
  • $\begingroup$ so, it's not even admissible ? $\endgroup$ – Forrest Aug 18 '16 at 1:46
  • $\begingroup$ I think I have written that in reverse order since the admissible heuristics must always give the cost that is lesser than the actual cost. The problem here is that you have to assume the heuristic. If the nodes were given in the form of (x,y) coordinates, then we could always use the Manhattan distance as the heuristic. This is a bit confusing! $\endgroup$ – kiner_shah Aug 18 '16 at 5:15
  • $\begingroup$ I'm currently using a heuristic function h(n) = the distance from n to the nearest vertex (It is a consistent heuristic) It means instead of only consider the cost from the root to n, now the next path will be taken into account as well. Granted, it doesnt express how close to the goal a vertex is. However, it will choose next vertex to expand with more caution like you say. It works pretty well, i tested it with Uniform Cost Search (UCS) in order to make a comparison with a graph having 1000 vertex. The time execution and the number of expanded vertices with A* algorithm is just a half. $\endgroup$ – Forrest Aug 18 '16 at 7:30
  • $\begingroup$ I think I get your approach, but we still can't be sure with the correctness of choosing that particular heuristic. Every algorithm has a weak point and keeping that in mind, there must be some hidden test case, which may fail the heuristic. Admissible heuristics has certain weaknesses which can lead to overheads. I would suggest focusing more on consistency rather than admissibility. Keeping that in mind, I guess you could improve your heuristic function such that there will be no overhead when some hidden test case is encountered $\endgroup$ – kiner_shah Aug 19 '16 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.