Is an optimal algorithm a complete algorithm?

Question

I do understand that a complete algorithm is one where if there is a solution, the algorithm is able to find it and that optimal algorithm is one where it manages to find a least cost solution.

But is an optimal algorithm, a complete algorithm? Can please briefly explain?

Thanks.

Answer 1

Yes, by definition. Finding the optimal solution entails proving optimality. This can be done by finding all solutions or by proving that no solution can have better cost than the one found already. In either case, at least one solution has to be found.

If there is no solution, neither an optimal nor a complete algorithm would find one of course.

Answer 2

The notion of completeness refers to the ability of the algorithm to find a solution if one exists, and if not, to report that no solution is possible.

If an algorithm can find an solution if it exists but it's not capable to "say" that there is no solution in cases when there are no solution, then it's not complete.

Answer 3

Yes. In simple terms

• completeness defines :

  If a solution is possible, it ensures the solution. (Is it guaranteed or not ?)

• Optimal :

  Ensures the best solution will be found or not ?

Therefore according to your problem if an algorithm is optimal, it tells the best solution is found. Then automatically it ensures the completeness of the algorithm because it already found the solution (as guaranteed).