Finding path through DAG with a total path cost equal or as close as possible to some value

user_6329005 0
Viewed 95

I am working on a problem that I have generalised to what I have described in the title. Essentially I have a DAG that will look something like this: (I know it doesn't matter what the DAG looks like I just thought it might show where I am at). Graph I've drawn the vertex values as the edge distance (or cost) from the vertices in the layer, where layers are made of the vertices that are aligned vertically. In other words the edges (a,a') (b,a') have equal value when a and b are in the same "layer".

I need to find the path from the left most layer to the right most layer such that the sum of the values of the edges in the path are equal, or less than and as close as possible to a target value.

The original problem is basically finding a sum of single values in distinct matrices equal (or less than and as close close as possible) to a target value where exactly one value from each value is used.

I have to use tabulation, and I am not sure how to approach this problem. Im not looking for an entire solution. If this question is poorly written please tell me.

graph-algorithm algorithm java
2 Answers

First, I'll comment that your original problem formulation of 'Given n sets of integers and bound B, select one number from each set to achieve the largest sum <= B' is much more straightforward than the DAG path analogy, so I'll stick to that.

Unfortunately, the problem is NP-Hard by reduction from subset sum: Given an instance of subset sum with universe S = (s1, s2, ... sn) and target B, create an instance of your problem with n sets of size 2: (s1, 0), (s2, 0), ... (sn, 0). The bound B is reachable iff there is a subset sum equal to B.

Fortunately, if your values are all small, you can use a pseudopolynomial algorithm similar to the subset-sum algorithm:

  • Initialize a boolean array A of length (B+1) and all values false except A[0] = True
  • For each set S in your list of sets:

    • Initialize a new boolean array A' of length (B+1), with all values False.

    • For each number x in S:

      • For each index i with A[i] = True: Set A'[i+x] = True, if in range.

    • Swap A and A'.

user_167571740
  • take smallest cost node from each layer to get minimum cost path
  • take largest cost node from each layer to get maximum cost path
  • if target outside range between minimum and maximum then DONE
  • make minimum path the current path
  • select node with largest positive delta from node in path in same layer but which does not put path cost over target when swapped with node in current path. Swap.
  • repeat last step until no more swaps are possible.
user_165820
Related