Я решаю задачу оптимизации поиска по графику. Мне нужно найти k лучших ациклических кратчайших путей через ориентированный взвешенный граф.
Я знаю, что существует ряд точных и приблизительных k-лучших алгоритмов, но большая часть недавних исследований, кажется, ориентирована на очень большие, очень редко связанные графики (например, дорожные маршруты и направления), и мой график не является ни тем, ни другим.
Отличительные аспекты моей проблемы:
Граф состоит из примерно 160 вершин.
График почти полностью связан (двунаправленно, поэтому ~ 160 ^ 2 ~ = 25k ребер)
k будет довольно маленьким (вероятно, меньше 10)
Максимальная длина пути, вероятно, будет ограниченной и очень маленькой (например, 3-5 ребер)
Я сказал «ациклично» выше, но просто повторюсь - решения не должны включать циклы. Это не проблема для 1-наилучшего кратчайшего пути, но это становится проблемой для k-наилучшего - например, рассмотрим трассу дороги - 2-й кратчайший путь от А до В может быть таким же, как 1-лучший, с быстрое путешествие вокруг квартала. Это может быть математически оптимальным, но не очень полезным решением. ;-)
Возможно, нам придется пересчитывать ребра на лету для каждого расчета. Стоимость фронта состоит из взвешенной суммы нескольких факторов, и окончательные требования (всякий раз, когда мы их получаем) могут позволить пользователю определять свои собственные приоритеты этих весовых коэффициентов, изменяя веса грани. Это относительно небольшой график (мы должны представить его в нескольких сотнях килобайт), поэтому, вероятно, целесообразно клонировать график в памяти, применить повторное взвешивание и затем выполнить поиск на клонированном графике. Но если есть более эффективный метод выполнения поиска при вычислении весов на лету, мне будет интересно.
Я смотрю на алгоритмы, описанные в Santos (K алгоритмах кратчайшего пути), Eppstein 1997 (В поисках k кратчайших путей) и других. Алгоритм Йена представляет интерес, прежде всего, из-за существующей реализации Java . Я не боюсь читать исследовательские работы, но я подумал, что стоит выбросить детали моей проблемы и попросить указатели, чтобы сэкономить время на чтение.
И если у вас есть указатели на реализации Java, даже лучше.
источник
Ответы:
Чтобы частично ответить на мой собственный вопрос:
После публикации этого вопроса я обнаружил, что нам нужно обрабатывать как отрицательные веса ребер, так и положительные (ограничение на ациклические / простые / безцикловые пути означает, что определено наилучшее решение, в то время как без этого ограничения кратчайший путь через граф с отрицательно- стоимость циклов не определена).
Алгоритм Йена и большинство других, которые я исследовал, зависят от серии поисков 1-лучших; большинство используют Dijkstra для этих промежуточных поисков. Дейкстра не поддерживает веса отрицательных краев, но мы можем заменить Беллмана-Форда на его место (по крайней мере, в иене; предположительно в Лоулере или Эппштейне). Я разработал модификацию Bellman-Ford с ограничением длины пути (по краям) и явной проверкой цикла во время поиска (вместо стандартного определения цикла после поиска). Вычислительная сложность хуже, но все же поддается требованиям. Я отредактирую этот ответ и свяжусь с техническим отчетом, если получу разрешение на его публикацию.
источник
Я бы сказал, что этот вопрос можно легко найти, и он также является дубликатом:
При этом я уже использовал и внедрил Eppstein и рекомендую его. Я нашел это довольно элегантно. Если я правильно помню, это также может быть оптимальным, и следующая статья объясняет это очень хорошо:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
источник