Сортировка строк так, чтобы расстояние Хэмминга между соседними строками было низким

Проблема:

У меня есть N (~100k-1m) строк, каждая длиной D (например, 2000) символов с небольшим алфавитом (например, 3 возможных символа). Я хотел бы отсортировать эти строки так, чтобы между соседними строками было как можно меньше изменений (например, расстояние Хэмминга было небольшим). Решение не обязательно должно быть наилучшим из возможных, но чем ближе, тем лучше.

Пример

N=4
D=5
//initial strings
1. aaacb
2. bacba
3. acacb
4. cbcba

//sorted so that hamming distance between adjacent strings is low
1. aaacb
3. acacb (Hamming distance 1->3 = 1)
4. cbcba (Hamming distance 3->4 = 4)
2. bacba (Hamming distance 4->2 = 2)

Мысли о проблеме

У меня плохое предчувствие, что это нетривиальная проблема. Если рассматривать каждую струну как узел, а расстояния до других струн - как ребро, то перед нами проблема странствующего коммивояжера. Большое количество строк означает, что вычисление всех парных расстояний заранее потенциально невыполнимо, что, я думаю, превращает проблему в нечто большее, чем Canadian Traveller Problem.

На данный момент мое решение заключается в использовании VP-дерева для поиска жадного решения типа ближайшего соседа

curr_string = a randomly chosen string from full set
while(tree not empty)
    found_string = find nearest string in tree
    tree.remove(found_string)
    sorted_list.add(curr_string)
    curr_string = found_string

но первые результаты кажутся плохими. Еще одним вариантом может быть хэширование строк, чтобы более похожие строки были ближе, но я мало знаю о том, насколько хорошее решение это даст или насколько хорошо оно будет масштабироваться для данных такого размера.