Оптимальные убийства

[Sicker]

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

[wrest]

Из вашего рассказа следует, что результат от выбора не зависит. Т.е. если вы намерены убить персонажа $x$, который наносит вам при его убийстве урон $y$, то без разницы будете ли вы это делать в начале битвы или конце, причитающийся вам $y$ вы все равно получите.

[kotenok gav]

Насколько я понял, он наносит урон не при убийстве, а при своей жизни.

[Sicker]

wrest в сообщении #1467419 писал(а):

Т.е. если вы намерены убить персонажа $x$, который наносит вам при его убийстве урон $y$, то без разницы будете ли вы это делать в начале битвы или конце, причитающийся вам $y$ вы все равно получите.

Нет, он наносит урон, пока жив

kotenok gav в сообщении #1467420 писал(а):

Насколько я понял, он наносит урон не при убийстве, а при своей жизни.

+

[EUgeneUS]

Sicker

Пусть $h_i$ - здоровье i-го моба, $s_i$ - сила i-го моба (скорость с которой он наносит урон персонажу).
Тогда мобов надо бить в порядке убывания отношения $\frac{s_i}{h_i}$
ИМХО, доказывается несложно, думаю Вы и сами справитесь.

[Sicker]

EUgeneUS

[ozheredov]

EUgeneUS
А можете подробно расписать решение, пожалуйста?

[EUgeneUS]

ozheredov
От чего же не расписать. Но не ожидайте математической строгости доказательств

1. Первым шагом поймем, что нельзя бить более одного моба одновременно. И действительно, пусть бьем двух мобов, каким-то образом распределяя свою силу на них. Один моб умирает в $t_1$, другой в $t_2 > t_1$.
а) понятно, что оба моба будут мертвы ровно в момент $t_2$, как бы мы не распределяли свою силу между ними. А значит, моб, который умрет вторым нанесет урон $s_2 t_2$, и этот урон не зависит от того, как мы распределим свои силу между этими двумя.
б) тогда, если сначала будем бить первого моба полной силой, мы уменьшим $t_1$, а значит уменьшим общий урон от этих двух мобов.
в) Итак, в каждый момент времени бьем ровно одного моба своей полной силой.

2. Нарисуем график урона персонажу в единицу времени. Этот график
а) Начинается в точке $ A (t=0, S = \sum\limits_{i=1}^{N} s_i)$
б) Заканчивается в точке $B (t = \frac{1}{s_0} \sum\limits_{i=1}^{N}h_i, S=0)$, где $s_0$ - сила персонажа, остальные обозначения, как в моем предыдущем посте.
Отметим, что эти точки не меняются от выбора порядка убийства мобов.
в) площадь под графиком - суммарный урон персонажу, который минимизируем.
г) график представляет собой ступенчатую убывающую функцию.

3. Соединим ломаной последовательно точку $A$, нижние точки ступенек, точку $B$. Тогда площадь под графиком разобьется на следующие части:
а) Треугольники над ломанной. Сумма площадей треугольников над ломаной не зависит от последовательности в которой располагаются отрезки.
б) График под ломанной. Его нужно минимизировать, путем перестановок отрезков ломанной (с сохранением длины и угла наклона каждого отрезка).

4. Из геометрических соображений понятно, что минимальная площадь под ломаной достигается в том случае, когда она выпукла вниз. А значит углы наклона отрезков должны уменьшаться (вообще-то углы отрицательные, то есть должен уменьшаться модуль угла).

5. А отношение $\frac{s_i}{h_i}$ есть ничто иное, как (минус) тангенс угла наклона i-го отрезка ломаной. Ч.Т.Д.

[B@R5uk]

А теперь ещё добавьте к этому возможность восстановить здоровье при смерти моба на процент от его здоровья. Или возможность получить уровень при убийстве каких-либо мобов, который увеличит урон и здоровье управляемого персонажа. Можно ещё вспомнить про тайминги респауна мобов. И про дебаффы на скорость атаки, которые они накладывают. И жизнь сразу станет сложной и непредсказуемой.

[Утундрий]

И.м.х.о., достаточно добавить один только разброс урона, чтобы всё окончательно запутать.

[Sicker]

Утундрий в сообщении #1467713 писал(а):

И.м.х.о., достаточно добавить один только разброс урона, чтобы всё окончательно запутать.

Да тут вроде все просто - чтобы минимизировать матожидание урона, надо взять среднее значения урона и проделать стратегию выше

[EUgeneUS]

Sicker
Чтобы "порушить стратегию" достаточно ввести "оглушение моба" - моб, получивший за n-секунд не менее k-урона, в течение l-секунд не может атаковать. И стратегия рассыпается на первом пункте, ибо становится выгодно бить несколько мобов одновременно.

[kotenok gav]

Предлагаю другую фичу: чем меньше здоровье моба (ну, т.е., чем больше он получил урона), тем сильнее/слабее он атакует.

[ozheredov]

EUgeneUS
Интересные соображения, thanks.
Вот что еще интересно. Это целевая функция, определенная на перестановках. Есть какие-то общие методы нахождения минимума таких функций?
В тред приглашаются:
Someone
pogulyat_vyshel (как из бани вернется)
Otta

P.S. Sicker, респектос за задачу. Вы ее сами придумали? (респектос разумеется не зависимо от того, сами или нет)

[mihaild]

Тут нужно действовать осторожно. Уже для такой простой функции как "число запрещенных пар" (есть некоторый список пар чисел, и мы хотим чтобы числа из пары не стояли рядом) NP-трудна.