Looking for an optimal solution that minimizes the limitation?

Question

We call this problem the Slinger-Bird problem (in fact, Slinger is similar to the server and the bird for the request, but I had a nervous breakdown thinking about it, so I changed them, hoping to get a different perspective!),

• There are S masons (slingers) and birds B.
• Slingers are not within one another.
• Slinging can one day kill all birds in the field of view of the slinger and will consume one shot and a unit of time

I am trying to figure out the optimal solution that minimizes the time and number of shots needed to kill the birds, taking into account the specific picture of the birds. Let me give you 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 is as follows:

 >> 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 that I might think (Sx at t = k means that slinger Sx takes a picture at time k):

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

It seems to me that solution 3 is optimal in this. Of course, I did it manually (so there is a chance that I might have missed something), but I can't think of a scalable way to do this. In addition, I am worried that there are angular cases, because the decision of one shooter may change the decision of others, but since I have a global view, maybe it does not matter.

What is a quick and efficient way to solve this problem in python? It’s hard for me to find a good data structure to do this, while keeping the algorithm in place for this. I think about using dynamic programming because it seems to be related to space exploration, but I'm a little confused about how to proceed. Any suggestions?

Answer 1

This is not a problem for optimal use, because slings kill all birds.

You have a two-dimensional objective function, so there can be many trade-offs between frames and time. Determining the minimum number of frames for a given time interval is a precisely defined cover problem (as mhum suggests). The set cover problem is NP-rigid and difficult to approximate, but in practice the branch and the use of dual formulation of linear programming are very effective in finding the optimal one.

Answer 2

I suggest using bitmaps for slings and birds, i.e.

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

Then the input can be written as

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

Now the cost function can be written as follows:

 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 is easy to find the optimal images by calculating the minimum cost function:

 from itertools import product shot_sequences = product(*([range(7)]*len(bird_data))) print min((cost(shots), shots) for shots in shot_sequences) 

Will print

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

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

However, since the algorithm uses brute force, running through all possible sequences of shots, it runs only quickly and practically when the data sets are very small, as in your example.

Answer 3

I assume that you know all the numbers that you give in the example when you run the algorithm, and do not get t2 after the end of t1, etc.

I also suggest that two lines can shoot at once, although this does not really matter.

The first time you select, you can assign a value to each cell, which is the value of the OfBirdsInCell-time sum.

This gives you two cells with values ​​of 1 being S1t1, S1t2, the rest are below.

Only the time of the last cell is calculated in your account, so choosing the earliest will delete the time on it for the next round, making it the most valuable time. This is the first choice.

Now remove the birds killed in this first selection from all the cages.

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

Repeating this process, you get the most valuable cells in the very near future.

One important bit in your example does not apply: if your first most valuable choice is at t2, the next most valuable choice may be at t1 or t2, so you should consider this. However, since t2 has already been confirmed, you should not consider their time for their value.

I never wrote in python, I'm just here because of an algorithm tag, so there is java / c-like pseudo code here:

 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); } 

If I didn’t forget something, now you have the optimal combination of cells in your collection of choice.

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

EDIT by OP : The first version and does not contain the best cells. I suppose this should be a mistake in my code, but nonetheless I post 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