CODEWITHSUNDEEP
algorithmterminologyheuristics
Barpa
Barpa

Reputation: 275

Is there a case that a heuristic approach to be guaranteed to provide optimal solution?

As it is said (e.g., Wikipedia) heuristics provide solution which are not guarantee to be optimal. I think this is true in many cases, but what if we use for example a heuristic cost estimation (like the one in A* algorithm) to achieve a solution which could be proven to be optimal. In that case shouldn't we refer to that algorithm as heuristics?

Upvotes: 2

Views: 208

Answers (1)

Fred Foo
Fred Foo

Reputation: 363547

Given a heuristic cost estimation function that obeys certain laws, A* is an algorithm in the strict sense of a method of computation that always gives the right answer to a prespecified set of problems.(*) The fact that it uses a heuristic does not make A* itself a heuristic.

( * ) There are cases where the optimal path between A and B might not exist and A* will run forever; for such problems, A* is a semi-algorithm.

Upvotes: 5

Related Questions