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

13

Предположим, в университете есть учебная сессия. У нас есть набор из вопросов и набор из студентов . Каждый студент имеет сомнение в определенной подгруппе вопросов, то есть для каждого студента , пусть множество вопросов , которые студент имеет сомнение. Предположим , что и .Q = { q 1q k } n S = { s 1s n } s j Q jQ 1 j n : Q jϕ 1 j n Q j = QkQ={q1qk}nS={s1sn}sjQjQ1jn:Qjϕ1jnQj=Q

Все ученики начинают учебное занятие в начале (при ). Теперь студент покидает учебное занятие, как только все вопросы, в которых у него есть сомнения, были обсуждены. Предположим, что время, затрачиваемое на обсуждение каждого вопроса, равно, скажем, 1 единица . Пусть будет временем, проведенным в обучающей сессии. Мы хотим выяснить оптимальную перестановку в которой обсуждаются вопросы такую ​​как величина сведено к минимуму.t j s j σ ( q σ ( 1 )q σ ( n ) ) T σ = Σ 1 j n t jt=0tjsjσ(qσ(1)qσ(n))Tσ=Σ1jntj

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

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

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

где - это набор . Q jFQQj

Затем мы можем найти минимальное значение используя бинарный поиск на и найти оптимальное значение используя частичные присвоения за полиномиальное время, используя оракул для . Кроме того, потому что в качестве сертификата можно использовать оптимальную которую мы можем легко проверить за полиномиальное время. C σ σ T U T T U TN P σTσCσσTUTTUTNPσ

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

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

Пример.
Пусть и . и . Мы можем видеть, что оптимальный потому что в этом случае уходит после а уходит после , поэтому сумма равна 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=3n=2Q1={q3}Q2={q1,q2,q3}σ=3,1,2s1t1=1s2t2=3
1,2,3s1s2t1=t2=3

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

skankhunt42
источник
Просто чтобы прояснить: все ли ученики поступают одновременно или же они поступают с момента, когда задают первый вопрос?
Дискретная ящерица
@Discretelizard Все ученики в начале участвуют одновременно (при t = 0).
skankhunt42
В текущем определении наборы вопросов являются уникальными, то есть набор вопросов принадлежит не более чем одному студенту. Это могло бы быть разумным упрощением, но я сомневаюсь, что это реалистично (и я сомневаюсь, что это многое сделает для сложности проблемы)
Дискретная ящерица
Я предполагаю, что у двух студентов может быть одинаковый набор вопросов, поэтому время ожидания будет умножено на два.
gnasher729

Ответы:

1

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

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

Для заданного набора вопросов размера , набора из подмножеств и целого числа существует ли последовательность , что для всех :к п Р QP ( Q ) C Σ : S 1 , ... , S кя { 1 , ... , K }QknFQP(Q)CΣ:S1,,Ski{1,,k}

  1. SiQ и ; и|Si|=i
  2. SiSj для всех ; иj>i
  3. i=1k|{qFQqSi}|C ?

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

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

Теперь проблема минимизациидля одного (это по существу игнорирует условие 2) эквивалентно следующей задаче, которую я назвал ' ':i Double max  k -вертекс-крышка|{qFQqSi}|iDouble max k-vertex-cover

Для неориентированного графа и целых чисел и существует ли множество вершин размером не более такое что множество имеет размер не менее ?к т V 'V к { ( U , V ) E | U V 'v V ' } тG=(V,E)ktVVk{(u,v)EuVvV}t

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

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

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

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

Примечание: приведенная мной формулировка заставляет заманчиво попробовать итерационный алгоритм, который находитпри условии 2 из путем нахождения всех максимальных «расширений» всех найденных максимальных наборов для . Это не приводит к эффективному алгоритму, так как количество максимальных множеств на одной итерации может быть экспоненциальным по . Кроме того, я не видел метода, чтобы определить, станет ли подмножество для некоторого в конечном итоге «глобальным» максимумом, чтобы предотвратить проверку экспоненциального количества подмножеств.|{qFQqSi}|i=1ki1ki

Дискретная ящерица
источник