Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.138.199.50] |
|
Сообщ.
#1
,
|
|
|
Что-то несвязуха какая-то. Вроде несложная задача, но как-то не вырисовывается алгоритм. Помогите разобраться. Задача не синтетическая, но изложу её синтетически.
Есть некая величина, постоянно растущая с определённой скоростью. Скажем, на 1 единицу за единицу времени. Величина не дискретная, растёт непрерывно. Другими словами, за пол-единицы времени она вырастет на пол-единицы. Нужно дождаться, чтобы она выросла до некого очень большого значения, например 100 тыщ миллионов. Понятно, что тут требуется 100 тыщ миллионов единиц времени, если начинать с нулевого стартового значения. Но есть одно но: скорость роста можно увеличить, если сбросить величину обратно в нуль. При этом скорость роста пропорциональна кубическому корню от (достигнутой величиной на момент сброса значения + все ранее накопленные на моменты сбросов значения). Пример. Берём сумму ранее накопленных значений 2. Скорость роста, скажем, 0,02. Ждём 300 единиц времени. Величина от 0 достигает значения 6. Сбрасываем и получаем увеличение скорости роста в 3√2+6 = 2 раза, т.е. после сброса она равна 0,04. Теперь (вновь до 6) величина вырастет всего за 150 единиц времени. Ждём однако 475 единиц времени, а не 150. За это время величина вырастет до значения 19. Сбрасываем и получаем увеличение скорости роста в 3√2+6+19 = 3 раза. Теперь скорость роста будет 0,06, но значение величины снова 0. Понятно, что чем чаще сбрасываем, тем быстрее увеличивается скорость роста, однако это держит величину постоянно в районе 0, а нам-то надо в итоге сделать её очень-очень-очень большой. Если же сбрасывать редко, то скорость роста будет ниже потенциально достижимой. В примере выше после последнего сброса мы теперь можем достичь величины 19 за ≈317 единиц вместо 475, однако суммарно-то мы потратим 317+475+300 = 1092, что без всяких сбросов, со скоростью 0,02 то бишь, позволило бы достичь 21,84, однако ещё всего через 71 единицу времени эти два сброса позволят догнать и перегнать консервативный вариант, который без сбросов. Вопрос: как оптимизировать моменты сброса величины, чтобы достичь 100 тыщ миллионов за минимальное время? |
Сообщ.
#2
,
|
|
|
Если бы не кубический корень был, а квадратный, подумал бы, что ты cookie clicker оптимизаруешь
Жадный алгортим "если сбросим и будем ползти к цели с новой скоростью меньше времени, чем просто ползти без сброса, то сбрасываем" не является ли оптимальным? |
Сообщ.
#3
,
|
|
|
Ну, про кубокорень это я от балды. На самом деле там может быть непоймикакая функция. Однозначно лишь, что её производная положительна и меньше единицы. Это из задачи управления сложной механической системой. Ну ты в курсе, какой направленности . Меня как бы это не касается, не я алгоритмы придумываю, просто праздный математический интерес.
Та вот, написал, пошёл покурить и вдруг придумалось, что оптимальнее всего будет сбрасывать постоянно, пока накопленные суммы не набегут до некой величины, когда очередной сброс уже отдалит, а не приблизит достижение цели. Потом прекратить сбрасывать, и пусть себе бежит остаток сам по себе с постоянной скоростью. Несинтетически если, то постоянно, конечно, сбрасывать не стоит, нужно как-нибудь без паранойи. Вопрос только, где эта пороговая величина? Как-то должна зависеть от закона роста, целевого значения и начальной скорости роста. Блин, кроме диффур, чтобы вывеси функцию, в голову ничего не лезет, но ведь если так, кто-то ж уже стопудово решал подобное. |
Сообщ.
#4
,
|
|
|
Самое простое решение - графическое.
Рисуешь график функции роста величины от времени. Начиная с нуля, но не скорость роста, а интегральную зависимость величины от времени. Проводишь из начала координат к этому графику касательную, чтобы весь график был под касательной (кроме точки (точек) касания, естественно). А дальше, дожидаешься, пока величина доберётся до точки касания (если их несколько, то до любой из них), и сбрасываешь величину в ноль. Это даст тебе максимальную среднюю скорость роста. Желательно, чтобы сброс осуществлялся точно в точке касания, но влияние небольших промахов почти незаметно. Если скорость роста монотонно возрастает, то оптимальное решение - ничего не трогать. То же, если скорость роста всегда больше текущей средней средней скорости. |