论文部分内容阅读
本文考虑了一个二维数字数据中的最大隔离问题。给定一个m行,n列数组以及l个元素,其中2≤l≤mn,问题是如何把这l个元素放到该数组中,使得任意两个元素的最小间隔距离尽可能大。本论文中,我们所研究的隔离问题是二维交错问题的一种延伸或者简化:集中考虑其中的一个码字,使得这一个码字中的不同码元之间的最小间隔距离最大化。这个问题类似于已经被广泛研究的针对二维数字数据突发错误的纠错方案,即交错方法,通过在空间中把成块状或者成片状出现的突发错误离散,使得每个码字中的突发错误达到尽可能小,从而容易修复。 对于一般的m,n,l,在n-1≥(l-1)(m-1)的情形中,最大隔离已经有比较完整的结论,所以我们考虑n-1<(l-1)(m-1)的情形,得到最大隔离的一个下界,对于l=6,m≤5的情形,得到数组中任意两个元素之间的最大隔离以及当l=7时,最大隔离的一个上界。另外,对m=5时的情况讨论了给定数组中元素的最小间隔距离d,得到数组中可放元素的最大个数。