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

Question

[trimm]

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

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

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

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

Заранее спасибо.

Answer 1

[cheerfulatlas]

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

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

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

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

Если вы захотите это проверить, вам придется написать некую модель, дабы не тратить производительность на работу с реальным тестом.

Comments

[cheerfulatlas]

Для исключения простоя при не попадении на выбранный вопрос, можно иметь таких 2-3, больше, с приоритетом выполнения. Если посмотреть на это более абстрактно, получаем некий пул задач по подбору вопросов.

[cheerfulatlas]

Практическая проблема - сможем ли мы гарантировать истинность принятого решения за приемлемое время. Потому что я пока слабо представляю, что делать при окончании перебора, если мы будем получать количество баллов несколько меньшее, чем максимум. Т.е. как быстро найти виновного?

[trimm]

По-видимому, я таки неправильно понял ваш прошлый ответ. Вы не могли бы его прояснить подробнее?

Я выполнил полный перебор именно так, как вы предлагаете в этом ответе ( toster.ru/q/54780#answer_199974 ). Логичным решением было бы масштабировать каким-то образом для одновременного анализа нескольких вопросов одновременно, но вот элегантного решения я не нашел, посему и обратился с общественности.

>>Если вы захотите это проверить, вам придется написать некую модель, дабы не тратить производительность на работу с реальным тестом.

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

[cheerfulatlas]

И простите, пропустил мимо, что модель у вас уже есть, раз есть гибкая симуляция

[cheerfulatlas]

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

Сейчас я уже хочу спать, завтра еще подумаю, интересно же.

[trimm]

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

[trimm]

Эх, никто математикой не поделился. Ищу дальше. Спасибо за комментарии. ВЫбрал ваш ответ, как решение, т.к. пока этот способо, хоть и тормознутый, но хотя бы решает поставленную задачу.

Answer 2

[cheerfulatlas]

Кажется, задача более практическая, чем теоретическая? Так что мое не очень математическое видение:

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

В случае же m < n единственной и всем очевидной оптимизацией может быть не только сохранение правильных ответов в случае удачного запуска-подбора, но и использование их для подстановки при запусках для отгадывания оставшихся вопросов.

Comments

[trimm]

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

Ваш вариант я пробовал (назвал его полным перебором). На маленьких тестовых сетах (до 100 вопросов, 2 варианта ответа в вопросе, в одном тесте до 20 вопросов) он показал себя неплохо. Однако, в случае увеличения количества вопросов (1000 вопросов, 8 вариантов у каждого вопроса, 20 вопросов в одном тесте), время полного перебора становится неимоверно большим (считало больше 4 часов и не досчитало, прекратил симуляцию, т.к. надоело ждать).

В любом случае, если не будет вариантов решения более оптимальными алгоритмами, приму ваш ответ, как правильный, т.к. он совпадает с моим решением.

Answer 3

[demolishka]

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

Comments

[trimm]

Каким образом при данных условиях задачи у вас всего-то m*k? Эта сложность просто великолепна для данной задачи, но как ее добится? На ум приходит разный теорвер и статистические методы, но блин у меня они все равно вырождались к прямому перебору, что при данных условиях задачи вырожадется в квадратичную сложность (зависит от распределения используемого для выборки вопросов в тесты).

[demolishka]

Получилось даже несколько по-другому нежели я хотел.
Зафиксируем у всех вопросов ответ под номером 1. Посмотрим результат. Теперь для каждого вопроса найдем правильный ответ на него. Перебираем варианты ответов для одного вопроса пока не изменится сумма баллов. Если на каком-то вопросе сумма увеличилась, то текущий ответ был правильный, если уменьшилась - правильный ответ под номером 1.

[trimm]

Скажите, вы условие задачи читали? ВЫ точно его читали? Выше решение работает только для случая m = n. В случае указанного мною условия задачи сложность m*k не будет. Модификацию вашего алгоритма я пробовал, однако она дает крайне неудовлетворитльный результат по быстродействию, причем при линейном росте n нелинейная скорость роста времени поиска решений.