Znalezienie optymalnej sekwencji pytań w celu zminimalizowania całkowitego czasu studenta

Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .$k$$Q = \{ q_1 \ldots q_k \}$$n$$S = \{ s_1 \ldots s_n \}$$s_j$$Q_j \subseteq Q$$\forall 1 \leq j \leq n: Q_j \neq \phi$$\bigcup_{1\leq j\leq n}Q_j = Q$

Wszyscy uczniowie rozpoczynają sesję szkoleniową na początku (przy ). Teraz uczeń opuszcza sesję samouczka, gdy tylko zostaną omówione wszystkie pytania, w które ma wątpliwości. Załóżmy, że czas poświęcony na omówienie każdego pytania jest równy, powiedzmy 1 jednostkę . Niech będzie czasem spędzonym przez w sesji szkoleniowej. Chcemy znaleźć optymalną permutację w której omawiane są pytania taką ilość jest zminimalizowany.∗ t j s j σ ( q σ ( 1 ) … q σ ( n ) ) T σ = Σ 1 ≤ j ≤ n t $t = 0$$^*$$t_j$$s_j$$\sigma$$(q_{\sigma(1)} \ldots q_{\sigma(n)})$$T_\sigma = \Sigma_{1\leq j \leq n}t_j$

I nie były w stanie zaprojektować algorytm czasu wielomianu, lub udowodnić -hardness.$\mathsf{NP}$

Możemy zdefiniować wersję decyzyjną problemu

gdzie jest zbiorem . $\mathcal{F}_Q$$Q_j$

Następnie możemy znaleźć minimalny za pomocą wyszukiwania binarnego na i znaleźć optymalny za pomocą częściowych przypisań do w czasie wielomianowym za pomocą wyroczni dla . Ponadto ponieważ optymalny może być użyty jako certyfikat, który możemy łatwo zweryfikować w czasie wielomianowym. C σ σ T U T T U T ∈ N P$T_\sigma$$C$$\sigma$$\sigma$$\mathsf{TUT}$$\mathsf{TUT} \in \mathsf{NP}$$\sigma$

Moje pytanie: czy -kompletne, czy możemy zaprojektować dla niego algorytm wielomianowy?N $\mathsf{TUT}$ $\mathsf{NP}$

Sidenote: Nawiasem mówiąc, myślałem o tym pytaniu po faktycznej sesji instruktażowej, w której TA omawiał pytania w normalnej kolejności przez co wielu studentów musiało czekać do końca.$q_1 \ldots q_n$

Przykład
Niech i . i . Widzimy, że optymalna ponieważ w tym przypadku odchodzi po a odchodzi po , więc suma wynosi 4. Jednak jeśli omówimy pytania w kolejność , a następnie i muszą czekać do końca, a , więc suma wynosi 6.n = 2 $k=3$$n=2$P 2 = { P 1 , Q 2 , Q 3 } σ = ⟨ 3 , 1 , 2 ⟩ s 1 t 1 = 1 s 2 t 2 = 3 ⟨ 1 , 2 , 3 ⟩ e 1 a 2 t 1$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$$t_2 = 3$
$\langle 1, 2, 3\rangle$$s_1$$s_2$$t_1 = t_2 = 3$

q i x $^*$ Możesz rozwiązać bardziej ogólny przypadek, w którym każde pytanie wymaga omówienia jednostek !$q_i$$x_i$

Podejrzewam, że problem jest trudny do rozwiązania. Pokażę, jak przekształcić problem tak, aby był silnie związany z problemem, który jest trudny NP. (Tak, to wszystko jest dość niejasne. Zasadniczo uważam, że moje ogólne podejście jest prawidłowe, ale obecnie nie mogę kontynuować.)$\mathsf{TUT}$

Po pierwsze zauważ, że problem można przeformułować w następujący sposób:$\mathsf{TUT}$

Biorąc pod uwagę zestaw pytań o rozmiarze , zbiór podzbiorów i liczba całkowita , czy istnieje sekwencja taki, że dla wszystkich :K N M Q ⊆ P ( Q ) C Σ : ⟨ S, 1 , ... , S K ⟩ 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. | S i | = $S_i\subseteq Q$ i ; i$|S_i|=i$
2. j > $S_i \subset S_j$ dla wszystkich ; i$j>i$
3. $\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$ ?

Zauważ, że zestaw reprezentuje pierwsze pytania które zostaną wyjaśnione. Warunki 1 i 2 zapewniają, że podzbiory są dobrze uformowane zgodnie z tą interpretacją. Warunek 3 zlicza liczbę uczniów, którzy nie wyjechali w każdym momencie, więc w rzeczywistości sumuje się do całkowitego czasu oczekiwania wszystkich uczniów.$S_i$$i$

Teraz ograniczenia wielkości podzbiorów w do , to można te stanowią podzbiory jako krawędzie na wykresie, gdzie wierzchołki są elementy z . (Wynik twardości dla tego specjalnego przypadku jest wystarczający dla twardości ogólnego problemu)$\mathcal{F}_Q$$2$$Q$

Teraz problem minimalizacjidla pojedynczego (jest to zasadniczo ignorowanie warunku 2) jest równoważne z następującym problemem, który nazywam „ ”:$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i$$\mathsf{\text{Double max $k$-vertex-cover}}$

Biorąc pod uwagę nieukierowany wykres i liczby całkowite i , czy istnieje zbiór wierzchołków o wielkości co najwyżej taki, że zbiór ma rozmiar co najmniej ?$G=(V,E)$$k$$t$$V'\subseteq V$$k$$\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$$t$

Ten problem jest trudny NP, ponieważ klika jest szczególnym przypadkiem tego problemu, jak pokazuje ta odpowiedź . Nie jest to jednak wystarczające, aby udowodnić, że jest NP-trudny, ponieważ musimy znaleźć maksimum dla każdego , jednocześnie przestrzegając warunku 2. Warunki te nie są spełnione przez każdą sekwencję która spełnia tylko warunek 1 i 3: rozważ wykres na wierzchołkach z dwoma rozłącznymi cyklami, jeden o rozmiarze , drugi o rozmiarze . Dla zaznaczenie wszystkich wierzchołków w cyklu daje maksimum, natomiast wybranie wszystkich wierzchołków w cyklu jest optymalne dla$k$$\mathsf{TUT}$$i$$\Sigma$$7$$4$$3$$i=3$$3$$4$$i=4$ .

Wygląda na to, że warunek 2 sprawia, że ​​problem jest jeszcze trudniejszy, a na pewno nie łatwiejszy, co oznacza, że powinien być trudny do NP, ale nie widziałem metody, aby to formalnie udowodnić.$\mathsf{TUT}$

Podsumowując, ograniczyłem pytanie do następującego:

• Czy można dołączyć warunek 2, aby ukończyć test twardości dla ?$\mathsf{TUT}$

Uwaga dodatkowa: Formuła, którą podałem, kusi do wypróbowania iteracyjnego algorytmu, który znajdziepod warunkiem 2 od , znajdując wszystkie maksymalne „rozszerzenia” wszystkich znalezionych maksymalnych zbiorów dla . Nie prowadzi to do wydajnego algorytmu, ponieważ liczba maksymalnych zestawów przy pojedynczej iteracji może być wykładnicza . Ponadto nie widziałem metody pozwalającej ustalić, czy podzbiór dla niektórych ostatecznie stałby się „globalnym” maksimum, aby zapobiec sprawdzeniu wykładniczej liczby podzbiorów.i = 1 … k i - 1 k $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i=1\ldots k$$i-1$$k$$i$