我将现实世界的问题抽象为以下问题：
- X 是所有可能的字母排列的池。
- Y 是一个字符串池。
- F 是一个函数，它从 X 中获取一个候选 x，并根据 x 是否属于 Y 返回一个布尔值。
F 很贵，X 很大。从 Y 中提取尽可能多的结果的最有效方法是什么？误报是可以的。
问问题
124 次
3 回答
2
确实没有办法很好地回答这个问题，因为这些类型问题的大多数解决方案都是高度特定于领域的。
您可能应该在这里尝试您的问题：https ://cstheory.stackexchange.com/
但是，给你一个例子来说明你正在谈论的可能性范围；旅行推销员问题似乎很相似 - 通常可以通过“自组织地图”解决：http ://www.youtube.com/watch?v=IA6eGYMyr1A
当然，人们对旅行商问题提出的“解决方案”不一定是最好的解决方案，只是一个好的解决方案......所以你的问题并不表明这是否适用于你的情况或不是。
听起来您在要求某种更有效的暴力破解技术……但根本没有。
再举一个例子，为了破解密码（这似乎与您的问题相似），人们通常先尝试“常用单词/密码”，然后再诉诸暴力……但这又是一个特定于域的解决方案。
于 2011-06-15T03:15:23.820 回答
1
通过实施基于 Delta 的分数计算来降低 F 的成本。然后使用元启发式（或分支定界）找到尽可能多的 Y（例如使用Drools Planner）。
于 2011-06-21T09:00:06.180 回答
0
引入另一个便宜的函数 G 并测试 x 是否属于 y。当 F 返回 true 时 G 必须返回 true，并且当 F 返回 false 时可能返回 true。首先使用 G 进行测试，仅当 G 返回 true 时才使用 F 进行测试。
考虑到您的表述的一般性，我看不出怎么说更具体。
于 2011-06-15T05:14:10.550 回答