I am studying intro to AI with shortest-path algorithms like A* and hill climbing.
I learned that A* is guaranteed to find the optimal solution if the heuristic function h(n) has the property : $$h(n) \leq \text{ actual distance n-t}$$ .
Is there a (mathematical) condition that tells us when we can trust hill climbing that will the optimal solution ? With some searches I could not find something clear.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Convex problems can be solved this way. Otherwise it will can find a local optima but it may not be global. $\endgroup$– CyclotomicFieldAug 30, 2022 at 16:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
A quick wiki search (here) says that hill climbing converges to a global optima under convexity, but it's not guaranteed to find global optima under an arbitrary function.
The idea is similar to why gradient descent doesn't necesarilly find global optima, close to a local optimum which is not a saddle point, no displacement will improve the value of the objective function.
-
$\begingroup$ I mean a practical condition for shortest -paths problem, gradient descent is not something , that can help me when I run the algorithm $\endgroup$ Aug 30, 2022 at 17:15