Мыслил в терминах шаров, поэтому предложение Serega126 о том, что «ловли не будет» понял неправильно. Осмысленный ответ дан niefer’ом.
Постараюсь пояснить «язык шаров» (к сожалению, коротко не получилось). Большинству это все известно, но кому-нибудь пригодится.
1. Популярно о задаче покрытия:
$ q=3,n=6, r=2, IMI \to min $.
а. Введение. Обозначим
$ E(6,3) $ – множество всех последовательностей длины 6 над троичным алфавитом (их число, очевидно, 729). В качестве троичного алфавита удобно принять множество
$ A=${
$ 0,1,2$} и использовать для построения функций над символами алфавита и над последовательностями из
$E(6,3) $ операции по модулю 3. На основе операций
$ +, - $ (определенных в
$ A$) вводятся операции
$ +, - $ сложения и вычитания (покомпонентного) последовательностей из
$ E(6,3) $.
Весом Хемминга последовательности
$ x=(x_1,…,x_n) \in E=E(n,q) $ называется число ненулевых компонент этой последовательности:
$ W(x)= \sum_i I(x_i \ne 0) $, где
$ I(.)$ – индикаторная функция:
$ I(True) = 1, I(False) = 0$.
Расстоянием Хемминга между последовательностями
$ x, y$ называется число компонент, в которых последовательность
$ y=(y_1,…,y_n)$ отличается от последовательности
$ x $:
$ D(x,y)= \sum_i I(x_i \ne y_i) $).
Если должным образом в
$ E$ определены операции
$ +, - $ и элемент
$ 0$, то, очевидно,
$ D(x,y)= W(x-y) $, т. е. расстояние Хемминга между последовательностями равно весу Хемминга разности этих последовательностей.
Под пространством Хемминга обычно понимают метрическое пространство:
$ <E, D>$.
б. Постановка задачи.
Пусть в соответствии с рассмотренным выше определены конструкции:
$ E(6,3),W(),D(),+, -$.
Произвольная последовательность
$y$ совпадает с заданной последовательностью
$x$ в 4-х или более позициях тогда и только тогда, когда
$ D(x,y) \le 2$, т.е. когда шар радиуса
$ 2$ с центром в точке
$ x$ включает (покрывает) точку
$ y$.
Для
$ x \in E, r=0,1,2…$ обозначим
$ S(x,r) $ – шар радиуса
$ r$ с центром в
$ x$. Тогда записанное выше условие может быть сформулировано в виде:
последовательность y совпадает с заданной последовательностью
$ x$ в 4-х или более позициях тогда и только тогда, когда
$ y \in S(x,2) $.
Пусть
$ M \subseteq E$ (т. е.
$ M$ - код в
$ E$). Мощностью (иногда объемом) кода
$ M$ называют число элементов в
$ M$ (обозначаемое
$ IMI$). Радиусом покрытия кодом
$ M$ пространства
$ E$ (или просто «радиусом покрытия кода
$ M$») называется наименьший радиус шаров с центрами в точках кода
$ M$, покрывающих в совокупности все точки пространства
$ E$.
Бытовой пример: На столе проставлены точки. Пусть круги радиуса 10 с центрами в данных точках покрывают всю поверхность стола, а круги меньшего радиуса не покрывают. Тогда радиус покрытия поверхности стола кодом из отмеченных точек равен 10.
С учетом введенных понятий рассматриваемая задача имеет следующую математическую формулировку:
Найти код
$ M \in E(3,6) $ минимальной мощности, с радиусом покрытия
$ 2$.
Ранее приведен пример кода с радиусом покрытия
$ 2$ мощности
$ 17$.
2. Некоторые детали.
а. Эквивалентные коды.
Поскольку параметры покрытия зависят лишь от метрической структуры кода, то преобразования кода, не меняющие его метрическую структуру, не изменяют свойства покрытия. При этом если код
$ M$ имеет радиус покрытия
$ 2$, то, очевидно, и эквивалентные коды, т. е. полученные в результате, так называемых, эквивалентных преобразований:
- перестановок компонент последовательностей,
- прибавления к каждому кодовому слову произвольной (одной и той же) последовательности,
будут иметь радиус покрытия
$ 2$.
б. Объемы шаров и нижние границы.
Нижние границы элементарно получаются из следующих соображений.
Каждый шар содержит ровно
$ N(q,n,r) = \sum_{j=0}^r C_n ^j(q-1)^j $ элементов. Поэтому множество из
$ m$ шаров не может содержать более
$ mN(q,n,r) $ точек и, следовательно, число элементов
$ m=IMI$ покрывающего кода удовлетворяет неравенству
$ mN(q,n,r) \ge q^n$, откуда
$ m \ge q^n/ N(q,n,r) $.
в. Элементарная граница. В нашем случае
$ N(3,6,2) =73$, поэтому
$ m \ge 729/730 \Rightarrow m \ge 10$.
г. Возможности для улучшения нижней границы.
Нетрудно установить (например, с использованием эквивалентных преобразований), что из любых
$ 4$ шаров радиуса
$ 2$ в
$ E(3,6) $, по крайней мере, 2 пересекаются и, следовательно, объем любых 4-х шаров не может превышать
$4x73-1$. Отсюда следует:
$ m \ge 4x729/ (4x73-1) \ge 10,2 \Rightarrow m \ge 11$.
Дальнейшее улучшение нижней границы возможно на основе получения верхней оценки максимального объема области покрытия 5-ю, 6-ю и более шарами (ограничивается вычислительной сложностью). Так, для того, чтобы убедиться в справедливости неравенства
$ m \ge 12$ достаточно получить одну из оценок объема области покрытия
Число шаров 5 6 7
объем области покрытия
$ \le $ 331 397 463
а для неравенства
$ m \ge 13$ – соответственно из оценок
Число шаров 6 7
объем области покрытия
$ \le $ 364 425
Число переборов можно сократить, если во всех вариантах использовать фиксированные две последовательности
$ (000000) $ и
$ (001111) $. Обоснованность такого выбора обусловлена возможностью приведения любого доминирующего варианта к варианту с указанными последовательностями путем эквивалентных преобразований.
Имеется много других возможностей для сокращения числа переборов.
С другой стороны, поиск шаров с максимальным суммарным объемом полезен для построения кода, наилучшим образом решающего сформулированную задачу.
Будем надеяться, что кто-нибудь посчитает.
