Algoritmo para resolver problemas de asignación de recursos

Question

Hola, estoy creando un programa en el que los estudiantes se inscriben para un examen que se lleva a cabo en varias ciudades de todo el país. Al inscribir a los estudiantes, proporcionen una lista de las tres ciudades donde les gustaría dar el examen en orden de su preferencia. Entonces, un estudiante puede decir que su primera preferencia para un centro de examen es Nueva York, seguido de Chicago seguido de Boston.

Ahora, teniendo en cuenta que los centros de examen tienen capacidad limitada, no pueden acomodar la primera opción de cada estudiante. Sin embargo, intentaríamos proporcionar tantos estudiantes como su primera o segunda elección de centros y evitar a los estudiantes tener que dé el tercer centro de elección a un estudiante

Ahora cualquier idea de un algoritmo de ordenamiento que haría este proceso más eficiente. La manera simple de hacerlo sería ir primero a través de la lista de estudiantes de primera elección asignar tantos como posible, luego revisa la lista de segundas opciones y asigna. Sin embargo, esto puede llevar a que los estudiantes que son primeros en la lista obtengan su primer centro y los últimos estudiantes que obtienen su tercera opción o peor ninguno de sus opciones. Cualquier cosa que pueda hacer esto más eficiente

Answer 1

Suena como una variante del clásico stable marriages problem o college admission problem. La Wikipedia enumera un algoritmo de tiempo lineal (en el número de preferencias, O (n ²) en el número de personas) para el primero; el NRMP describe un efficient algorithm para este último.

Sospecho que si generas aleatoriamente preferencias de lugares de examen para estudiantes (un Fisher–Yates shuffle por lugar de examen) y luego aplicas el algoritmo de matrimonios estables, obtendrás una solución bastante justa y eficiente.

Answer 2

Este problema podría formularse como una instancia de minimum cost flow. Deje N ser el número de estudiantes. Deje que cada alumno sea un vértice de origen con capacidad 1. Deje que cada centro de examen sea un vértice de sumidero con capacidad, bueno, su capacidad. Haga un arco de cada alumno a su primera, segunda y tercera opción. Establezca el costo de los arcos de primera elección en 0; el costo de los arcos de segunda elección es 1; y el costo de los arcos de tercera elección a N + 1.

Encuentra un flujo de costo mínimo que mueve N unidades de flujo. Asumiendo que su solucionador devuelve una solución integral (debe, los LP de flujo son totalmente impersonales), cada alumno fluye una unidad a su centro asignado. Los costos minimizan la cantidad de asignaciones de tercera opción, rompiendo lazos por el número de asignaciones de segunda elección.

Answer 3

Hay una clase de algoritmos que abordan esta asignación de recursos limitados llamados subastas. Básicamente, en este caso, cada estudiante obtendría una cierta cantidad de dinero (un número que puede gastar), luego su software haría ofertas entre esos estudiantes. Puede usar una fórmula basada en preferencias.

Un ejemplo sería para los tiempos de tutoriales. Si anota sus preferencias, entonces haría una oferta efectiva más por esos momentos y menos por los tiempos que no desea. Entonces, si no obtienes tus preferencias, tienes más "dinero" para pujar por otros tutoriales.

Answer 4

Assignment problem.

se puede utilizar el algoritmo original desarrollado para esto: the Hungarian algorithm