algorithm - 回答 'yes' 或 'maybe' 的决策算法的名称是什么？

Question

我想知道决策算法的名称是什么，它不返回"is"或“否”，但只能为输入的真实子集决定"is"，不能提供对其余部分做出最终决定。

一个合适的例子是确定矩阵可逆性的算法——我的算法对矩阵的一个子类正确回答"is"，但对于其余矩阵既不能确认也不能否认。

在我看来，这是对真实答案的(某种)合理的欠近似，但维基百科仅在优化领域内定义了一种近似算法。

感谢您的参与!

Answer 1

您可能指的是随机/概率算法或随机数据结构。

以概率方式确定数字是否为素数的算法 (a primality test) 就是此类随机算法的示例。 Miller-Rabin算法就是一个具体的例子。

可以构建数据结构以使用某些操作的概率。 bloom filter就是这样一种概率数据结构。