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

В общем виде задача такая:
Нужно найти на ненаправленном графе с неотрицательными весами ребер и узлов кратчайший путь не нарушающий определенных правил. Определить нарушает ли путь правила можно с помощью некой булевой функции isValid(Subpath x) которая на вход принимает путь целиком или его часть. Если часть пути невалидна, то не валиден и весь путь.

Пример 1:
Найти кратчайший путь, в котором ребра или ноды с определенным значением какого-то признака не встречаются более N раз подряд.

Пример 2:
Найти кратчайший путь, в котором ноды не должны быть включены в каком-то определенном порядке.

Первое что пришло в голову - взять алгоритм Дейкстры и добавить вызов isValid перед тем как считать вес подпути. Если подпуть невалиден - отбраковываем его. Это работает на простых примерах, но в принципе подход неправильный.
Например, имеем граф представленный на картинке, ищем путь от 1 до 6, веса написаны на ребрах. Допустим, что есть некие правила запрещающие, чтоб в пути были ноды в порядке 1-2-3 и 1-2-5.
По алгоритму Дейкстры с фильтрацией подпутей найдем путь 1-3-4-5-6 суммарной ценой 330, хотя кратчайший путь: 1-3-2-5-6, суммарной ценой 170.
a5f2108506c34be997b1a6e4af69e1fa.png

Еще один вариант: использовать алгоритм Йена но поменять условие выхода из внешнего цикла: искать не K путей, а первый путь для которого isValid == true. Так работать должно, но велика сложность алгоритма, будут проблемы с временем работы.

Может быть кто-то знает какие-то готовые решения, задача-то не такая уж и экзотическая.
  • Вопрос задан
  • 1018 просмотров
Пригласить эксперта
Ответы на вопрос 1
@AlexSku
не буду отвечать из-за модератора
Можно искать кратчайший путь с помощью рекурсивного запроса SQL (последние разделы 7 и 8). Не знаю насчёт скорости (вообще-то MS SQL Server шустрая машина. Хотя некоторые пишут, что рекурсия это зло, т.к. считается медленно. Короче - проверяйте), но в запрос можно вставлять любые условия.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы