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

13

Angenommen, es gibt eine Tutorialsitzung an einer Universität. Wir haben eine Menge von k Fragen Q={q1qk} und eine Menge von n Schülern S={s1sn} . Jeder Schüler hat Zweifel an einer bestimmten Teilmenge von Fragen, dh für jeden Schüler sj sei QjQ die Menge von Fragen, an denen ein Schüler zweifelt. Es sei angenommen, dass 1jn:Qjϕ und 1jnQj=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=0tjsjσ(qσ(1)qσ(n)) minimiert.Tσ=Σ1jntj

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

Wir können eine Entscheidung Version des Problems definieren

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

wobei die Menge von Q j ist . FQQj

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 TN P, weil das optimale σ als Zertifikat verwendet werden kann, das wir in polynomialer Zeit leicht überprüfen können.TσCσσTUTTUTNPσ

Meine Frage: Ist N P -vollständig oder können wir einen polynomialen Zeitalgorithmus dafür entwerfen?TUT 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.q1qn

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 tk=3n=2Q1={q3}Q2={q1,q2,q3}σ=3,1,2s1t1=1s2 , so Summe 4. ist jedochwenn wir die Fragen in der Reihenfolge diskutierent2=3
, dann s 1 und s 2 beide bis zum Ende warten müssenund t 1 = t 2 = 3 , so Summe ist 6.1,2,3s1s2t1=t2=3

Sie sind freiden allgemeineren Fall zu lösenwo jede Frage q i nimmt x i Einheiten zu diskutieren!qixi

skankhunt42
quelle
Um ganz klar zu sein: Treten alle Schüler zur gleichen Zeit ein oder treten sie von dem Moment an ein, an dem ihre erste Frage gestellt wird?
Diskrete Eidechse
@Discretelizard Alle Schüler melden sich zu Beginn zur gleichen Zeit an (bei t = 0).
Skankhunt42
In der aktuellen Definition sind die Fragensätze eindeutig, dh ein Fragensatz gehört höchstens einem Schüler. Dies könnte eine vernünftige Vereinfachung sein, aber ich bezweifle, dass dies realistisch ist (und ich bezweifle, dass dies viel zur Komplexität des Problems
beiträgt
Ich nehme an, zwei Schüler könnten genau die gleichen Fragen haben, daher würde sich die Wartezeit mit zwei multiplizieren.
gnasher729

Antworten:

1

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.)TUT

Beachten Sie zunächst, dass das Problem wie folgt umformuliert werden kann:TUT

Bei einer Reihe von Fragen der Größe k , eine Menge von n Teilmengen F QP ( Q ) und eine ganze Zahl C , nicht existiert eine Folge Σ : S 1 , ... , S k derart , daß für alle i { 1 , , k } :QknFQP(Q)CΣ:S1,,Ski{1,,k}

  1. und | S i | = i ; undSiQ|Si|=i
  2. für alle j > iSiSjj>i ; und
  3. ?i=1k|{qFQqSi}|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.Sii

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 sindFQ2 . (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 -Vertex-Abdeckung bezeichne|{qFQqSi}|iDouble 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)ktVVk{(u,v)EuVvV}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 4 ausgewählt werdenkTUTiΣ743i=334i=4

TUT

Zusammenfassend habe ich die Frage auf Folgendes reduziert:

  • TUT

|{qFQqSi}|i=1ki1ki would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.

Discrete lizard
quelle