Finden einer optimalen Folge von Fragen, um die Gesamtstudienzeit zu minimieren

Angenommen, es gibt eine Tutorialsitzung an einer Universität. Wir haben eine Menge von $k$ Fragen $Q = \{ q_1 \ldots q_k \}$ und eine Menge von $n$ Schülern $S = \{ s_1 \ldots s_n \}$ . Jeder Schüler hat Zweifel an einer bestimmten Teilmenge von Fragen, dh für jeden Schüler $s_j$ sei $Q_j \subseteq Q$ die Menge von Fragen, an denen ein Schüler zweifelt. Es sei angenommen, dass $\forall 1 \leq j \leq n: Q_j \neq \phi$ und $\bigcup_{1\leq j\leq n}Q_j = Q$ .

Alle Schüler nehmen zu Beginn an der Übungsstunde teil (bei ). Nun verlässt ein Schüler die Übungsstunde, sobald alle Fragen besprochen wurden, an denen er Zweifel hat. Angenommen, die Zeit für die Erörterung jeder Frage ist gleich, sagen wir 1 Einheit ∗ . Sei t j die Zeit, die s j in der Lerneinheit verbracht hat. Wir wollen eine optimale Permutation σ herausfinden, in der Fragen diskutiert werden ( q σ ( 1 ) … q σ ( n ) ), wie die Größe T σ$t = 0$$^*$$t_j$$s_j$$\sigma$$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ minimiert.$T_\sigma = \Sigma_{1\leq j \leq n}t_j$

Ich war nicht in der Lage, einen polynomialen Zeitalgorithmus zu entwerfen oder die -Härte zu beweisen .$\mathsf{NP}$

Wir können eine Entscheidung Version des Problems definieren

wobei die Menge von Q j ist . $\mathcal{F}_Q$$Q_j$

Wir können dann das Minimum Verwendung der binären Suche in C herausfinden und das optimale σ unter Verwendung von Teilzuweisungen zu σ in der Polynomzeit unter Verwendung eines Orakels für T U T herausfinden . Auch T U T ∈ N P, weil das optimale σ als Zertifikat verwendet werden kann, das wir in polynomialer Zeit leicht überprüfen können.$T_\sigma$$C$$\sigma$$\sigma$$\mathsf{TUT}$$\mathsf{TUT} \in \mathsf{NP}$$\sigma$

Meine Frage: Ist N P -vollständig oder können wir einen polynomialen Zeitalgorithmus dafür entwerfen?$\mathsf{TUT}$ $\mathsf{NP}$

Randbemerkung: Ich habe mir diese Frage übrigens nach einer eigentlichen Übungsstunde überlegt, in der der TA die Fragen in der normalen Reihenfolge besprochen hat, weshalb viele Schüler bis zum Ende warten mussten.$q_1 \ldots q_n$

Beispiel
Sei und n = 2 . Q 1 = { q 3 } und Q 2 = { q 1 , q 2 , q 3 } . Wir können sehen , dass eine optimale σ = ⟨ 3 , 1 , 2 ⟩ , weil in diesem Fall s 1 Blätter nach t 1 = 1 und s 2 Blätter nach $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$ , so Summe 4. ist jedochwenn wir die Fragen in der Reihenfolge diskutieren$t_2 = 3$
, dann s 1 und s 2 beide bis zum Ende warten müssenund t 1 = t 2 = 3 , so Summe ist 6.$\langle 1, 2, 3\rangle$$s_1$$s_2$$t_1 = t_2 = 3$

Sie sind freiden allgemeineren Fall zu lösenwo jede Frage q i nimmt x i Einheiten zu diskutieren!$^*$$q_i$$x_i$

Ich vermute das Problem NP-schwer ist. Ich werde zeigen, wie man das Problem so transformiert, dass es in engemZusammenhangmit einem NP-harten Problem steht. (Ja, das ist alles ziemlich vage. Ich denke im Grunde, dass mein allgemeiner Ansatz korrekt ist, aber ich bin derzeit nicht in der Lage, fortzufahren.)$\mathsf{TUT}$

Beachten Sie zunächst, dass das Problem wie folgt umformuliert werden kann:$\mathsf{TUT}$

Bei einer Reihe von Fragen der Größe k , eine Menge von n Teilmengen F Q ⊆ P ( Q ) und eine ganze Zahl C , nicht existiert eine Folge Σ : ⟨ S 1 , ... , S k ⟩ derart , daß für alle 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. und | S i | = i ; und$S_i\subseteq Q$$|S_i|=i$
2. für alle j > $S_i \subset S_j$$j>i$ ; und
3. ?$\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$

Beachten Sie, dass der Satz stellen die ersten i Fragen , die erläutert wird. Die Bedingungen 1 und 2 stellen sicher, dass die Teilmengen gemäß dieser Interpretation gut geformt sind. Bedingung 3 zählt die Anzahl der Schüler, die nicht zu jedem Zeitpunkt abgereist sind, und summiert sich in der Tat zu der gesamten Wartezeit unter allen Schülern.$S_i$$i$

Jetzt beschränken wir die Größe der Teilmengen in auf 2 , damit wir diese Teilmengen als Kanten in einem Diagramm darstellen können, von denen die Eckpunkte die Elemente sind$\mathcal{F}_Q$$2$ . (Ein Härteergebnis für diesen Sonderfall ist ausreichend für die Härte des allgemeinen Problems)$Q$

Nun ist das Problem der Minimierung für ein einzelnes i (dies ignoriert im wesentlichen Bedingung 2) ist äquivalent zu dem folgenden Problem, das ich als ' Double Max  K$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i$$\mathsf{\text{Double max $k$-vertex-cover}}$ ' :

Gibt es bei einem ungerichteten Graphen und ganzen Zahlen k und t eine Menge von Scheitelpunkten V ' ⊆ V mit einer Größe von höchstens k, so dass die Menge { ( u , v ) ∈ E ∣ u ∈ V ' ∧ v ∈ V ′ } hat eine Größe von mindestens t ?$G=(V,E)$$k$$t$$V'\subseteq V$$k$$\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$$t$

Dieses Problem ist NP-schwer, da clique ein Sonderfall dieses Problems ist, wie diese Antwort zeigt. Dies ist jedoch nicht ausreichend , um zu beweisen , T U T NP-schwer, sein , da wir das Maximum für jeden finden müssen i , während 2. respektieren Bedingung Diese Bedingungen sind nicht durch jede Folge erfüllt Σ daß erfüllt nur Bedingung 1 und 3: Betrachten Sie den Graphen auf 7 Eckpunkten mit zwei nicht zusammenhängenden Zyklen, einer der Größe 4 und der anderen der Größe 3 . Für i = 3 ergibt die Auswahl aller Scheitelpunkte im 3- Zyklus das Maximum, während alle Scheitelpunkte der $k$$\mathsf{TUT}$$i$$\Sigma$$7$$4$$3$$i=3$$3$$4$$i=4$

$\mathsf{TUT}$

Zusammenfassend habe ich die Frage auf Folgendes reduziert:

• $\mathsf{TUT}$

$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i=1\ldots k$$i-1$$k$$i$ would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.