Алгоритм для сравнения сходства направленных путей через направленный график

Question

У меня есть направленный график с двумя направленными путями в нем.

Я хочу алгоритм, чтобы определить сходство между двумя путями.

Эта почта упоминает, используя Левенштейн расстояние определить приблизительное сходство. Я также понимаю, что Расстояние Хэминга использует аналогичную метрику.

Мой вопрос:

Как вы справляетесь с случаем, когда два пути бегут параллельно друг другу. То есть, если два пути не имеют похожих узлов, но будут считаться «похожими», потому что их пути движутся в одном направлении, очень близко друг к другу.

Спасибо

Answer 1

Простой ответ заключается в том, что это очень сложный вопрос, и многое опирается на ваше определение того, что означает «похожий» на графике. На большинстве графиков вы могли перестраивать узлы двух непересероченных путей плоским способом, чтобы показаться «параллельными».

Хорошим местом для начала рассмотрения более продвинутых показателей сходства было бы рассмотреть матрицу смежности графика и посмотреть на различные Матричное сходство алгоритмы.

Редактировать: ограничение вопроса на евклидовые графики

Существует множество активных исследований по этому вопросу при ограничении домена евклидовыми графиками, так как это применимая тема для таких областей, как ГИС, приложения машинного обучения для робототехники и совместная фильтрация в социальных сетях / искусственных сетях, таких как Интернет. Проверьте статьи на Google ученый.