算法的健全性和完整性 [英] Soundness and Completeness of a algorithm

问题描述

我对算法的健全性和完整性感到困惑。

I am confused with soundness and completeness of algorithms.

声音算法永远不会返回错误的结果。

A sound algorithm will never return a false result. Is it possible that the algorithm doesn't return anything?

完整的算法将处理所有输入。算法返回的结果是否会影响算法的完整性？

A complete algorithm will address all inputs. Does the results the algorithm returns affect the completeness of the algorithm?

例如：如果排序算法将获取所有输入并返回列表，但不能保证返回排序列表，它只是一个不完善的算法，但是，它是完整的吗？

For example: if a sorting algorithm will take all inputs and returns a list, but it doesn't guarantee to return a sorted list, it is simply an unsound algorithm, however, is it complete?

推荐答案

让我们作为一组

声音算法永远不会在 S 中包含错误的答案，但可能会错过一些正确答案。 =>不一定是完整。

A sound algorithm never includes a wrong answer in S, but it might miss a few right answers. => not necessarily "complete".

完整算法应该在 S ：包括完整的正确答案。但这可能包含一些错误的答案。对于单个输入，它可能返回错误的答案。 =>不一定是声音。

A complete algorithm should get every right answer in S: include the complete set of right answers. But it might include a few wrong answers. It might return a wrong answer for a single input. => not necessarily "sound".

所以，

声音算法永远不会返回错误的结果。算法可能不返回
吗？

A sound algorithm will never return a false result. Is it possible that the algorithm doesn't return anything?

必须正确。但是它什么也不会返回。（缺失部分）

It must be right. But it can return nothing.(missed part)

例如，如果排序算法将接受所有输入并返回
列表，但不能保证返回排序后的列表，它只是一个
不健全的算法，但是，它是否完整？

For example, if a sorting algorithm will take all inputs and return a list, but it doesn't guarantee to return a sorted list, it simply a unsound algorithm, however, is it complete?

好吧，这取决于。

如果算法中返回的列表构成了集合 S ，则表示已完成因为包括了每个正确答案。不一定意味着每个输出都是正确的。例如。 S = {b1，b2} 。假设对于输入 a1 ，正确的输出为 b1 ；对于输入 a2 ，正确的输出是 b2 。如果算法为 a1 返回 b2 ，则为 b1 code> a2 ，它是完整的，但没有声音。

If the returned lists from the algorithm forms the set S, it's complete because every correct answer is included. It doesn't necessarily mean that every single output is correct. E.g. S = {b1, b2}. Assume that, for input a1, the correct output is b1; For input a2, the correct output is b2. If the algorithm returns b2 for a1, b1 for a2, it's complete but not sound.

另一方面，如果算法始终返回解决方案<$ c对于 a1 和 a2 的$ c> b1 ，显然还不完整。

On the other hand, if the algorithm always returns the solution b1 for both a1 and a2, it's obviously not complete.

因此，您不能仅凭其合理性来推断算法是否完整，反之亦然。

请参考 7种方式达到健全性和完整性，也此处。

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