¿Encontrar una solución óptima que minimice una restricción?

Llamemos a este problema el problema de Slinger-Bird (en realidad, el Slinger es análogo a un servidor y el ave a una solicitud, pero estaba teniendo una crisis nerviosa al pensarlo, ¡así que los cambié con la esperanza de obtener una perspectiva diferente!).

  • Hay S lanzadores de piedras (honderos) y B aves.
  • Los honderos no están dentro del rango uno del otro.
  • Cabalgar una vez puede matar a todas las aves a la vista de un hongo y consumirá una vez y una unidad de tiempo.

Estoy tratando de encontrar la solución óptima que minimice el tiempo y la cantidad de disparos que se necesitan para matar a las aves, dado un patrón particular de llegada de aves. Permítanme darles un ejemplo con números absolutos: 3 Slingers y 4 aves.

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 

y mis datos se parecen a esto:

 >> 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]} } ] 

Hay una serie de soluciones que podría pensar (Sx en t = k implica que el slinger Sx toma un tiro en el momento k):

  1. S1 en t = 1, S1 en t = 2, S1 en t = 3 <- Costo : 3 disparos + 3 unidades de tiempo = 6
  2. S1 en t = 2, S1 en t = 3 <- Costo : 2 disparos + 3 unidades de tiempo = 5
  3. S1 en t = 1, S3 en t = 2 <- Costo : 2 disparos + 2 unidades de tiempo = 4
  4. S3 en t = 4 <- Costo : 1 disparo + 4 unidades de tiempo = 5

A mí me parece que la solución 3 es la óptima en esto. Por supuesto, lo hice a mano (por lo que existe la posibilidad de que me haya perdido algo) pero no puedo pensar en una forma escalable de hacerlo. Además, me preocupa que haya casos de esquina porque la decisión de un tirador puede alterar la decisión de otros, pero como tengo la visión global, puede que no importe.

    ¿Cuál es una manera rápida y buena de resolver este problema en Python? Me está costando mucho encontrar una buena estructura de datos para hacer esto y dejar de lado el algoritmo para hacerlo. Estoy pensando en usar progtwigción dinámica porque esto parece involucrar la exploración espacial del estado pero estoy un poco confundido sobre cómo proceder. ¿Alguna sugerencia?

    Este no es un problema de asignación óptimo, porque los honderos matan a todas las aves a la vista.

    Tiene una función de objective bidimensional, por lo que puede haber una serie de compensaciones entre tomas y tiempo. Determinar el número mínimo de disparos para un límite de tiempo en particular es exactamente el problema de cobertura establecido (como sugiere mhum). El problema de la cobertura de conjunto es NP-duro y difícil de aproximar, pero en la práctica, la bifurcación y el enlace con el doble de la formulación de progtwigción lineal es bastante eficaz para encontrar el óptimo.

    Sugiero usar mapas de bits para los honderos y las aves, es decir,

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

    Entonces los datos de entrada se pueden escribir como

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

    La función de costo ahora se puede escribir así:

     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 

    Ahora es fácil encontrar las tomas óptimas calculando el mínimo de la función de costo:

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

    Esto imprime

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

    lo que significa que el óptimo es 4 unidades, cuando S1 y S3 (5 = 1 + 4) disparan a t = 2. Por supuesto, su solución también es posible, donde S1 dispara a t = 1 y S3 a t = 2, ambos tienen el mismo costo.

    Sin embargo, dado que el algoritmo usa fuerza bruta, que se ejecuta en todas las posibles secuencias de disparo, solo es rápido y factible cuando los conjuntos de datos son muy pequeños, como en su ejemplo.

    Supongo que sabes todos los números que das en el ejemplo cuando inicias el algoritmo, y no obtienes t2 después de terminar t1, etc.

    También asumo que dos honderos pueden disparar a la vez, aunque eso no debería importar mucho.

    En la primera opción, puede asignar un valor a cada celda, siendo amountOfBirdsInCell-time.

    Esto le da dos celdas con valores 1, siendo S1t1, S1t2, el rest es menor.

    Solo el tiempo de la última celda cuenta en tu puntuación, por lo que elegir la más antigua eliminará el tiempo de la siguiente ronda, por lo que es el momento más valioso. Esa es la primera elección.

    Ahora, elimina las aves muertas en esa primera selección de todas las células.

    Repita el proceso de determinación de valor para las celdas restantes. En su ejemplo, la celda S3t2 dará el resultado más alto, siendo 0.

    Repitiendo este proceso, obtienes las celdas más valiosas lo antes posible.

    Un bit importante que su ejemplo no cubre: si su primera selección más valiosa es en t2, la próxima selección más valiosa podría ser en t1 o t2, por lo que debe tenerlos en cuenta. Sin embargo, dado que t2 ya está confirmado, no debe tomar en cuenta su tiempo por su valor.

    Nunca he escrito en Python, solo estoy aquí debido a la etiqueta de algoritmo, así que aquí hay un pseudo código java / c-like:

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

    A menos que olvide algo, ahora tiene una combinación óptima de celdas en su colección de selecciones.

    Espero que este código tenga sentido para un progtwigdor de Python. Si alguien puede traducirlo, por favor hazlo! Y por favor, elimine este bit de texto y la mención anterior de java / c-pseudocode cuando lo haga.

    EDITAR por OP : Primera versión y no termina con las mejores celdas. Supongo que debe haber un error en mi código pero, sin embargo, estoy publicando aquí.

     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