|
Такой вот вопрос интересует -
его можно по-разному формулировать, но ниже я его привожу
в простейшем виде, а затем даю конкретные параметры,
для которых меня интересует решение.
Дано множество всех двоичных слов разрядности m.
За расстояние между двумя словами из этого множества
принимаем количество разрядов, в которых эти слова отличаются.
Необходимо предложить способ задания
k центральных точек (слов) в этом множестве ( k = 2, 4, 8, 16, ... )
таким образом, чтобы после разбиения всех слов исходного множества
на k подмножеств по критерию близости к некоторой центральной точке,
максимальное расстояние между двумя точками, отнесенными к одному
подмножеству, было минимальным.
В действительности, решение этой задачи интересует для m = 50
и для 5-ричных слов (т.е., слов, каждый разряд которых может принимать
значения от 0 до 4).
Расстояние между словами, при этом, считается обычным образом -
как сумма абсолютных значений разницы в соответсвующих разрядах.
Интересует даже и приближенное решение этой задачи, т.е., чтобы
"расстояние было близким к минимальному".
Может есть общеизвестная теория решения таких задач ?
Буду очень благодарен ...
|
30.01.2008, 15:45 
