Finding an optimal solution that minimizes a constraint?

Question

Let us call this problem the Slinger-Bird problem (actually the Slinger is analogous to a server and the bird to a request but I was having a nervous breakdown thinking about it so I changed them hoping to get a different perspective!).

• There are S stone throwers (slingers) and B birds.
• The slingers are not within the range of each other.
• Slinging once can kill all birds within the sight of a slinger and will consume one shot and one time unit

I am trying to figure out the optimal solution that minimizes the time and the number of shots it takes to kill the birds given a particular arrival pattern of birds. Let me give an example with absolute numbers: 3 Slingers and 4 birds.

        Time        1            2            3           4             5
Slinger
S1                B1, B2     B1, B2, B3       B4
S2                               B1         B1, B2      B3,B4     
S3                  B1         B3, B4                 B1,B2,B3,B4

and my data looks like this:

>> print t
[
  {
    1: {S1: [B1, B2], S2: [], S3: [B1]}, 
    2: {S1: [B1, B2, B3], S2: [B1], S3: [B3, B4]},
    3: {S1: [B4], S2: [B1,B2], S3: []},
    4: {S1: [], S2: [B3, B4], S3: [B1, B2, B3, B4]}
  }
]

There are a number of solutions I could think of (Sx at t=k implies that slinger Sx takes a shot at time k):

1. S1 at t=1, S1 at t=2, S1 at t=3 <- Cost: 3 shots + 3 time units = 6
2. S1 at t=2, S1 at t=3 <- Cost: 2 shots + 3 time units = 5
3. S1 at t=1, S3 at t=2 <- Cost: 2 shots + 2 time units = 4
4. S3 at t=4 <- Cost: 1 shot + 4 time units = 5

To me it appears that solution 3 is the optimal one in this. Of course, I did this by hand (so there is a possibility I may have missed something) but I cannot think of a scalable way of doing this. Also, I am worried there are corner cases because the decision of one shooter might alter the decision of others but because I have the global view, may be it does not matter.

What is a fast and good way to solving this problem in python? I am having a hard time coming up with a good data structure to do this leave alone the algorithm to do it. I am thinking of using dynamic programming because this seems to involve state space exploration but am a bit confused on how to proceed. Any suggestions?

Answer 1

This is not an optimal assignment problem, because slingers kill all birds in view.

You have a two-dimensional objective function, so there can be a number of tradeoffs between shots and time. Determining the minimum number of shots for a particular time limit is exactly the set cover problem (as mhum suggests). The set cover problem is NP-hard and hard to approximate, but in practice, branch and bound using the dual of the linear programming formulation is quite effective in finding the optimum.

Answer 2

I suggest using bitmaps for the slingers and birds, i.e.

S1 = B1 = 1, S2 = B2 = 2, S3 = B3 = 4, B4 = 8

Then the input data can be written as

bird_data = [[3, 0, 1], [7, 1, 12], [8, 3, 0], [0, 12, 15]]

The cost function can now be written like this:

def cost(shots):
    hit = units = 0
    for show, shot in zip(bird_data, shots):
        units += 1
        for n, birds in enumerate(show):
            if shot & 1:
                units += 1
                hit |= birds
                if hit == 15: # all are hit
                    return units
            shot >>= 1
    return 99 # penalty when not all are hit

Now it's easy to find the optimal shots by calculating the minimum of the cost function:

from itertools import product

shot_sequences = product(*([range(7)]*len(bird_data)))

print min((cost(shots), shots) for shots in shot_sequences)

This prints

(4, (0, 5, 0, 0))

which means the optimum is 4 units, when S1 and S3 (5 = 1 + 4) fire at t=2. Of course your solution is also possible, where S1 fires at t=1 and S3 at t=2, both have the same cost.

However, since the algorithm is using brute force, running over all possible shot sequences, it is only fast and feasible when the data sets are very small, like in your example.

Answer 3

I'm assuming you know all the numbers you give in the example when you're starting the algorithm, and don't get t2 after finishing t1 etc.

I also assume two slingers can fire at once, though that shouldn't matter much.

At the first choice, you can assign a value to each cell, being amountOfBirdsInCell-time.

This gives you two cells with values 1, being S1t1, S1t2, the rest is lower.

Only the time of the last cell counts in your score, so picking the earliest one will remove the time on it for the next round, making it the most valuable time. That's the first pick.

Now, remove the birds killed in that first pick from all cells.

Repeat the value determining process for the remaining cells. In your example, cell S3t2 will give the highest result, being 0.

Repeating this process, you get the most valuable cells at the earliest times.

One important bit your example doesn't cover: If your first most valuable pick is at t2, the next most valuable pick might be at t1 or t2, so you should take those into account. However, since t2 is already confirmed, you should not take their time into account for their value.

I've never written in python, I'm just here because of the algorithm tag, so here's some java/c-like pseudo code:

highestCellTime = 0;
while(birdsRemain)
{
    bestCell;

    for(every cell that has not been picked yet)
    {
        currentCellValue = amountOfBirds;
        if(currentCellTime > highestCellTime)
        {
            currentCellValue = currentCellValue - currentCellTime;
        }

        if(currentCellValue < bestCellValue)
        {
            bestCell = thisCell;
        }
        else if(currentCellValue == bestCellValue && currentCellTime < bestCellTime)
        {
            bestCell = thisCell;
        }
    }
    addCellToPicks(bestCell);
    removeBirdsFromOtherCells(bestCellBirds);
}

Unless I forgot something, you now have an optimal combination of cells in your picks collection.

I hope this code makes sense to a python programmer. If someone can translate it, please do! And please remove this bit of text and the earlier mention of java/c-pseudocode when you do.

EDIT by OP: First version and does not end up with the best cells. I am guessing it must be a bug in my code but nevertheless I am posting here.

import math

cellsNotPicked = range(0,12)
cellToBird = {
    0: [1, 2],
    1: [],
    2: [1],
    3: [1,2,3],
    4: [1],
    5: [3,4],
    6: [4],
    7: [1,2],
    8: [],
    9: [],
    10: [3,4],
    11: [1,2,3,4]
}

picks = []

def getCellValue(cell):
    return len(cellToBird[cell])

def getCellTime(cell):
    return int(math.floor(cell / 3)) + 1

birdsRemain = 4

while(birdsRemain > 0):

    bestCell = 0;

    for thisCell in cellsNotPicked:

        currentCellValue = getCellValue(thisCell);

        currentCellTime = getCellTime(thisCell)
        highestCellTime = getCellTime(bestCell)

        if(currentCellTime > highestCellTime):
            currentCellValue = currentCellValue - currentCellTime;

        if(currentCellValue < getCellValue(bestCell)):
            bestCell = thisCell
        elif (currentCellValue == getCellValue(bestCell)) and (currentCellTime < getCellTime(bestCell)):
            bestCell = thisCell

    picks.append(bestCell)
    cellsNotPicked.remove(bestCell)

    birdsToRemove = cellToBird[bestCell]

    for key in cellToBird:
        for bird in birdsToRemove:
            try:
                cellToBird[key].remove(bird)
                birdsRemain -= 1
            except:
                pass

print picks