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 = 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

T U T = {⟨ k, n, F_{Q}, C ⟩ ∣ \exists σ : T_{σ} \leq C}

$\mathsf{TUT} = \{\langle k, n, \mathcal{F}_Q, C \rangle \mid \exists \sigma : T_{\sigma} \leq C\}$

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. $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? $\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. $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$ $t_2 = 3$
$\langle 1, 2, 3\rangle$ $s_1$ $s_2$ $t_1 = t_2 = 3$

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

— skankhunt42
źródło

Żeby było jasne: czy wszyscy uczniowie wchodzą w tym samym czasie, czy też wchodzą od momentu zadawania pierwszego pytania?

— Dyskretna jaszczurka

@Discretelizard Wszyscy uczniowie wchodzą na początku w tym samym czasie (w czasie t = 0).

— skankhunt42

W obecnej definicji zestawy pytań są unikalne, tzn. Zestaw pytań należy do co najwyżej jednego studenta. To może być rozsądne uproszczenie, ale wątpię, czy to jest realistyczne (i wątpię, że to zrobi wiele dla złożoności problemu)

— Dyskretna jaszczurka

Przypuszczam, że dwoje studentów może mieć dokładnie taki sam zestaw pytań, więc czas oczekiwania zostanie pomnożony przez dwa.

— gnasher729,

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 : $Q$ $k$ $n$ $\mathcal{F}_Q\subseteq \mathcal{P}(Q)$ $C$ $\Sigma : \langle S_1,\ldots, S_k\rangle$ $i \in\{1,\ldots,k\}$

$S_i\subseteq Q$ i ; i $|S_i|=i$
$S_i \subset S_j$ dla wszystkich ; i $j>i$
$\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. $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ $i=1\ldots k$ $i-1$ $k$ $i$

— Dyskretna jaszczurka
źródło