Как упорядочить последовательности битов, чтобы минимизировать их (циклическое) расстояние
У меня есть набор из N последовательностей по 12 битов, не обязательно различающихся, например:
011001111010
000101100101
000101100101
011000111011
011011011100
110010010100
...
Мне нужно упорядочить их и назначить каждому из них отдельное число от 0 до N-1 включительно, чтобы минимизировать сумму их расстояний Хэмминга между последовательными последовательностями. В общую сумму расстояний мне также нужно включить расстояние между элементом N-1 и элементом 0.
Итак, если мне нужно расстояние Хэмминга между
011011011100
110010010100
это 4, потому что есть 4 места, где две последовательности отличаются. Я знаю, что существует код Грея, который делает это для всех перестановок, в данном случае, 2^12 возможных последовательностей. Но мне нужно что-то более общее с некоторыми из этих перестановок, возможно, повторенными.
Я начинаю с одной последовательности, перебираю все остальные последовательности и нахожу ближайшую, а затем снова начинаю с этой. НО, в этом случае я не знаю, как учитывать расстояние между первой и последней последовательностью.
Другой подход, о котором я думал, - это попытаться упорядочить все мои N последовательностей, но N составляет около 64, поэтому грубая сила невозможна. Я должен пойти на что-то вроде кодирования всех возможных упорядочений в архитектуре генетического алгоритма, которая постепенно эволюционирует в сторону лучшего упорядочения, но... я уверен, что должно быть что-то умнее!
Это предназначено, чтобы помочь мне разработать настольную игру, поэтому она не должна быть пуленепробиваемой, мне не нужно что-то, что точно соответствует последовательности, которая минимизирует общую сумму расстояний... просто то, что, по крайней мере, идет вполне рядом с этим.
Thankx