问题描述
我对算法的健全性和完整性感到困惑。
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".
所以,
必须正确。但是它什么也不会返回。(缺失部分)
It must be right. But it can return nothing.(missed part)
好吧,这取决于。
如果算法中返回的列表构成了集合
,它是完整的,但没有声音。 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.
因此,您不能仅凭其合理性来推断算法是否完整,反之亦然。
请参考,也。
这篇关于算法的健全性和完整性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!