考虑长度为n的所有二进制向量的集合S,其中每个包含正好m个; 所以每个载体都有nm零.
我的目标是从S构造一个数量k的向量,使得这些向量尽可能彼此不同.
举一个简单的例子,取n = 4,m = 2和k = 2,那么可能的解是:[1,1,0,0]和[0,0,1,1].
这似乎是编码理论文献中的一个开放性问题(？).
有没有办法(即算法)找到一个次优但好的解决方案？
汉明距离是在这种情况下使用的正确性能指标吗？
一些想法:
在本文中,作者提出了几种算法来找到向量子集,使得成对汉明距离> =某个值 d.
我已经实现了如下随机方法:取一个 SS,它由 S中的任何向量初始化.然后,我考虑 S中的剩余向量.对于这些矢量中的每一个,我检查该矢量相对于 SS中的每个矢量是否至少具有距离 d.如果是,则将其添加到 SS.
通过取最大可能 d,如果 SS的大小> = k,那么我将 SS视为最优解,并且我从 SS中选择 k个向量的任何子集.使用这种方法,我认为导致 SS将取决于初始向量的识别 SS ; 即有多种解决方案(？).
但是如果 SS的大小< k,怎么办？
从本文提出的算法中,我只理解了随机算法.我对二进制词典搜索(第2.3节)感兴趣,但我不知道如何实现它(？).
algorithm combinatorics binary-data hamming-distance data-structures