pathfinding: несколько путей к месту назначения, с удалением края

Question

У меня странная проблема с поиском пути. На приведенной ниже диаграмме имеются два вида краев - красный и синий. Красные края надежны, в то время как синие края - нет - они обеспечивают ярлыки, но могут исчезнуть или быть недоступными в некоторых случаях - вы можете думать о них как о горных перевалах, которые снег зимой, или переправах, которые не работают по выходным , или железнодорожные линии, которые работают только во время работы в кулуарах.

Я хочу, чтобы мой дорожный указатель создавал ряд возможных путей. Пользователь должен знать самый быстрый ненадежный способ добраться до места назначения и возможные альтернативы, если этот путь недоступен. Следопыт должен составить кратчайший маршрут (на диаграмме, 3 прыжка с использованием синего края «b») и самый короткий надежный маршрут - (5 прыжков, используя только красные края), а также все другие возможные маршруты, которые короче надежного маршрута и использовать ненадежные синие края.

Для диаграммы, эти возможные перестановки:

• 3 хмель, используя кромку 'B'
• 3 хмель, используя 'а' краев, 'D'
• 4 хмеля, используя кромку 'C'
• 4 хмеля, используя край 'а'
• 4 хмеля, используя кромку 'D'
• 5 хмель, используя только красные края

Моей первую попытку для этого алгоритма следующим образом:

1. Найти & сохранить кратчайший возможный путь (используя ширину первого поиск)
2. Если есть нет синих краев на пути, остановитесь.
3. Если есть синие края в пути, удалить первый и перейти к 1.

Однако этот алгоритм не является полным, так как он может пропустить некоторые возможные пути. В приведенном выше примере путь, использующий только край 'a', будет пропущен (все остальные пути будут включены.)

Следующая мысль заключалась в том, чтобы выполнить поиск всех возможных сочетаний синих краев: [a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]. Естественно, это очень неэффективно и, вероятно, небезопасно для большого количества синих краев.

---

Можете ли вы придумать какие-либо решения, которые могли бы помочь мне здесь? Мне нужно один из:

• эффективного способа рассчитать все возможные пути
• Алгоритма, который возвращает пути, чтобы кратчайшие к длинным

Первым из них является лучшим решением, но позже Я мог бы работать, скажем, 10 секунд, а затем возвращать хотя бы хороший выбор коротких путей к месту назначения.

Кстати, у меня довольно хорошее представление о размере моего графика: около 7000 вершин, 30 000 красных краев и 200 синих краев.

Я уверен, что эта проблема была рассмотрена ранее, но я не могу найти ничего о ней. Можете ли вы указать мне в правильном направлении?

Answer 1

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

1. Get кратчайших надежный путь - это может быть сделано путем удаления всех синих ребер из графа, и запустить любой короткий алгоритм пути (например Dijkstra's Algorithm).
2. Получить k кратчайшие ненадежные пути - это K shortest paths problem на неизмененном графике, и вам нужно будет выбрать k. Bigger k - более экспансивным будет генерировать пути.

Обратите внимание, что поиск всех возможных путей крайне неэффективно, так как существует факторный число тех, и это число, как правило, невозможно вычислить во всех, кроме самых маленьких графов (определенно вне досягаемости для 7000 узлов)