Algoritmo de optimización de espacio abierto

Como resultado de los cambios en la empresa, tenemos que reorganizar nuestro plan de sesión: una sala con 10 escritorios en ella. Algunos escritorios son más populares que otros por varias razones. Una solución sería dibujar un número de escritorio de un sombrero. Creemos que hay una mejor manera de hacerlo.Algoritmo de optimización de espacio abierto

Tenemos 10 escritorios y 10 personas. Vamos a dar a cada persona en este concurso 50 fichas hipotéticas para hacer una oferta en los escritorios. No hay límite de cuánto ofertas en un escritorio, puedes poner los 50, lo que sería "quiero sentarte solo aquí, punto". También puede decir "No me importa" dando a cada mesa 5 fichas.

Nota importante: nadie sabe lo que otras personas están haciendo. Cada uno tiene que decidir en base sólo en su/su mejor interés (suena familiar?)

Ahora digamos que hemos obtenido estos resultados hipotéticos:

# | Desk# >| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 
1 | Alise | 30 | 2 | 2 | 1 | 0 | 0 | 0 | 15 | 0 | 0 | = 50 
2 | Bob | 20 | 15 | 0 | 10 | 1 | 1 | 1 | 1 | 1 | 0 | = 50 
    ... 
10 | Zed | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | = 50

Ahora, lo que tenemos que encontrar es que uno (o más) Configuración (s) que nos da la máxima satisfacción (es decir, las personas obtienen los escritorios que querían teniendo en cuenta todas las ofertas y maximizando el total del grupo. Naturalmente, la suposición es que cuanto más pedimos en el escritorio más lo quiere)

Dado que solo hay 10 personas, creo que podemos forzarlo brutalmente buscando en todas las configuraciones posibles, pero me preguntaba si hay un algoritmo mejor para resolver este tipo de problemas.

Fuente

2010-06-11 Georgy Bolyuba

Puede estar relacionado con http://en.wikipedia.org/wiki/Stable_marriage_problem – polygenelubricants

Creo que en la práctica, es posible que desee algo más como una decepción mínima en lugar de la satisfacción máxima. O al menos alguna combinación. –

@Doug: gracias por la pista :). Es posible –

Parece que está mirando el Assignment Problem que se puede resolver usando Hungarian Algorithm. Este es un problema bien investigado y probablemente encontrará código en la web, listo para usar.

En su caso puede usar el costo = 50 - hacer una oferta y usar lo anterior (cualquier problema de solución a la asignación).

Fuente

2010-06-11 13:15:32

Estoy, francamente, sorprendido por su cultura. Parece que cada vez que se pregunta una pregunta en algoritmos, ¡simplemente se da cuenta del nombre del problema! –

@ Matthieu: Lo tomaré como un cumplido :-) ¡Gracias! Supongo que la razón es que estoy realmente interesado en los algoritmos. Con suerte, aún podré recordar todo esto en 5 años. Además, la gente generalmente pregunta alguna versión de un problema ya resuelto aquí, así que eso ayuda. –

@Matthieu: cualquiera puede google problemas como este. Son respuestas como [este (enlace)] (http://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element/2955527#2955527) que son realmente impresionantes. –

Aún más rápido, si tiene Excel también debe tener una versión de SOLVER disponible. Simplemente configure su matriz de ofertas (10x10 con ofertas), matriz de asignaciones (10x10 con asignaciones 0/1), use sumproducto (ofertas, asignaciones) para calcular el valor de una tarea, haga que su función objetivo y agregue restricciones para que haya solo una asignación de personas a escritorios y escritorios para las personas. Asegúrese de tener las opciones> casilla "modelo lineal" marcada y "asumir no negativo" y resuelva. Acabo de configurar un problema de muestra de 10x10, parece funcionar bien.

Fuente

2010-06-11 21:01:04 Grembo

Algoritmo de optimización de espacio abierto

Respuesta

Cuestiones relacionadas