Как найти ближайший вектор в {0,1,2} ^ 12, снова и снова

Я ищу пространство векторов длины 12 с элементами 0, 1, 2. Например, один такой вектор -
001122001122. У меня около тысячи хороших векторов и около тысячи плохих. Для каждого плохого вектора мне нужно найти ближайший хороший вектор. Расстояние между двумя векторами - это просто количество координат, которые не совпадают. Хорошие векторы не очень хорошо расположены, и причина, по которой они «хорошие», здесь не помогает. Мой главный приоритет - чтобы алгоритм был быстрым.

Если я провожу простой исчерпывающий поиск, я должен вычислить примерно 1000 * 1000 расстояний. Это кажется довольно тупоголовым.

Если я сначала применяю алгоритм Дейкстры с использованием хороших векторов, я могу вычислить ближайший вектор и минимальное расстояние для каждого вектора в пространстве, так что каждый плохой вектор требует простого поиска. Но в этом пространстве 3 ^ 12 = 531 441 вектор, поэтому предварительное вычисление составляет полмиллиона вычислений расстояния. Небольшая экономия.

Вы можете помочь мне придумать лучший способ?

Редактировать: Поскольку люди искренне спрашивали, что делает их «хорошими»: Каждый вектор представляет собой описание шестиугольного изображения шести равносторонних треугольников, которое является 2D-изображение трехмерного расположения кубиков (подумайте об обобщенном Q-bert). Равносторонние треугольники - это половинки граней кубов (45-45-90), наклоненных в перспективу. Шесть координат описывают природу треугольника (воспринимаемый пол, левая стена, правая стена), а шесть координат описывают природу краев (воспринимаемая непрерывность, два вида воспринимаемой прерывности). 1000 хороших векторов - это те, которые представляют собой шестиугольники, которые можно увидеть, глядя на кубы в перспективе. Причина поиска - применить локальные поправки к шестнадцатеричной карте, полной треугольников ...