我有一个项目数组（大约5000个项目，每个项目都是一个英文单词）和一个项目对之间的距离函数。我想在数组中找到一组项目，其中一组项目中的所有项目都满足距离标准（例如，每对项目的距离都小于2）。小组通常应该尽可能大，但没有正式的定义或硬性要求。
我的实现语言是PHP，但我正在寻找关于能够有效处理这一问题的算法的一般建议。
更新：我想我可以通过构建一个图来解决这个问题，其中顶点是项目，并且满足距离约束的项目之间有一条边。一旦我构建了图，我就可以运行像Bron–Kerbosch这样的算法来列出所有的最大集团。如果成功的话，我会更新，但在此期间，请随时添加您的想法。
这个函数是如何定义的？它是预先计算的吗？如果是这样，您可以迭代计算的函数表示，并根据您的标准检索成对的单词。如果没有，你就别无选择，只能计算所有成对单词之间的函数（这在你的图形方法中是必要的）。我会选择随机化+近似策略，而不是Bron-Kerbosch算法，比如
http://dimacs.rutgers.edu/Workshops/Challenge10/abstracts.html#ovelgonne
http://dl.acm.org/citation.cfm?id=1933306.1934471
它基于模块化最大化方法。模性是集群中传出边的数量与集群内边的数量之比。在您的情况下，您将查找比率为0的簇，并从中选择最大的一个。这个算法真的很快，适用于我使用过的大多数数据集。尽管基于模块化的方法可能对这个问题过于夸张，但IMHO我觉得这是一个思考这个问题的好方法+这个算法的实现是在线的（论文作者的C实现）。
我所理解的问题是：
"A-G"代表单词。"#"代表两个单词之间的距离。并且你需要找出距离<=2.
A B C D E F G
A * # # # # # #
B * # # # # #
C * # # # #
D * # # #
E * # #
F * #
G *
基本上它需要两级循环，我们可以做的是减少比较时间，只比较上面矩阵中的"#"部分。以下是PHP中的代码：
$result = array();
while ( ($word = array_shift($arrWordList)) !== NULL ) {
foreach ($arrWordList as $otherWord ) {
if ( calc_dist($word, $otherWord) <= 2 ) {
$result[] = array($word, $otherWord);
}
}
}
您可以使用$result继续执行某些操作。
考虑到您希望您的标准适用于组的所有成员，您需要一个允许重叠组的聚类算法。这是一个非常复杂的主题，所以我能做的最好的事情就是指导你阅读关于聚类算法的文献，特别是为重叠组设计的C-Means聚类。