Аннотация:Проблема проверки изоморфизма произвольных графов сложна и актуальна. Относительно недавно Ласло Бабаи опубликовал квази-полиномиальный алгоритм проверки изоморфизма. Для некоторых классов графов удаётся доказать даже полиномиальность сложности решения задачи изоморфизма. В частности, существует линейный алгоритм проверки изоморфизма деревьев, рассмотренный Александрой ранее в её курсовой работе.
В выпускной работе Измайловой А.А. была поставлена задача схемной реализации алгоритма проверки изоморфизма деревьев в нейросетевом базисе. То есть построить нейронную схему без памяти для решения задачи изоморфизма деревьев. Возможно, полученная нейросетевая архитектура может быть доучена для решения задачи изоморфизма в более широком классе графов.
Александрой была написана программа на javascript, действующая со всеми ограничениями нейронных схем, по которой впоследствии была построена и протестирована требуемая схема. Для сортировки наборов в лексикографическом порядке реализован алгоритм битонической сортировки (схемная сортировка за время порядка log^2 n). Для этого потребовалось реализовать компаратор в нейросетевом базисе.
Нелинейная глубина полученной схемы составила O(n), что соответствует обычному (не нейросетевому) алгоритму.