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

Question

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

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

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

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

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

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 ресурсов.

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

Answer 2

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

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

Есть псевдополиномиальные алгоритмы времени для решения этой проблемы, которая называется, как и следовало ожидать, «Кратчайший путь с ограничениями ресурсов» (SPPRC).Проблема часто возникает в проблемах маршрутизации транспортных средств (VRP) и проблемах со связанными экипажами (обе проблемы транспортировки, которые в основном рассматриваются в Operations Research). В качестве отправной точки см. Следующую (обзорную) статью: С. Ирнич & G. Desaulniers, «Кратчайшие проблемы пути с ограничениями ресурсов», В G. Desaulniers, J. Desrosiers, M. Solomon (eds): Column Generation, Springer, 2005.

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