Всем привет
Подскажите, пожалуйста, какой наиболее оптимальный алгоритм можно использовать для решения следующей задачи:
Задача:
Есть 80 вопросов разных уровней сложности (от 1 до 5).
Каждый из этих вопросов относится к определенной категории (16).
Необходимо сформировать 20 анкет по 10 вопросов разных категорий в каждой таким образом, чтобы средний вес (сложность) вопросов была примерно одинаковая для всех анкет.
Определив алгоритм, я смогу набросать программку, которая осуществит перебор.
Спасибо заранее!
Пример данных на рисунке. Заранее спасибо!
поиск алгоритма
поиск алгоритма
Последний раз редактировалось Maximus_G 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
Придумал такой алгоритм, но он будет выполняться немеряное количество времени .
Moe решение такое (но длинное):
1. Перебираем все комбинации по 10 из 80 (больше триллиона!)
2. Отбираем комбинации, в которых не повторяются категории.
3. Из полученных комбинаций отбираем наиболее равные по весу.
Что-то бы пооптимальней.
Moe решение такое (но длинное):
1. Перебираем все комбинации по 10 из 80 (больше триллиона!)
2. Отбираем комбинации, в которых не повторяются категории.
3. Из полученных комбинаций отбираем наиболее равные по весу.
Что-то бы пооптимальней.
Последний раз редактировалось Maximus_G 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
4.Там попадутся анкеты отличающиеся только одним вопросом, a Вам это надо? Еще бы как-то профильтровать. Можно сделать, чтобы в любой паре из 20 анкет не более одного вопроса совпадало. Неплохо бы еще так сделать, чтобы 80 вопросов было упомянуто в анкетах равномерно (200 раз в сумме) 40 по 2 раза, 40 по триMaximus_G писал(а):Source of the post Moe решение такое (но длинное):
1. Перебираем все комбинации по 10 из 80 (больше триллиона!)
2. Отбираем комбинации, в которых не повторяются категории.
3. Из полученных комбинаций отбираем наиболее равные по весу.
Последний раз редактировалось Ian 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
a в каждой категории есть вопросы всех весов?
a получается нужно 200 вопросов, a есть только 80? т.e. они могут повторяться?
Может, их лучше как шарики по корзинкам раскладывать? Взяли 1-ю категорию - разложили по 10 корзинкам. потом, отслеживая, чего куда положили, раскладываем 2-ю категорию...
ps ни разу не программист, просто, может, на что умное натолкну..
a получается нужно 200 вопросов, a есть только 80? т.e. они могут повторяться?
Может, их лучше как шарики по корзинкам раскладывать? Взяли 1-ю категорию - разложили по 10 корзинкам. потом, отслеживая, чего куда положили, раскладываем 2-ю категорию...
ps ни разу не программист, просто, может, на что умное натолкну..
Последний раз редактировалось myn 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
Ian, myn
Спасибо что заглянули и за советы
Задание одноразовое, кое-как разбросал вручную.
Времени на продумывание и написания программы не дают .
Удачи!
Спасибо что заглянули и за советы
Задание одноразовое, кое-как разбросал вручную.
Времени на продумывание и написания программы не дают .
Удачи!
Последний раз редактировалось Maximus_G 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
я обычно такие вещи тоже вручную делаю.. кто так ещё может все отследить и взвесить равноценность заданий.. Иногда даже задания одного веса все равно не равноценны... И задания разных категорий не должны быть похожими..
Последний раз редактировалось myn 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
Maximus_G, по-моему то что вы описали -- это по сути задача k-разбиения которая NP-труда, т.e. точное решение можно найти только полным перебором. T.к. решение требуется приближенное то подойдут следующие приближенные алгоритмы: алгоритм свёртки, алгоритм типа "в минимально загруженный", обменный алгоритм, прямо-двойственный подход
Последний раз редактировалось F(x) 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
Означает ли условие
что,
B каждом уровне сложности содержится 80/5 = 16 вопросов?
B каждой категории содержится 80/16 = 5 вопросов?
Согласно изложенному условию, вы можете создать одну анкету и скопировать ee 20 раз. И все веса во всех анкетах будут одинаковыми. B любом случае, у вас 80 вопросов по 200 вариантам должны повторяться.
Maximus_G писал(а):Source of the post
Задача:
Есть 80 вопросов разных уровней сложности (от 1 до 5).
Каждый из этих вопросов относится к определенной категории (16).
Необходимо сформировать 20 анкет по 10 вопросов разных категорий в каждой таким образом, чтобы средний вес (сложность) вопросов была примерно одинаковая для всех анкет.
что,
B каждом уровне сложности содержится 80/5 = 16 вопросов?
B каждой категории содержится 80/16 = 5 вопросов?
Согласно изложенному условию, вы можете создать одну анкету и скопировать ee 20 раз. И все веса во всех анкетах будут одинаковыми. B любом случае, у вас 80 вопросов по 200 вариантам должны повторяться.
Последний раз редактировалось Fff 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
поиск алгоритма
F(x), Fff
Спасибо за подсказки! Удачи!
Спасибо за подсказки! Удачи!
Последний раз редактировалось Maximus_G 29 ноя 2019, 09:50, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 48 гостей