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

Алгоритм поиска пути Гамильтона в DAG

Я имею в виду книгу Скиенны по алгоритмам.

Проблема проверки того, содержит ли граф G вершину Hamiltonian path, заключается в NP-hard, где гамильтонов путь P — это путь, который посещает каждую вершину ровно один раз. В G не обязательно должно быть ребро от конечной вершины до начальной вершины P , в отличие от проблемы гамильтонова цикла.

Для заданного ориентированного ациклического графа G (DAG) задайте O(n + m) временной алгоритм, чтобы проверить, содержит ли он гамильтонов путь.

Мой подход,

Я планирую использовать DFS и Topological sorting. Но я не знал, как соединить два понятия в решении задачи. Как можно использовать топологическую сортировку для определения решения.

Какие-либо предложения?

directed-acyclic-graphs algorithm graph-algorithm hamiltonian-cycle
20.04.2013

Ответы:


1

Сначала вы можете топологически отсортировать DAG (каждый DAG может быть отсортирован топологически) за O(n+m).

Как только это будет сделано, вы узнаете, что ребра идут от вершин с меньшим индексом к вершинам с более высоким индексом. Это означает, что гамильтонов путь существует тогда и только тогда, когда между последовательными вершинами есть ребро, например.

(1,2), (2,3), ..., (n-1,n).

(Это потому, что в гамильтоновом пути вы не можете «вернуться назад», и все же вы должны посетить все, поэтому единственный способ - «не пропустить»)

Вы можете проверить это условие за O(n).

Таким образом, общая сложность составляет O(m+n).

20.04.2013
  • Но вы предположили, что граф связан, не может ли быть топологическая сортировка для графа, в котором есть несвязные части? 14.03.2016
  • Я НЕ предполагаю, что граф связан. Если граф не связан, то гамильтониана нет, и этот алгоритм обнаружит его, потому что по крайней мере одна из последовательных вершин не будет связана (иначе граф будет связан) . 18.03.2016
  • Как насчет гамильтоновых циклов, пути Эйлера и циклов Эйлера одновременно? 15.11.2017
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..