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

Question

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

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

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

Мой вопрос:

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

Спасибо

Answer 1

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

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

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

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