6
$\begingroup$

I am working on a project that requires to find the minimum number of steps to move ants from source to sink in a graph; one step is the movement of all ants from one node to the next of the graph. Only one ant per node

I already solved the problem of finding all possible disjoint paths. The issue I have is selecting the number of ants to send per path.

Here is an example: enter image description here

every colour is a disjoint path. Given 12 ants, the best solution is to send 4 along gray, 3 along black, 3 along red, 1 along yellow and 1 along blue.

The only way that I found for now is a greedy solution but this will not scale well at all. I am not too good at math and I am sure there must be some smart formula to help me solve this problem. I tried to use the total length of the paths to help me solve it but I can't figure it out... Any help or resource is greatly appreciated

My current take: I am calculating solutions by seeing how many ants go through the shortest path (grey) while one goes through a second one. So for "black" is 2 as len(n) / len(shortest). This helps me create proportions. Moreover I have the paths stored in increasing order. I do not send ants through a edge with increased len unless all previous edges are at capacity. if more edges have the same len I treat them as one (send same amount through them). This method seems to work but only with small tweaks in numbers when I find a solution. I feel like there is some sort of mistake but can't really pinpoint it.

$\endgroup$
3
  • 1
    $\begingroup$ This may come under the heading of "network flows" although it differs from the netwrok flow problems I'm familiar with in that only one unit of flow can be in any given arc at any given time. $\endgroup$ Sep 4, 2020 at 0:04
  • 1
    $\begingroup$ This is more of a queueing theory flavour. Once the paths are identified, it's like saying each one is a queue (a processor) and the grey processor completes a job in 1 step and the red processor completes in 2 steps and the yellow processor completes in 3 steps, etc. $\endgroup$
    – JimN
    Sep 4, 2020 at 10:28
  • $\begingroup$ If there are many ways to decompose the graph into a set of disjoint paths, it may not be easy to find the best way. $\endgroup$
    – usul
    Oct 2, 2021 at 17:55

1 Answer 1

0
$\begingroup$

I'm thinking of this from the perspective of how many ants can you accommodate in $s$ steps. Suppose your disjoint source-to-sink paths have lengths $(p_1, \ldots, p_n)$ listed in nondecreasing order. The number of ants you can handle in $s$ steps is then, using the integer floor function, $$ \left\lfloor \frac{s}{p_1} \right\rfloor + \cdots + \left\lfloor \frac{s}{p_n} \right\rfloor.$$

Your example has path lengths $(1,2,2,3,4)$. In five steps, you can handle $$ \left\lfloor \frac{5}{1} \right\rfloor + \left\lfloor \frac{5}{2} \right\rfloor + \left\lfloor \frac{5}{2} \right\rfloor + \left\lfloor \frac{5}{3} \right\rfloor + \left\lfloor \frac{5}{4} \right\rfloor = 5+2+2+1+1 = 11$$ ants, while with $s=6$ steps you can handle $$ \left\lfloor \frac{6}{1} \right\rfloor + \left\lfloor \frac{6}{2} \right\rfloor + \left\lfloor \frac{6}{2} \right\rfloor + \left\lfloor \frac{6}{3} \right\rfloor + \left\lfloor \frac{6}{4} \right\rfloor = 6+3+3+2+1 = 15.$$ So for 12 ants, you need 6 steps. To make something algorithmic, set up the plan for the optimal 15 ants in 6 steps and then ignore, say, the first 3, giving here (3 gray, 3 black, 3 red, 2 yellow, 1 blue). Or the last 3, giving (6 gray, 3 black, 3 red).

In general, compute the $\lfloor s/p_i \rfloor$ sum for increasing $s$ until you first reach or exceed the number of ants you need, make the allocation from the formula for the optimal number that can be handled, and then ignore the appropriate number of ants.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.