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