Поиск оптимальной последовательности вопросов, чтобы минимизировать общее время студента

Предположим, в университете есть учебная сессия. У нас есть набор из вопросов и набор из студентов . Каждый студент имеет сомнение в определенной подгруппе вопросов, то есть для каждого студента , пусть множество вопросов , которые студент имеет сомнение. Предположим , что и .Q = { q 1 … q k } n S = { s 1 … s n } s j Q j ⊆ Q ∀ 1 ≤ j ≤ n : Q j ≠ ϕ ⋃ 1 ≤ j ≤ n Q j = $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$

Все ученики начинают учебное занятие в начале (при ). Теперь студент покидает учебное занятие, как только все вопросы, в которых у него есть сомнения, были обсуждены. Предположим, что время, затрачиваемое на обсуждение каждого вопроса, равно, скажем, 1 единица . Пусть будет временем, проведенным в обучающей сессии. Мы хотим выяснить оптимальную перестановку в которой обсуждаются вопросы такую ​​как величина сведено к минимуму.∗ 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$

Я не смог разработать алгоритм за полиномиальное время или доказать -твердость.$\mathsf{NP}$

Мы можем определить вариант решения проблемы

где - это набор . Q $\mathcal{F}_Q$$Q_j$

Затем мы можем найти минимальное значение используя бинарный поиск на и найти оптимальное значение используя частичные присвоения за полиномиальное время, используя оракул для . Кроме того, потому что в качестве сертификата можно использовать оптимальную которую мы можем легко проверить за полиномиальное время. C σ σ T U T T U T ∈ N P$T_\sigma$$C$$\sigma$$\sigma$$\mathsf{TUT}$$\mathsf{TUT} \in \mathsf{NP}$$\sigma$

Мой вопрос: -полный или мы можем разработать для него алгоритм полиномиального времени?Н $\mathsf{TUT}$ $\mathsf{NP}$

Замечание: Кстати, я подумал об этом вопросе после реальной учебной сессии, на которой ТП обсуждала вопросы в обычном порядке из-за чего многим студентам пришлось ждать до конца.$q_1 \ldots q_n$

Пример.
Пусть и . и . Мы можем видеть, что оптимальный потому что в этом случае уходит после а уходит после , поэтому сумма равна 4. Однако, если мы обсудим вопросы в порядок , затем и оба должны ждать до конца и , поэтому сумма равна 6.п = 2 Q 1 = { д 3 } Q 2 = { д 1 , д 2 , кв 3 } σ = ⟨ 3 , 1 , 2 ⟩ с 1 т 1 = 1 сек 2 т 2 = 3 ⟨ 1 , 2 , 3 ⟩ с 1 с 2 т 1$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$

$^*$ Вы можете решить более общий случай, когда каждый вопрос требует единиц для обсуждения!x $q_i$$x_i$

Я подозреваю, что проблема является NP-трудной. Я покажу, как преобразовать проблему так, чтобы она была тесно связана с проблемой, которая является NP-трудной. (Да, все это довольно расплывчато. Я думаю, что мой общий подход верен, но в настоящее время я не могу продолжать.)$\mathsf{TUT}$

Во-первых, обратите внимание, что проблему можно переформулировать следующим образом:$\mathsf{TUT}$

Для заданного набора вопросов размера , набора из подмножеств и целого числа существует ли последовательность , что для всех :к п Р Q ⊆ P ( Q ) C Σ : ⟨ S 1 , ... , S к ⟩ я ∈ { 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\subseteq Q$ и ; и$|S_i|=i$
2. $S_i \subset S_j$ для всех ; и$j>i$
3. $\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$ ?

Обратите внимание, что набор представляет первые вопросы которые будут объяснены. Условия 1 и 2 гарантируют, что подмножества правильно сформированы согласно этой интерпретации. Условие 3 подсчитывает количество студентов, которые не уехали в каждый момент времени, поэтому оно действительно суммирует общее время ожидания среди всех студентов.$S_i$$i$

Теперь мы ограничиваем размер подмножеств в до , таким образом , мы можем представить эти подмножества в качестве ребер на графе , где вершины являются элементами из . (Результат твердости для этого особого случая достаточен для твердости общей проблемы) 2$\mathcal{F}_Q$$2$$Q$

Теперь проблема минимизациидля одного (это по существу игнорирует условие 2) эквивалентно следующей задаче, которую я назвал ' ':i Double max  k$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i$$\mathsf{\text{Double max $k$-vertex-cover}}$

Для неориентированного графа и целых чисел и существует ли множество вершин размером не более такое что множество имеет размер не менее ?к т V ' ⊆ V к { ( U , V ) ∈ E | U ∈ V ' ∧ v ∈ V ' } $G=(V,E)$$k$$t$$V'\subseteq V$$k$$\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$$t$

Эта проблема является NP-трудной, поскольку -clique является частным случаем этой проблемы, как показывает этот ответ . Однако этого недостаточно, чтобы доказать, что является NP-трудным, поскольку нам нужно найти максимум для каждого , соблюдая при этом условие 2. Этим условиям не удовлетворяет каждая последовательность которая удовлетворяет только условию 1 и 3: рассмотрим граф на вершинах с двумя непересекающимися циклами, один из которых имеет размер , а другой - размер . Для выбор всех вершин в цикле дает максимум, а выбор всех вершин в цикле оптимален для$k$ i Σ 7 4 3 i = 3 3 4 i = $\mathsf{TUT}$$i$$\Sigma$$7$$4$$3$$i=3$$3$$4$$i=4$ .

Кажется, что условие 2 делает проблему еще сложнее и, скорее всего, не проще, что означает, что должен быть NP-сложным, но я не видел способа, чтобы формально доказать это.$\mathsf{TUT}$

Итак, подведя итог, я сократил вопрос до следующего:

• Можно ли включить условие 2 для завершения доказательства твердости для ?$\mathsf{TUT}$

Примечание: приведенная мной формулировка заставляет заманчиво попробовать итерационный алгоритм, который находитпри условии 2 из путем нахождения всех максимальных «расширений» всех найденных максимальных наборов для . Это не приводит к эффективному алгоритму, так как количество максимальных множеств на одной итерации может быть экспоненциальным по . Кроме того, я не видел метода, чтобы определить, станет ли подмножество для некоторого в конечном итоге «глобальным» максимумом, чтобы предотвратить проверку экспоненциального количества подмножеств.$|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$$i=1\ldots k$$i-1$$k$$i$