Elegir horario para maximizar el número de estudiantes que puede atender a por lo menos una ranura de tiempo

Question

Tengo el siguiente (mundo real!!!) problema que es más fácilmente se describe mediante un ejemplo.

Pido a mis seis estudiantes de cuándo es el mejor momento para mantener las horas de oficina sería. Yo les doy cuatro opciones, y dicen que me van a tener dos horas en total. La encuesta los resultados son como sigue (1 sí, 0 no):

$$\begin{array}{l|c|c|c|c} \text{Name} & 9 \text{ am} & 10 \text{ am} & 11 \text{ am} & 12 \text{ pm} \\ \hline \text{Alice} & 1 & 1 & 0 & 0 \\ \text{Bob} & 1 & 1 & 0 & 1 \\ \text{Charlotte} & 1 & 1 & 0 & 1 \\ \text{Daniel} & 0 & 1 & 1 & 1 \\ \text{Eve} & 0 & 0 & 1 & 1 \\ \text{Frank} & 0 & 0 & 1 & 0 \\ \hline \text{Total} & 3 & 4 & 3 & 4 \end{array}$$

Ingenuamente, uno puede elegir las columnas 2 y 4, que tienen los mayores totales. Sin embargo, la solución que permite que la mayoría de personas distintas a asistir es escoger las columnas 2 y 3.

En la práctica, sin embargo, he ~30 posibles intervalos de tiempo y más de 100 estudiantes, y quiere recoger, digamos, cinco diferentes intervalos de tiempo para las horas de oficina. ¿Cómo elegir los intervalos de tiempo que maximizar el número de los distintos alumnos que pueden asistir?

Answer 1

En general, este problema es la cobertura máxima problema, que es NP-duro, así que no vas a ser capaz de encontrar la solución óptima mediante cualquier método sustancialmente más rápido que la fuerza bruta. (Como ya he mencionado, por un problema de su tamaño, la fuerza bruta es todavía factible.)

Sin embargo, una modificación de su estrategia (a elegir los intervalos de tiempo con los totales más altos) se comporta razonablemente bien.

Que en realidad no hacen sentido para elegir todos los intervalos de tiempo con los totales más altos de inmediato: si todos tienen los mismos alumnos, entonces esto no es mejor que simplemente elegir uno de los intervalos de tiempo. En lugar de ello, podemos:

1. Elija un intervalo de tiempo con el mayor número total de estudiantes.
2. Quitar todos los estudiantes que se puede hacer para que el intervalo de tiempo considerado. Calcular los totales para el resto de los estudiantes.
3. Repita los pasos 1 y 2 hasta que haya elegido $k=5$ intervalos de tiempo.

Según el artículo de la wikipedia, este algoritmo se logra una aproximación de la proporción de $1 - \frac1e$; es decir, si se puede llegar a $N$ de los estudiantes con la elección óptima de los intervalos de tiempo, este algoritmo va a llegar, al menos, $(1 - \frac1e)N$ de los estudiantes.

Hay otras posibles soluciones aproximadas; por ejemplo, no es el gran paso de la heurística, que considera todas las opciones de $p$ intervalos de tiempo en cada paso, en oposición a todos los intervalos temporales individuales. (Al $p=1$, es el algoritmo anterior; al $p=k$, es simplemente la fuerza bruta.) Ningún algoritmo rápido ha garantizado un mejor desempeño que $(1 - \frac1e)N$, pero que puede funcionar mejor en algunos casos.

Answer 2

Con esos números, la fuerza bruta es todavía factible. Usted tiene 30 elija 5 = 142506 diferentes combinaciones. Creo que no hay ningún algoritmo de otros que la fuerza bruta que está garantizado para conseguir la mejor solución, pero una heurística sería la de organizar a los estudiantes en grupos de menos de disponibilidad para la mayoría. A continuación, el rango de las ranuras de tiempo por la forma en que muchos de los que menos disponible, los estudiantes coinciden, romper los lazos de cuántos de segundo no sea disponible, etc. Tomar la mejor ranura de tiempo de acuerdo a ese criterio. Quitar todos los estudiantes que pueden hacer que la ranura de tiempo, y aplicar el mismo algoritmo para el resto de las franjas horarias y los estudiantes, y continuar hasta que se haya alcanzado el número máximo de ranuras de tiempo. En tu ejemplo, Frank es el menos disponible estudiante, para las 11 de la mañana, como el único espacio de tiempo se puede hacer, es la primera opción. Esto deja a Alice, Bob y Charlotte sin una ranura de tiempo, y de ellos, Alice es el menos disponible. Las 9 de la mañana y las 10 de la mañana acogen a Alice, así que usted puede tomar de uno (aunque si se toma en cuenta a los estudiantes que se han eliminado en los pasos anteriores, entonces las 10 de la mañana gana).

Se pueden combinar los dos: el uso de la heurística hasta llegar a los pequeños números suficientes de que estás de acuerdo con el uso de la fuerza bruta.

Otra heurística es mirar a la agrupación (hay un conjunto de estudiantes que en su mayoría está disponible en la mañana y otra por la noche), y de la recogida de las ranuras de tiempo en diferentes grupos.

Answer 3

Prácticamente hablando, simplemente variar la oficina horas cada semana.