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

13

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 .kQ={q1qk}nS={s1sn}sjQjQ1jn:Qjϕ1jnQj=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 jt=0tjsjσ(qσ(1)qσ(n))Tσ=Σ1jntj

I nie były w stanie zaprojektować algorytm czasu wielomianu, lub udowodnić -hardness.NP

Możemy zdefiniować wersję decyzyjną problemu

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

gdzie jest zbiorem . FQQj

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 TN P σTσCσσTUTTUTNPσ

Moje pytanie: czy -kompletne, czy możemy zaprojektować dla niego algorytm wielomianowy?N PTUT 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.q1qn

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 Qk=3n=2P 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 =Q1={q3}Q2={q1,q2,q3}σ=3,1,2s1t1=1s2t2=3
1,2,3s1s2t1=t2=3

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

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,

Odpowiedzi:

1

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

Po pierwsze zauważ, że problem można przeformułować w następujący sposób: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 QP ( Q ) C Σ : S, 1 , ... , S Ki { 1 , ... , K }QknFQP(Q)CΣ:S1,,Ski{1,,k}

  1. | S i | = iSiQ i ; i|Si|=i
  2. j > iSiSj dla wszystkich ; ij>i
  3. i=1k|{qFQqSi}|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.Sii

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)FQ2Q

Teraz problem minimalizacjidla pojedynczego (jest to zasadniczo ignorowanie warunku 2) jest równoważne z następującym problemem, który nazywam „ ”:|{qFQqSi}|iDouble 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)ktVVk{(u,v)EuVvV}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 dlakTUTiΣ743i=334i=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ć.TUT

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

  • Czy można dołączyć warunek 2, aby ukończyć test twardości dla ?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 i|{qFQqSi}|i=1ki1ki

Dyskretna jaszczurka
źródło