Is an optimal algorithm a complete algorithm?

Question

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

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

Thank.

Answer 1

Yes, by definition. The search for the optimal solution entails a proof of optimality. This can be done by finding all the solutions or by proving that no solution can have a higher value than the one that has already been found. In any case, at least one solution must be found.

If there is no solution, neither the optimal nor the complete algorithm will be found, of course.

Answer 2

, , , .

, , "", , , .

Answer 3

Yes. Simply put

• completeness determines:

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

• Optimal:

  Does it guarantee that the best solution will be found or not?

Therefore, according to your task, if the algorithm is optimal, it says that the best solution has been found. Then it automatically ensures the completeness of the algorithm, because it has already found a solution (as guaranteed).