Есть ли алгоритм поиска кратчайшего пути в ориентированном графе, который включает циклы отрицательной длины? Ограничение состоит в том, что каждый узел можно посетить только один раз, поэтому решение существует.
Я знаю алгоритм Беллман-Форд, но он не работает, когда присутствуют отрицательные циклы. Также ясно, что обход отрицательных циклов навсегда делает проблему неопределенной, поэтому я ограничиваю путь для посещения каждого узла не более одного раза.
Есть такой алгоритм? И есть ли готовая реализация, которую я могу использовать?
---РЕДАКТИРОВАТЬ---
Как указано ниже, вот фактическое приложение:
Учитывая входное изображение, содержащее рукописный текст, я могу оценить вероятности направления штриха в каждом пикселе:
Затем я могу поместить пиксели в график и найти путь пера:
Видите, как пропущено «л»? Если я могу установить соседние веса отрицательными, оптимальный путь будет проходить по всем буквам. Но отрицательные веса создают отрицательные циклы.
Вероятно, есть лучшее объяснение, но вот контрпример, когда нет эффективного решения: Предположим, что стоимость всех ссылок отрицательна. Тогда ваша проблема сводится к найти самый длинный путь (сбор как можно большего количества отрицательных затрат), что является NP-трудным.
@SomeDude Я языковой агностик, с питоном все в порядке. Но каков алгоритм?
@SaiBot NP-трудные проблемы все еще могут иметь достойные решения для средней сложности, а мои графики не полностью связаны. Вы знаете алгоритм?
Вы правы, что алгоритм Беллмана-Форда в этом случае не работает. Вы можете обратиться к разделу 2 этот ресурс. В нем обсуждается проблема неориентированного графа и работает на основе алгоритма идеального соответствия минимального веса Эдмондса. На самом деле, вас может заинтересовать этот вопрос, который очень похож на ваш.
Когда граф является направленным, то, как указал @SaiBot, проблема сводится к проблеме NP Hard, и нет эффективного решения.
Интересно. Так является ли это «проблемой пути Гамильтона»?
Не совсем так, но они связаны в том смысле, что проблема пути Гамильтона может быть сведена к задаче самого длинного пути. Возможно, вас заинтересует эта статья в Википедии.
And is there an off-the-shelf implementation I can use?
- скорее всего, но это зависит от языка, над которым вы работаете. У Python должен быть один из них на полке.