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.