# Tag Info

4

The heuristic function $h:V \longrightarrow \mathbb{R}_{\geq 0}$ is *an input to the $A^*$ algorithm. If the function is admissible then $A^*$ algorithm gives you the solution; however as you have noted for infinite graphs the edge weights must have a positive lower bound. The point of the heuristic function is to find the shortest path in the least amount ...

3

No. Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1. We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)>1$. However, using $A^*$ search algorithm, we will end up with the path $s, t$, the unique and, ...

2

The solution provided by Apass Jack is absolutely correct but beyond simple examples proving that the answer is "definitely no", let me add another consideration (which actually provides a solution to the exercise suggested by Apass Jack): A heuristic which is inadmissible does not necessarily mean that paths found by A$^*$ with that heuristic should be sub-...

2

It depends how you implement Dijkstra. The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient. A* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them. This means that, especially in sparse ...

2

For A* to be optimal, the heuristic needs to be admissible (and this example shows why). This heuristic is not admissible because the heuristic value at M is 40, while the shortest path from M to R has length 30.

2

I think you might have misunderstood the heuristic function. It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$. The closer this estimate is to the true value, the better A* will perform. The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $... 1 They can't possibly be on the same scale throughout the search, if by that you mean that$g(n) \approx h(n)$for every node encountered near the search. Near the start, you'll have$g(n) \approx 0$, so$g(n) \ll h(n)$. Near the goal node, you'll likely have$h(n) \approx 0$, so$h(n) \ll g(n)$. On the other hand, it is possible to have the range of values ... 1 For A* to get the optimal path it requires that$f(n) \leq g(goal)$. In other words that the heuristic underestimates the cost from the node to the goal. Multiplying a valid hueristic with$0 \lt\alpha\lt 1$will not violate this requirement. Multiplying$g(n)$is not allowed because you can end up with$f(goal) = \alpha g(goal) < f(n)\$ which would ...

1

No, Dijkstra will explore all nodes with cost less than the cost of the completed path. While A* will explore all nodes with cost+heuristic less than the cost of the completed path. Thus if the heuristic is always positive then A* will expand less or equal nodes.

1

The best way to answer this is to use a profiler, but since I don't have your test cases I've looked around in the code and I'm fairly confident that it's due to differences in the way they produce the paths. The networkx A* implementation uses the standard technique of building a predecessor map and chaining backwards down it when the destination is ...

1

I would do a unique breadth exploration from the exit to get the shortest distance to exit of any position. Only obstacles (like walls) should be considered, not critters. This exploration should be done again each time an obstacle is added or removed. With some optimization, you may not have to recompute all the positions. Then each time a critter should ...

1

This is greedy best-first search.

Only top voted, non community-wiki answers of a minimum length are eligible