Кратчайший путь в ориентированном графе с циклами отрицательной длины

Есть ли алгоритм поиска кратчайшего пути в ориентированном графе, который включает циклы отрицательной длины? Ограничение состоит в том, что каждый узел можно посетить только один раз, поэтому решение существует.

Я знаю алгоритм Беллман-Форд, но он не работает, когда присутствуют отрицательные циклы. Также ясно, что обход отрицательных циклов навсегда делает проблему неопределенной, поэтому я ограничиваю путь для посещения каждого узла не более одного раза.

Есть такой алгоритм? И есть ли готовая реализация, которую я могу использовать?

---РЕДАКТИРОВАТЬ---

Как указано ниже, вот фактическое приложение:

Учитывая входное изображение, содержащее рукописный текст, я могу оценить вероятности направления штриха в каждом пикселе: Кратчайший путь в ориентированном графе с циклами отрицательной длины

Затем я могу поместить пиксели в график и найти путь пера: Кратчайший путь в ориентированном графе с циклами отрицательной длины

Видите, как пропущено «л»? Если я могу установить соседние веса отрицательными, оптимальный путь будет проходить по всем буквам. Но отрицательные веса создают отрицательные циклы.

And is there an off-the-shelf implementation I can use? - скорее всего, но это зависит от языка, над которым вы работаете. У Python должен быть один из них на полке.
SomeDude 10.09.2018 17:07

Вероятно, есть лучшее объяснение, но вот контрпример, когда нет эффективного решения: Предположим, что стоимость всех ссылок отрицательна. Тогда ваша проблема сводится к найти самый длинный путь (сбор как можно большего количества отрицательных затрат), что является NP-трудным.

SaiBot 10.09.2018 17:09

@SomeDude Я языковой агностик, с питоном все в порядке. Но каков алгоритм?

MrMartin 10.09.2018 17:20

@SaiBot NP-трудные проблемы все еще могут иметь достойные решения для средней сложности, а мои графики не полностью связаны. Вы знаете алгоритм?

MrMartin 10.09.2018 17:21
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
4
541
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы правы, что алгоритм Беллмана-Форда в этом случае не работает. Вы можете обратиться к разделу 2 этот ресурс. В нем обсуждается проблема неориентированного графа и работает на основе алгоритма идеального соответствия минимального веса Эдмондса. На самом деле, вас может заинтересовать этот вопрос, который очень похож на ваш.

Когда граф является направленным, то, как указал @SaiBot, проблема сводится к проблеме NP Hard, и нет эффективного решения.

Интересно. Так является ли это «проблемой пути Гамильтона»?

MrMartin 10.09.2018 17:22

Не совсем так, но они связаны в том смысле, что проблема пути Гамильтона может быть сведена к задаче самого длинного пути. Возможно, вас заинтересует эта статья в Википедии.

Zargles 10.09.2018 17:34

Другие вопросы по теме