Encontrar la secuencia óptima de preguntas para minimizar el tiempo total del estudiante

13

Supongamos que hay una sesión de tutoría en una universidad. Tenemos un conjunto de kk preguntas Q = { q 1 ... q k }Q={q1qk} y un conjunto de nn estudiantes S = { s 1 ... s n }S={s1sn} . Cada estudiante tiene una duda en un determinado subconjunto de preguntas, es decir, para cada estudiante s jsj , y mucho Q JQQjQ el conjunto de preguntas que un estudiante tiene una duda. Suponga que 1 j n : Q jφ1jn:Qjϕ y 1 j n Q j = Q1jnQj=Q .

Todos los estudiantes ingresan a la sesión de tutoría al principio (en t = 0t=0 ). Ahora, un estudiante deja la sesión de tutoría tan pronto como se hayan discutido todas las preguntas en las que tiene dudas. Suponga que el tiempo necesario para discutir cada pregunta es igual, digamos 1 unidad . Deje que t j sea ​​el tiempo empleado por s j en la sesión de tutoría. Queremos encontrar una permutación óptima σ en la que se discutan las preguntas ( q σ ( 1 ) ... q σ ( n ) ) como la cantidad T σ =tjsjσ(qσ(1)qσ(n))Σ 1 j n t j se minimiza.Tσ=Σ1jntj

No he podido diseñar un algoritmo de tiempo polinómico ni probar la dureza N P.NP

Podemos definir una versión decisión del problema T T T = { k , n , M Q , C | sigma : T sigmaC }

TUT={k,n,FQ,Cσ:TσC}

donde F Q es el conjunto de Q j 's. FQQj

Entonces podemos averiguar el mínimo T sigma mediante la búsqueda binaria en C y averiguar la óptima σ utilizando las cesiones parciales de sigma en tiempo polinomial usando un oráculo para T T T . Además, T U TN P porque el σ óptimo se puede usar como un certificado que podemos verificar fácilmente en tiempo polinómico.TσCσσTUTTUTNPσ

Mi pregunta: ¿ T U T N P -completo o podemos diseñar un algoritmo de tiempo polinómico para ello?TUT NP

Nota al margen: Por cierto, pensé en esta pregunta después de una sesión de tutoría real, en la que el TA discutió las preguntas en el orden normal q 1 ... q n debido a que muchos estudiantes tuvieron que esperar hasta el final.q1qn

Ejemplo
Let k = 3 y n = 2 . Q 1 = { q 3 } y Q 2 = { q 1 , q 2 , q 3 } . Podemos ver que una óptima σ = 3 , 1 , 2 porque en ese caso, s 1 hojas después de t 1 = 1 y s 2 hojas después de tk=3n=2Q1={q3}Q2={q1,q2,q3}σ=3,1,2s1t1=1s22 = 3 , por lo que suma es 4. Sin embargo, si se discuten las preguntas en el orden1 , 2 , 3 , entonces s 1 y s 2 ambos tienen que esperar hasta el final y t 1 = t 2 = 3 , por lo suma es 6.t2=3
1,2,3s1s2t1=t2=3

∗ ¡ Eres libre de resolver el caso más general donde cada pregunta q i toma x i unidades para discutir!qixi

skankhunt42
fuente
Para ser claros: ¿todos los estudiantes ingresan al mismo tiempo, o ingresan desde el momento en que se hace su primera pregunta?
Lagarto discreto
@Discretelizard Todos los estudiantes ingresan al mismo tiempo al principio (en t = 0).
skankhunt42
En la definición actual, los conjuntos de preguntas son únicos, es decir, un conjunto de preguntas pertenece a un máximo de un alumno. Esto podría ser una simplificación razonable, pero dudo que sea realista (y dudo que esto haga mucho por la complejidad del problema)
Lagarto discreto
Supongo que dos estudiantes podrían tener exactamente el mismo conjunto de preguntas, por lo que el tiempo de espera se multiplicaría por dos.
gnasher729

Respuestas:

1

Sospecho que el problema T U T es NP-hard. Mostraré cómo transformar el problema de modo que esté fuertemente relacionado con un problema que es NP-hard. (Sí, todo esto es bastante vago. Básicamente creo que mi enfoque general es correcto, pero actualmente no puedo continuar).TUT

Primero, tenga en cuenta que el problema T U T puede reformularse de la siguiente manera:TUT

Dado un conjunto de preguntas Q de tamaño k , un conjunto de n subconjuntos F QP ( Q ) y un entero C , que hace existe una secuencia Σ : S 1 , ... , S k tal que, para todo i { 1 , ... , k } :QknFQP(Q)CΣ:S1,,Ski{1,,k}

  1. S iQ y | S i | = i ; ySiQ|Si|=i
  2. SiSjSiSj for all j>ij>i; and
  3. ki=1|{qFQqSi}|Cki=1|{qFQqSi}|C ?

Note that the set SiSi represent the first ii questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.

Now, we restrict the size of the subsets in FQFQ to 22, so we can represent these subsets as edges on a graph where the vertices are the elements from QQ. (A hardness result for this special case is sufficient for hardness of the general problem)

Now, the problem of minimizing |{qFQqSi}||{qFQqSi}| for a single ii (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub 'Double max k-vertex-coverDouble max k-vertex-cover':

Given an undirected graph G=(V,E)G=(V,E) and integers kk and tt, does there exist a set of vertices VVVV of size at most kk such that the set {(u,v)EuVvV}{(u,v)EuVvV} has a size of at least tt?

This problem is NP-hard, since kk-clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove TUTTUT to be NP-hard, since we need to find the maximum for every ii, while respecting condition 2. This conditions are not satisfied by every sequence ΣΣ that satisfies only condition 1 and 3: consider the graph on 77 vertices with two disjoint cycles, one of size 44, the other size 33. For i=3i=3, selecting all vertices in the 33-cycle gives the maximum, while selecting all vertices of the 44-cycle is optimal for i=4i=4.

It seems that condition 2 makes the problem even harder and most certainly not easier, which means TUTTUT should be NP-hard, but I haven't seen a method to formally prove this.

So, to summarize, I have reduced the question to the following:

  • Is it possible to include condition 2 to complete the hardness proof for TUTTUT?

Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds |{qFQqSi}||{qFQqSi}| under condition 2 from i=1ki=1k, by finding all maximum 'extenstions' of all found maximum sets for i1i1. This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in k. Additionally, I have not seen a method to determine whether a subset for some i would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.

Discrete lizard
fuente