algorithm - ¿Qué tipo de algoritmo debería usar para clasificar estudiantes?

sorting lua

Question

En un programa que genera grupos aleatorios de estudiantes, le doy al usuario la opción de obligar a los estudiantes específicos a agruparse y también a evitar que los estudiantes se emparejen. He intentado durante dos días hacer mi propio algoritmo para lograr esto, pero me pierdo en toda la recursión. Estoy creando el programa en Lua, pero podré comprender cualquier tipo de pseudo código. Aquí hay un ejemplo de cómo se ordenan los estudiantes:

students = {
    Student1 = {name=Student1, force={"Student2"}, deny={}};
    Student2 = {name=Student2, force={"Student1","Student3"}, deny={}};
    Student3 = {name=Student3, force={"Student2"}, deny={}};
}-- A second name property is given in the case that the student table needs to be accessed by students[num] to retrieve a name

Luego creo tablas temporales:

forced = {}--Every student who has at least 1 entry in their force table is placed here, even if they have 1 or more in the deny table
denied = {}--Every student with 1 entry for the deny table and none in the force table is placed here
leftovers = {}--Every student that doesn''t have any entries in the force nor deny tables is placed here
unsortable = {}--None are placed here yet -- this is to store students that are unable to be placed according to set rules(i.e. a student being forced to be paired with someone in a group that also contains a student that they can''t be paired with

SortStudentsIntoGroups()--predefined; sorts students into above groups

Después de colocar a cada alumno en esos grupos (tenga en cuenta que también permanecen en la mesa de los alumnos), empiezo insertando a los alumnos forzados a formar parejas (bueno, lo intenté), inserto alumnos que tienen uno o más entradas en la tabla de denegación en grupos donde pueden ubicarse, y simplemente llene los grupos restantes con las sobras.

Hay un par de cosas que serán de alguna utilidad:

numGroups--predefined number of groups
maxGroupSize--automatically calculated; quick reference to largest amount of students allowed in a group
groups = {}--number of entries is equivalent to numGroups(i.e. groups = {{},{},{}} in the case of three groups). This is for storing students in so that the groups may be displayed to the end user after the algorithm is complete.

sortGroups()--predefined function that sorts the groups from smallest to largest; will sort largest to smallest if supplied a true boolean as a parameter)

Como dije antes, no tengo idea de cómo configurar un algoritmo recursivo para esto. Cada vez que trato de insertar a los estudiantes forzados, termino obteniendo el mismo estudiante en múltiples grupos, los pares forzados no se emparejan, etc. También tenga en cuenta los formatos. En la tabla de fuerza / denegación de cada alumno, se da el nombre del alumno objetivo, no una referencia directa al alumno. ¿Qué tipo de algoritmo debería usar (si existe uno para este caso)? Cualquier ayuda es muy apreciada.

Answer 1

Me parece que estás enfrentando un problema NP-Hard aquí.

Esto es equivalente al problema de la coloración de gráficos con k colores, donde los bordes son las listas de negación.

Graph Coloring:

Given a graph G=(V,E), and an integer `k`, create coloring function f:V->{1,2,..,k} such that:
f(v) = f(u) -> (v,u) is NOT in E

La reducción de la coloración gráfica a su problema:
Dado un problema de coloreado de gráficos (G,k) donde G=(V,E) , crea una instancia de tu problema con:

students = V
for each student: student.denial = { student'' | for each edge (student,student'')}
#groups = k

Intuitivamente, cada vértice está representado por un alumno, y un alumno niega a todos los alumnos que haya un borde entre los vértices que los representan. La cantidad de grupos es la cantidad dada de colores.

Ahora, dada una solución a su problema, obtenemos k grupos que si el alumno deniega al alumno v , no están en el mismo grupo, pero esto es lo mismo que colorear u y v en diferentes colores, por lo que para cada borde (u, v) en el gráfico original, u v están en diferentes colores.
A la inversa, es similar

Entonces, obtuvimos una reducción polinómica del problema de la coloración gráfica y, por lo tanto, encontrar una solución óptima para su problema es NP-Hard, y no hay una solución eficiente conocida para este problema , y la mayoría cree que no existe.

Algunas alternativas son el uso de heurísticas tales como los algoritmos genéticos que no proporcionan una solución óptima o el uso de enfoques de fuerza bruta que consumen mucho tiempo (que no son factibles para una gran cantidad de estudiantes).
La fuerza bruta generará todas las divisiones posibles para k grupos, y verificará si es una solución factible; al final, se elegirá la mejor solución encontrada.