Nano Hash - криптовалюты, майнинг, программирование

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

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

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

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

Мой вопрос:

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

Спасибо

path compare similarity graph-algorithm directed-graph
25.07.2011

  • Вы можете придумать любую метрику. Например, вычислите расстояние между первыми узлами в каждом пути, между вторыми узлами и т. д. и сделайте что-то вроде 1/(1+d1+d2+...+dn), а затем умножьте на x=0,9^|length1 - длина2| или что-то. 26.07.2011
  • Вы нашли ответ на этот вопрос? 07.11.2011

Ответы:


1

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

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

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

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

25.07.2011
  • Вы не можете изменить порядок узлов на моем графике, так как каждый узел представляет собой физическое местоположение на карте. Похоже, я выбрал довольно сложный вопрос. Мне просто интересно, есть ли какие-то конкретные алгоритмы, которые, возможно, уже были созданы, о которых я не знал. 28.07.2011
  • Ах, тогда вы говорите об очень специфическом ограничении теории графов, называемом евклидовыми графами. Смотрите отредактированный пост. 28.07.2011
  • я думаю, что то, что он описал, больше похоже на геометрический график, чем на евклидов график. См. en.wikipedia.org/wiki/Geometric_graph_theory и mathworld.wolfram.com/EuclideanGraph.html 18.05.2012
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..