Добрый день!
Не совсем уверен, что правильный форум, если что, модераторы - переместите, d CS как-то увидел тольео техничесские вопросы, а хотелось бы получить помощь с направлением поиска алгоритма.
Пусть имеется занумерованный набор слов из некоторого алфавита. Требуется построить сеть, узлами которой служат начальная точка/буква алфавита/идентификатор слова, так что по заданному слову можно было найти идентификатор слова с условием, чтобы кол-во узлов отвечающих буквам алфавита было минимальным.
Пример.
слова:
adef - 1
xeh - 2
bceg - 3
решетка:
Код:
a - d f - #1
/ \ /
* - x - e - h - #2
\ / \
b - c g - #3
Нужна какая-то общая идея что и в чем минимизировать, есть большое подозрение что задачу можно свести к задаче целочисленного линейного программирования, но что-то пока ничего конструктивного в голову не пришло.
Еще одна мысль - запустить алгоритмы множественного выравнивания, что в существенном и даст требуемую сеть.
P.S. эта задача была названна как lattice, что я понял как требование построить "почти решетку", без стока.
