2
$\begingroup$

I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge. Let's imagine that there's a 2D grid, where S units need to go to T points, but the caveat is that going through a known/explored path has a lower cost than going through a new one (meaning, going through the same edges as other flows).

Max Flow Minimum Cost can easily handle exactly the opposite, meaning that it will prioritize to spread to cover as much ground as possible to reach the destinations. Still, this technique cannot be inverted to satisfy the original statement, meaning to reuse paths/cells to reach the destinations at a lower cost if the edge has any flow.

Improve this question
$\endgroup$
2
  • $\begingroup$ What does "S units need to go to T points" mean? Each of the S units must be able to go to all of the T points? Maybe S=T and you have a set of S pairs, where each pair describes the starting position of a unit and the desired ending position? Apparently we are to find a set of paths, but what properties must that set of paths satisfy? $\endgroup$
    – D.W. ♦
    May 26 at 6:29
  • 3
    $\begingroup$ Depending on the problem formulation, you might be able to show it NP-hard by reduction from the (rectilinear) Steiner tree problem or the minimum routing cost spanning tree. $\endgroup$
    – D.W. ♦
    May 26 at 6:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.