Алгоритм автоматического поиска решений тестовых вопросов со взаимоисключающими ответами?

Господа, уже не первый день мучаюсь с решением следующей задачки.

Дано:
Тестовый набор из n вопросов, каждый из которых имеет несколько взаимоисключающих ответов, причем правильный ответ неизвестен. Тест составляется из случайной выборки m вопросов, где m намного меньше n. За каждый правильный ответ на тестовый вопрос начисляется одно очко. Результатом теста является количество очков (т.к. количество правильно отвеченных вопросов).
Найти:
Правильные ответы на все тестовые вопросы.

На данный момент попробовал полным перебором. Решение работает, но крайне некрасивое в силу своей неэффективности. Все другие варианты решения, которые пришли в голову в худшем случае все равно приводят к сложности полного перебора, что совсем даже и не айс.

Возможно, кто-нибудь посоветует, что можно почитать, чтобы таки добить эту задачку? Хотелось бы найти какие-нибудь более элегантные решения, либо хотя бы математическое обоснование, почему таковых решений быть не может (например, если проблема np-полная).

Заранее спасибо.
  • Вопрос задан
  • 5297 просмотров
Решения вопроса 1
cheerfulatlas
@cheerfulatlas
Придумался еще один немного извращенный метод, с использованием статистики.

При первом запуске программы мы запоминаем один из вопросов для дальнейшей его идентификации при последующих запусках.
Поочередно выбираем каждый из вариантов ответа. После чего запускаем тест одинаковое конечное количество раз N со случайными входными наборами, подставляя, при случае, наш избранный ответ.
При достаточно большом числе запусков, глядя на среднюю сумму баллов, мы сможем однозначно определить, какой из ответов является правильным.

У меня, конечно, возникают сильные сомнения в эффективности подобного подхода, но в теории он возможен, и кто его знает, вдруг при большой размерности тестового набора он будет более эффективным, чем тупой перебор.

Плюсом подобного подхода является то, что при определении 100-го правильного ответа, вы уже будете иметь 99 готовых.

Если вы захотите это проверить, вам придется написать некую модель, дабы не тратить производительность на работу с реальным тестом.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
cheerfulatlas
@cheerfulatlas
Кажется, задача более практическая, чем теоретическая? Так что мое не очень математическое видение:

Рассмотрим вариант, когда m=n
Предположим, что тестовый набор состоит из одного вопроса. Очевидно, мы используем полный перебор.
Если тестовый набор состоит из двух вопросов, то ответ на первый вопрос может быть получен только в случае известного ответа на второй вопрос. Исход, когда мы попадаем на неверный ответ к вопросу №2 дает 0+0 либо 0+1 баллов, что не представляет собой полезную информацию.
Аналогично со случаем 3 и больше, ответ на третий вопрос мы можем подобрать только зная ответы на первый и второй.
Таким образом, на практике, нам необходимо запускать наш тест, перебирая входные наборы до тех пор, пока на выходе мы не получим сумму баллов = m.

В случае же m < n единственной и всем очевидной оптимизацией может быть не только сохранение правильных ответов в случае удачного запуска-подбора, но и использование их для подстановки при запусках для отгадывания оставшихся вопросов.
Ответ написан
demolishka
@demolishka
Самый быстрый вариант - предподсчет (то есть - заранее знать все ответы на вопросы). В противном случае, быстрее O(m*k), где k-количество вариантов ответа на каждый вопрос, ответить на все вопросы не получится и то, только в том случае, если мы сразу умеем отвечать на вопрос неверно (например можем пропустить его). Вы ведь не умеете всегда давать правильный ответ на вопрос, не анализируя все варианты ответов на него?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы