Difference between cost and the heuristic function in A* search

Question

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd see the heuristic function here as the number of direct steps. Or the number of cities we pass through, for example. The cost then is the number of miles between each city.

Am I right in thinking that it's the number of direct paths before we reach a path where there are multiple choices?

What confused me is, that I've also seen other examples where these numbers don't add up. For instance the image below:

The numbers in the second image don't add up the number of nodes on any path. Is it a case that the heuristic function varies from problem to problem, and I shouldn't think about how those numbers were generated too much? And that heuristic functions themselves are a separate problem, that we're just taking for granted in these two images?

Answer 1

Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "better" choice. Theoretical proof can be found in aima(I forget the exact page, sorry), but in practice, you need to ensure heuristic function follow the "triangle inequality"(in a graph version search.If you work on a tree, limit is not that strict, you can check the book above). And that will give you an optimal A* search.

triangle inequality is almostly same as formula in math and direct distance satisfies it naturally. That's why it's usual to use direct distance as a heuristic(if allowed).

if we say function $f$ satisifies triangle inequality, it means $\forall x,u,v ,f(u,v) < f(u,x)+f(x,v)$. In A star algorithm, we take $h(x)=h(x,target)$ by default. Intuitively, it says it's always further if you take a detour than directly go ahead.

Heuritics is chosen by yourself, but cost is attribute of the problem itself. You can change Heuritics to whatever you like, as long as it satisfies triangle inequality. But you can't change cost function.

I think trying to prove the optimal property is important for beginner, which helps you understand how algorithm is working. Forgive me for saying so much.