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

Supposons qu'il y ait une session de tutorat dans une université. Nous avons un ensemble de $k$ questions $Q = \{ q_1 \ldots q_k \}$ et un ensemble de $n$ élèves $S = \{ s_1 \ldots s_n \}$ . Chaque élève a un doute dans un certain sous-ensemble de questions, c'est-à-dire que pour chaque élève $s_j$ , soit $Q_j \subseteq Q$ l'ensemble des questions qu'un élève en doute. Supposons que $\forall 1 \leq j \leq n: Q_j \neq \phi$ et $\bigcup_{1\leq j\leq n}Q_j = 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 σ =$^*$$t_j$$s_j$$\sigma$$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ est minimisé.$T_\sigma = \Sigma_{1\leq j \leq n}t_j$

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

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

où est l'ensemble des Q j . $\mathcal{F}_Q$$Q_j$

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 T ∈ N P car le σ optimal peut être utilisé comme un certificat que l'on peut vérifier facilement en temps polynomial.$T_\sigma$$C$$\sigma$$\sigma$$\mathsf{TUT}$$\mathsf{TUT} \in \mathsf{NP}$$\sigma$

Ma question: N P est-elle complète ou pouvons-nous concevoir un algorithme de temps polynomial pour cela?$\mathsf{TUT}$ $\mathsf{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.$q_1 \ldots q_n$

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 $k=3$$n=2$$Q_1 = \{q_3\}$$Q_2 = \{q_1, q_2, q_3\}$$\sigma = \langle 3, 1, 2 \rangle$$s_1$$t_1 = 1$$s_2$ , donc somme 4. Cependant, si nous discutons des questions dans l'ordre ⟨ 1 , 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.$t_2 = 3$
$\langle 1, 2, 3\rangle$$s_1$$s_2$$t_1 = t_2 = 3$

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

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.)$\mathsf{TUT}$

Notons tout d'abord que le problème peut être reformulé comme suit:$\mathsf{TUT}$

Etant donné un ensemble de questions de taille k , un ensemble de n sous - ensembles F Q ⊆ P ( Q ) et un nombre entier C , ne il existe une suite Σ : ⟨ S 1 , ... , S k ⟩ de telle sorte que, pour tout i ∈ { 1 , … , k } :$Q$$k$$n$$\mathcal{F}_Q\subseteq \mathcal{P}(Q)$$C$$\Sigma : \langle S_1,\ldots, S_k\rangle$$i \in\{1,\ldots,k\}$

1. et | S i | = i ; et$S_i\subseteq Q$$|S_i|=i$
2. pour tout j > i ; et$S_i \subset S_j$$j>i$
3. ?$\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq 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.$S_i$$i$

Maintenant, nous limitons la taille des sous-ensembles dans à$\mathcal{F}_Q$ ,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)$2$$Q$

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 « $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i$ »:$\mathsf{\text{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)$$k$$t$$V'\subseteq V$$k$$\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ 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 = $k$$\mathsf{TUT}$$i$$\Sigma$$7$$4$$3$$i=3$ , la sélection de tous les sommets dans le cycle donne le maximum, tandis que la sélection de tous les sommets des $3$$4$-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.$\mathsf{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 ?$\mathsf{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 $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i=1\ldots k$$i-1$$k$$i$ deviendrait finalement le maximum «global» pour éviter de vérifier une quantité exponentielle de sous-ensembles.