сеть поиска

[theambient]

Добрый день!

Не совсем уверен, что правильный форум, если что, модераторы - переместите, d CS как-то увидел тольео техничесские вопросы, а хотелось бы получить помощь с направлением поиска алгоритма.

Пусть имеется занумерованный набор слов из некоторого алфавита. Требуется построить сеть, узлами которой служат начальная точка/буква алфавита/идентификатор слова, так что по заданному слову можно было найти идентификатор слова с условием, чтобы кол-во узлов отвечающих буквам алфавита было минимальным.

Пример.

слова:
adef - 1
xeh - 2
bceg - 3

решетка:

  a - d       f - #1
/       \   /
* - x -   e - h - #2
\       /   \ 
  b - c       g - #3

Нужна какая-то общая идея что и в чем минимизировать, есть большое подозрение что задачу можно свести к задаче целочисленного линейного программирования, но что-то пока ничего конструктивного в голову не пришло.

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

P.S. эта задача была названна как lattice, что я понял как требование построить "почти решетку", без стока.