algorithm - 有效的猜测算法

Question

我将现实世界的问题抽象为以下问题:

• X 是所有可能的字母排列组合。
• Y 是一个字符串池。
• F 是一个函数，它从 X 中取出一个候选 x，并根据 x 是否属于 Y 返回一个 bool 值。

F 很昂贵，X 很大。从 Y 中提取尽可能多的结果的最有效方法是什么？误报是可以的。

Answer 1

确实没有办法很好地回答这个问题，因为这些类型问题的大多数解决方案都是高度特定于领域的。

您可能应该在这里尝试您的问题:https://cstheory.stackexchange.com/

但是，举例说明您所谈论的可能性范围； Traveling Salesman 问题看起来很相似 - 并且通常用“自组织 map ”解决:http://www.youtube.com/watch?v=IA6eGYMyr1A

当然，人们针对旅行商问题提出的“解决方案”不一定是最好的解决方案，只是一个好的解决方案......所以你的问题并不表明这是否适用于你的情况与否。

这听起来像是您在寻求某种更有效的暴力破解技术……但目前还没有。

作为另一个例子，对于破解密码(这似乎与您的问题相似)，人们通常先尝试“常用词/密码”，然后再诉诸完全暴力...但这又是一个特定于域的问题解决方案。