#javascript #algorithm #optimization
Вопрос:
Мне стало известно, что я описываю проблему многорукого бандита.
Допустим, у меня есть функция, которая бросает взвешенные 20-сторонние кости, и каждый набор аргументов бросает кубик с разным весом. Мы не знаем точных распределений для этих кубиков, но где-то у них есть пик или два, и другие возможные числа, вероятно, находятся поблизости, но не всегда рядом. Только некоторые аргументы являются числовыми, но в основном проблематичны нечисловые.
Проблема, которую я хочу решить, заключается в том, как эффективно найти набор аргументов, который дает наилучший средний результат (итак, найдите «лучший штамп») и оценку его среднего возвращаемого значения.
Я попытаюсь проиллюстрировать. В нашем примере функция принимает два аргумента: строку типа матрицы и размер эффекта. Вдохновение для моего примера типов штампов: https://kingdom-come-deliverance.fandom.com/wiki/Dice#Dice_Effects
Давайте возьмем матрицу «lu» в качестве нашего типа и получим для нее размер эффекта 1. Это делает число 20 на 19% более вероятным результатом, а остальные 19 чисел будут на 1% менее вероятными. Давайте назовем этот набор аргументов Die-A. Мы получаем средний бросок кубика 12,4. Давайте возьмем еще один кубик, но типа «ul», который имеет «противоположный» эффект от кубика lu. При размере эффекта, равном 1, вероятность того, что результат 1 будет равен 19%-баллам, более вероятным, а остальные числа на 1%-балл менее вероятны. У этого кубика B средний бросок кубика равен 8,6. В этом примере мы бы вернули идентификатор для матрицы-A и оценку для среднего значения, которое он дает, близкую к фактическому 12.4.
Конечно, в реальном сценарии есть еще много «кубиков», и «бросание» их выполняется с помощью очень сложного алгоритма, который в основном требует стохастического решения для получения средних результатов. Как мне выбрать наилучший вариант, уделяя при этом меньше внимания менее перспективным кандидатам для повышения эффективности? Я чувствую, что для этого должен быть какой-то алгоритм или другой, но что мне искать? Моя кодовая база написана на JavaScript, поэтому примеры кода предпочтительнее на этом.
Комментарии:
1. Одной из возможностей может быть метод Нелдера-Мида. Вы бросаете кубик X раз, чтобы получить среднее значение. X должен быть достаточно большим, чтобы вы знали, что среднее значение не отклоняется. Вы выполняете это количество аргументов 1 раз со случайными аргументами, чтобы получить начальный симплекс и прогрессировать оттуда. Это работает только в том случае, если похожие аргументы дают похожие результаты.
2. Пожалуйста, отредактируйте вопрос, чтобы ограничить его конкретной проблемой с достаточной детализацией для определения адекватного ответа.
3. Было бы полезно увидеть какой-то ввод и ожидаемый результат. Вы говорите «набор аргументов», можете ли вы быть более конкретным?
4. Я отредактировал вопрос, чтобы упомянуть, что также используются нечисловые входные данные, поэтому я не уверен, что Нелдер-Мид справится с задачей в этом случае: «Это подходит для одномерных или многомерных функций с числовыми входами».
5. И я также переработал пример, чтобы иметь входные данные только сейчас.