最佳算法是完整算法吗? [英] Is an optimal algorithm a complete algorithm?

问题描述

我确实知道，完整的算法是一种解决方案，只要有解决方案，它就能找到它，而最优算法是一种能够找到成本最低的解决方案的算法.

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?

谢谢.

推荐答案

是的，根据定义.找到最佳解决方案需要证明最优性.可以通过找到所有解决方案或证明没有一种解决方案比已经找到的解决方案具有更好的成本来实现.无论哪种情况，都必须找到至少一个解决方案.

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.

这篇关于最佳算法是完整算法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！