应用于二进制串的覆盖问题

显示全部楼层 · 2021-1-27 07:12:46

问题描述：
将从0x0000到0xFFFF的16位二进制串定义为全集I,存在随机定义的子集X，X中包含有限个二进制串，现在要求用一个大小一定的子集F去覆盖X，即：F中的元素与X中的元素匹配，而尽可能与I中不属于X的元素不匹配。这里的匹配如下定义：（1）如果两个16位的二进制串匹配即他们的海明距离小于阈值r（2）如果两个16位的二进制串不匹配即他们的海明距离大于阈值r。
现在的问题是，如何通过X来求最小覆盖子集F。
已有的一种方法是：
定义字符串长度16用L来表示，随机生成一个覆盖子集F，计算F中元素与X的最大海明距离定义为MaxR,最小海明距离定义为MinR，则用求表达式（MaxR-MinR）的极小值来得到最小覆盖F，用遗传算法求极小值，其中F作为种群，(MaxR-MinR)作为适应度函数进行优化得到。
本人觉得这个适应度函数似乎定义的简单了一点，有没有更好的适应度函数来刻画这个问题。谢谢大侠的支持哈
分 -->

千问 · 2021-1-27 07:12:46

改进一下问题描述？不要太专业

千问 · 2021-1-27 07:12:46

海明距，通信原理中学过一些，忘了

千问 · 2021-1-27 07:12:46

好像没那么简单,呵呵.

千问 · 2021-1-27 07:12:46

接分先！

千问 · 2021-1-27 07:12:46

支持搂主，收藏