На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Оптимизация роста постоянно растущей величины , со сбросами в 0, увеличивающими скорость роста.
    Что-то несвязуха какая-то. Вроде несложная задача, но как-то не вырисовывается алгоритм. Помогите разобраться. Задача не синтетическая, но изложу её синтетически.
    Есть некая величина, постоянно растущая с определённой скоростью. Скажем, на 1 единицу за единицу времени. Величина не дискретная, растёт непрерывно. Другими словами, за пол-единицы времени она вырастет на пол-единицы. Нужно дождаться, чтобы она выросла до некого очень большого значения, например 100 тыщ миллионов.
    Понятно, что тут требуется 100 тыщ миллионов единиц времени, если начинать с нулевого стартового значения. Но есть одно но: скорость роста можно увеличить, если сбросить величину обратно в нуль. При этом скорость роста пропорциональна кубическому корню от (достигнутой величиной на момент сброса значения + все ранее накопленные на моменты сбросов значения).
    Пример. Берём сумму ранее накопленных значений 2. Скорость роста, скажем, 0,02. Ждём 300 единиц времени. Величина от 0 достигает значения 6. Сбрасываем и получаем увеличение скорости роста в 32+6 = 2 раза, т.е. после сброса она равна 0,04. Теперь (вновь до 6) величина вырастет всего за 150 единиц времени. Ждём однако 475 единиц времени, а не 150. За это время величина вырастет до значения 19. Сбрасываем и получаем увеличение скорости роста в 32+6+19 = 3 раза. Теперь скорость роста будет 0,06, но значение величины снова 0.
    Понятно, что чем чаще сбрасываем, тем быстрее увеличивается скорость роста, однако это держит величину постоянно в районе 0, а нам-то надо в итоге сделать её очень-очень-очень большой. Если же сбрасывать редко, то скорость роста будет ниже потенциально достижимой. В примере выше после последнего сброса мы теперь можем достичь величины 19 за ≈317 единиц вместо 475, однако суммарно-то мы потратим 317+475+300 = 1092, что без всяких сбросов, со скоростью 0,02 то бишь, позволило бы достичь 21,84, однако ещё всего через 71 единицу времени эти два сброса позволят догнать и перегнать консервативный вариант, который без сбросов. Вопрос: как оптимизировать моменты сброса величины, чтобы достичь 100 тыщ миллионов за минимальное время?
    Сообщение отредактировано: Qraizer -
      Если бы не кубический корень был, а квадратный, подумал бы, что ты cookie clicker оптимизаруешь :D
      Жадный алгортим "если сбросим и будем ползти к цели с новой скоростью меньше времени, чем просто ползти без сброса, то сбрасываем" не является ли оптимальным?
        Ну, про кубокорень это я от балды. На самом деле там может быть непоймикакая функция. Однозначно лишь, что её производная положительна и меньше единицы. Это из задачи управления сложной механической системой. Ну ты в курсе, какой направленности ;) . Меня как бы это не касается, не я алгоритмы придумываю, просто праздный математический интерес.
        Та вот, написал, пошёл покурить и вдруг придумалось, что оптимальнее всего будет сбрасывать постоянно, пока накопленные суммы не набегут до некой величины, когда очередной сброс уже отдалит, а не приблизит достижение цели. Потом прекратить сбрасывать, и пусть себе бежит остаток сам по себе с постоянной скоростью. Несинтетически если, то постоянно, конечно, сбрасывать не стоит, нужно как-нибудь без паранойи. Вопрос только, где эта пороговая величина? Как-то должна зависеть от закона роста, целевого значения и начальной скорости роста. Блин, кроме диффур, чтобы вывеси функцию, в голову ничего не лезет, но ведь если так, кто-то ж уже стопудово решал подобное.
          Самое простое решение - графическое.
          Рисуешь график функции роста величины от времени. Начиная с нуля, но не скорость роста, а интегральную зависимость величины от времени.
          Проводишь из начала координат к этому графику касательную, чтобы весь график был под касательной (кроме точки (точек) касания, естественно).
          А дальше, дожидаешься, пока величина доберётся до точки касания (если их несколько, то до любой из них), и сбрасываешь величину в ноль. Это даст тебе максимальную среднюю скорость роста.
          Желательно, чтобы сброс осуществлялся точно в точке касания, но влияние небольших промахов почти незаметно.

          Если скорость роста монотонно возрастает, то оптимальное решение - ничего не трогать. То же, если скорость роста всегда больше текущей средней средней скорости.
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0210 ]   [ 16 queries used ]   [ Generated: 19.03.24, 05:05 GMT ]