Кратчайшие пути с ограничениями ресурсов

Question

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

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

Я нашел довольно много литературы по этой теме, this дает хороший обзор, я думаю.Тем не менее, я изо всех сил пытаюсь понять это и найти краткий алгоритм, который может быть реализован (я использую Python, однако любые четкие алгоритмические идеи были бы хороши).

Я понимаю, что эта проблема является NP-полной, и поэтому меня интересуют любые хорошие алгоритмы аппроксимации, а также точные подходы.

У кого-нибудь есть хорошие рекомендации?

Answer 1

Что вы можете сделать, это преобразовать ваш график (V,E) в (V',E'), где

• P(v) - цена исходного узла v
• R - максимальное использование ресурса.
• V' = {(v,k) | v in V and k in [0..R]}
• E'((v,k),(w,l)) = E(v,w) and k+P(w)=l

Затем вы выполняете поиск dijkstra из (v0,P(v0)). Если можно было найти путь к v1, то с учетом ограничения самое короткое расстояние до него будет самым коротким из (v1,k) вершин.

Вы явно не создаете фактический расширенный график. То, что будет происходить в вашем модифицированном dijkstra, заключается в том, что в дополнение к расстоянию вы также сохраните использование ресурсов. Вы бы пошли по пути, только если он не превысил предел. И вместо того, чтобы хранить dist[v], вы бы сохраняли dist[v,k], представляющий кратчайший путь до v, используя ровно k ресурсов.

Если ваша привязка к ресурсу очень велика, она потенциально может вырасти до большой. Отсюда и полнота НП. Однако, если ваш ресурс ограничен, или вы не возражаете против округления до ближайших 10, 100 или 1000, он будет выполняться за быстрое полиномиальное время. Особенно, если вы реализуете оптимизацию остановки после того, как достигли полезного значения (v1,k).

Answer 2

Решение этой проблемы как k-кратчайшего пути страдает от того факта, что вы не знаете, как выбрать k.

Решение этого вопроса в соответствии с предложенным принятым ответом страдает от того факта, что вам необходимо поддерживать dist[v,k] для потенциально всех значений k из всех различных путей, поступающих из источника в узел v (что приводит к очень неэффективному алгоритму).

Существуют алгоритмы псевдополиномиального времени для решения этой проблемы, которые, как и следовало ожидать, называются «проблемой кратчайшего пути с ограничениями ресурсов» (SPPRC). Эта проблема часто возникает в проблемах маршрутизации транспортных средств (VRP) и проблемах сопряжения экипажа (обе эти проблемы связаны с транспортировкой, которые в основном рассматриваются в исследовании операций). За отправную точку см. Следующую (обзорную) статью: С. Ирнич и Г. Дезаульнерс, «Проблемы кратчайшего пути с ограничениями ресурсов», В Г. Дезолье, Дж. Дезрозье, М. Соломон (ред.): Генерация столбцов, Springer, 2005.

Вы можете найти название статьи в Google, и вы сможете скачать ее бесплатно. Я должен отметить, что ваша проблема имеет необычную структуру ограничений: вам нужно «потратить» хотя бы определенное количество ресурса вместо того, чтобы убедиться, что вы не тратите «слишком много» ресурса ...