Даны два графика G=(V,E), например:
и G'=(V',E'), например:
Мне нужно найти максимальное совпадение подграфа между ними.Рассмотрим G в качестве целевого графа и G' в качестве графа набережных.Каждый узел и каждое ребро имеет набор атрибутов, но это не слишком важно, поскольку у меня есть функция, которая дает два узла (или два ребра), она будет возвращать значение, представляющее сходство между обоими элементами (более высокое значение, более высокое сходство).
Максимальное совпадение совпадений будет совпадением с наибольшим сходством, в этом случае, поскольку у нас есть 2 узла и 1 ребро в качестве запроса, добавление значений сходства для этих 2 узлов и 1 ребра с элементамив целевом графике (G) должно быть максимумом.
Выполнение этого методом грубой силы вернет правильное решение, но его слишком сложно вычислить, поэтому я открыт не глобальному максимуму, ахорошее решение (например, алгоритм Жадного или алгоритм, который руководствуется чем-то для выполнения поиска), но алгоритм должен возвращать лучшее значение без ущерба для времени вычислений.