Heuristic function for finding a path using a star

Question

I am trying to find the best solution for the next task.

• The numbers indicated inside each node are represented as (x,y) .
• Adjacent nodes to node always have a y value that is (current y nodes are +1).
• There is a cost of 1 to change the value of x when we move from one node to its neighboring
• To move from node to adjacent, there are no changes in the value of x .
• No two nodes with the same y value are considered adjacent.

The optimal solution is the one that has the lowest cost, I think about using the A * path search algorithm to find the optimal solution.

My question is: Is A * a good choice for such problems, or should I look at any other algorithm, and I also thought about using a recursive method to calculate the heuristic value, but I feel that this is not a good idea.

This is an example of how I think the heuristic function would be like this:

• Heuristic weight a node = Min (heuristic weight of its child nodes)
• The same goes for child nodes.

But as far as I know, heuristic should be approximate, so I think I'm going in the wrong direction, as far as the heuristic function is concerned.

Answer 1

A * guarantees the search for the least cost path in the graph with the cost of non-negative boundary paths, provided that you use the appropriate heuristic. What makes a heuristic function suitable?

Firstly, this should be valid, i.e. E. It must, for any node, either underestimate or correctly estimate the cost of the cheapest path from this node to any of the nodes in the target. This means that heuristics should never overestimate the value that you need to get from node to target.

Note that if your heuristic calculates an estimated cost of 0 for each node, then A * just turns into an exhaustive breadth-first search. Thus, h (n) = 0 is still a valid heuristic, only the worst possible. So, of all the valid heuristics, the more stringent the goal value is, the better.

Secondly, it must be cheap to calculate. This should, of course, be O (1), and it is advisable to look only at the current node. The recursive cost estimate you offer will make your search much slower, not faster!

So the question of the applicability of A * is whether you can come up with a pretty good heuristic. From your description of the problem, it is unclear whether you can easily come up with this.

Depending on the problem area, A * can be very useful if the requirements are relaxed. If the heuristic becomes invalid, you lose the guarantee of finding the best way. Depending on the degree of overestimation of the distance, the solution, the solution may be good enough (to determine a specific problem “good enough”). The advantage is that sometimes you can figure out this “good” way faster. In some cases, the probabilistic assessment of heuristics works well (it may have additional restrictions on its stay in the acceptable range).

Thus, in general, you have a search for the first time for accommodating problems, the next time you have A * for acceptable problems with valid heuristics. If your problem is unsolvable for a broad comprehensive search and does not allow heuristics, then your only option is to agree to a "reasonably good" suboptimal solution. Again, A * may still work with invalid heuristics here, or you should look at ray search options. The difference is that ray search has a limit on the number of ways to study the graph, and A * limits them indirectly, choosing a subset of less expensive ones. There are practical cases that A * cannot resolve even with uncomplicated admissibility, when the difference in cost between the different search paths is negligible. Ray search with its strict limit on the number of paths works more efficiently in such problems.

Answer 2

It seems redundant to use A * when something like Dijkstra will work. Dijkstra will only work on non-negative transitions of value, which, apparently, are true in this example. If you may have negative transitions, then Bellman-Ford should also work.