Trouver la séquence optimale de questions pour minimiser le temps total des élèves

13

Supposons qu'il y ait une session de tutorat dans une université. Nous avons un ensemble de k questions Q={q1qk} et un ensemble de n élèves S={s1sn} . Chaque élève a un doute dans un certain sous-ensemble de questions, c'est-à-dire que pour chaque élève sj , soit QjQ l'ensemble des questions qu'un élève en doute. Supposons que 1jn:Qjϕ et 1jnQj=Q .

Tous les étudiants entrent dans la session de tutorat au début (à t=0 ). Maintenant, un étudiant quitte la session de tutorat dès que toutes les questions dans lesquelles il a un doute ont été discutées. Supposons que le temps nécessaire pour discuter de chaque question soit égal, disons 1 unité . Soit t j le temps passé par s j dans la session de tutoriel. Nous voulons trouver une permutation optimale σ dans laquelle les questions sont discutées ( q σ ( 1 )q σ ( n ) ) telles que la quantité T σ =tjsjσ(qσ(1)qσ(n)) est minimisé.Tσ=Σ1jntj

Je n'ai pas été en mesure de concevoir un algorithme de temps polynomial, ni de prouver la dureté NP

Nous pouvons définir une version de décision du problème

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

est l'ensemble des Q j . FQQj

On peut alors trouver le minimum en utilisant la recherche binaire sur C et trouver la valeur optimale σ en utilisant les affectations partielles σ en temps polynomial en utilisant un oracle pour T U T . Aussi, T U TN P car le σ optimal peut être utilisé comme un certificat que l'on peut vérifier facilement en temps polynomial.TσCσσTUTTUTNPσ

Ma question: N P est-elle complète ou pouvons-nous concevoir un algorithme de temps polynomial pour cela?TUT NP

Sidenote: Soit dit en passant, j'ai pensé à cette question après une session de tutorat, au cours de laquelle le TA a discuté des questions dans l'ordre normal cause de quoi de nombreux étudiants ont dû attendre jusqu'à la fin.q1qn

Exemple
Soit et n = 2 . Q 1 = { q 3 } et Q 2 = { q 1 , q 2 , q 3 } . On peut voir qu'un optimal σ = 3 , 1 , 2 parce que dans ce cas, s 1 feuilles après t 1 = 1 et s 2 feuilles après tk=3n=2Q1={q3}Q2={q1,q2,q3}σ=3,1,2s1t1=1s2 , donc somme 4. Cependant, si nous discutons des questions dans l'ordre1 , 2 , 3 , alors s 1 et s 2 fois attendre jusqu'à la fin et t 1 = t 2 = 3 , donc la somme est de 6.t2=3
1,2,3s1s2t1=t2=3

Vous êtes libre de résoudre le cas plus général où chaque question q i prend x i unités à discuter!qixi

skankhunt42
la source
Juste pour être clair: tous les élèves entrent-ils en même temps, ou entrent-ils à partir du moment où leur première question est posée?
Lézard discret
@Discretelizard Tous les élèves entrent en même temps au début (à t = 0).
skankhunt42
Dans la définition actuelle, les ensembles de questions sont uniques, c'est-à-dire qu'un ensemble de questions appartient à au plus un élève. Cela pourrait être une simplification raisonnable, mais je doute que cela soit réaliste (et je doute que cela fasse beaucoup pour la complexité du problème)
Lézard discret
Je suppose que deux étudiants pourraient avoir exactement le même ensemble de questions, donc le temps d'attente serait multiplié par deux.
gnasher729

Réponses:

1

Je soupçonne que le problème est NP-difficile. Je vais montrer comment transformer le problème de sorte qu'il soit fortement lié à un problème qui est NP-difficile. (Oui, tout cela est assez vague. Je pense que mon approche générale est correcte, mais je ne suis pas en mesure de continuer pour le moment.)TUT

Notons tout d'abord que le problème peut être reformulé comme suit:TUT

Etant donné un ensemble de questions de taille k , un ensemble de n sous - ensembles F QP ( Q ) et un nombre entier C , ne il existe une suite Σ : S 1 , ... , S k de telle sorte que, pour tout i { 1 , , k } :QknFQP(Q)CΣ:S1,,Ski{1,,k}

  1. et | S i | = i ; etSiQ|Si|=i
  2. pour tout j > i ; etSiSjj>i
  3. ?i=1k|{qFQqSi}|C

Notez que l'ensemble représente les premières i questions qui seront expliquées. Les conditions 1 et 2 garantissent que les sous-ensembles sont bien formés selon cette interprétation. La condition 3 compte le nombre d'élèves qui ne sont pas partis à chaque instant, ce qui correspond en fait au temps d'attente total de tous les élèves.Sii

Maintenant, nous limitons la taille des sous-ensembles dans àFQ ,sorteon peut représenter ces sousensembles en tant que bords sur un graphe où les sommets sont les éléments de Q . (Un résultat de dureté pour ce cas spécial suffit pour la dureté du problème général)2Q

Maintenant, le problème de la minimisation pour un seul i (c'est essentiellement ignorer la condition 2) est équivalent au problème suivant, que je surnomme « Double max |{qFQqSi}|i »:Double max k-vertex-cover

Etant donné un graphe non orienté et des entiers k et t , existe- t -il un ensemble de sommets V V de taille au plus k tels que l'ensemble { ( u , v ) E u V v V }G=(V,E)ktVVk{(u,v)EuVvV} a une taille d'au moins ?t

Ce problème est NP-difficile, car -clique est un cas particulier de ce problème, comme le montre cette réponse . Cependant, cela ne suffit pas pour prouver que T U T est NP-difficile, car nous devons trouver le maximum pour chaque i , tout en respectant la condition 2. Ces conditions ne sont pas satisfaites par chaque séquence Σ qui ne satisfait que les conditions 1 et 3: considérons le graphique sur 7 sommets avec deux cycles disjoints, l'un de taille 4 , l'autre de taille 3 . Pour i = 3, lekTUTiΣ743i=3 , la sélection de tous les sommets dans le cycle donne le maximum, tandis que la sélection de tous les sommets des 434-cycle est optimal pour .i=4

Il semble que la condition 2 rend le problème encore plus difficile et certainement pas plus facile, ce qui signifie que devrait être NP-difficile, mais je n'ai pas vu de méthode pour le prouver formellement.TUT

Donc, pour résumer, j'ai réduit la question à ce qui suit:

  • Est-il possible d'inclure la condition 2 pour compléter la preuve de dureté pour ?TUT

Note latérale: La formulation que j'ai donnée rend tentant d'essayer un algorithme itératif qui trouve dans la condition 2 de i = 1 k , en trouvant toutes les «extensions» maximales de tous les ensembles maximaux trouvés pour i - 1 . Cela ne conduit pas à un algorithme efficace, car la quantité d'ensembles maximum à une seule itération peut être exponentielle en k . De plus, je n'ai pas vu de méthode pour déterminer si un sous-ensemble pour certains i|{qFQqSi}|i=1ki1ki deviendrait finalement le maximum «global» pour éviter de vérifier une quantité exponentielle de sous-ensembles.

Lézard discret
la source