Персонаж некоторой игры характеризуется двумя натуральными числами: $%A$% и $%B$%. Изначально $%A=B=0$%.
На каждом ходу он может улучшить (увеличить на единицу) одну из характеристик. Стоимость улучшения характеристики $%A$% равна $%k^A\over{A+B+c}$% у.е., характеристики $%B$% - $%k^B\over{A+B+c}$% у.е., соответственно. $%k, c$% - константы. $%k\gt1$%. $%c\gt0$%.
Игрок поставил своей целью максимально повышать хар-ку $%A$%. Но, как видно из условия, ему выгодно иногда также улучшать и $%B$%, чтоб снижать цену на следующее улучшение $%A$%.
Вопрос: в какой последовательности надо улучшать параметры, чтобы добиться максимального роста $%A$% при минимальных затратах?
Я не требую "идеального" алгоритма игры, оптимального с точностью до каждой копейки. Достаточно будет соображений о том, в каких, примерно, соотношениях следует держать $%A$% и $%B$%.

задан 25 Сен '13 13:58

10|600 символов нужно символов осталось
0
  1. Задача направлена на оптимизацию пошагового алгоритма (игровой задачи здесь нет). $$ $$ 2. Для корректной постановки задачи не хватает увязки между параметром A и "затратами" ("максимальный рост A при минимальных затратах" не годится). Кроме того, в общем случае нужна определенность временного интервала, на котором должно достигаться оптимальное соотношение "эффект-затраты". В частности же может оказаться, что существует алгоритм, оптимальный на каждом интервале. $$ $$ 3. Задачи такого типа решаются на основе алгоритмов динамического программирования (см., например, Бертсекас, Шрив. Стохастическое оптимальное управление...).

$$ $$ 4. Дополнение с учетом поправки @Chameleon ’a к условию (требуется достичь заданного значения параметра A с минимальными затратами). $$$$ 4.1. Обозначения: $$ p(A,B)=k^A/(A+B+c), q(A,B)=k^B/(A+B+c).$$ m – требуемое (конечное) значение параметра A, j(i) – минимальное целое число, для которого $$ \sum_{j=0}^{j(i)} q(i,j) \ge \sum_{i=0}^m p(i,0) $$ 4.2. Выделим на единичной квадратной сетке область $% i \in \lbrace 0,1, ,…,m \rbrace , j \in \lbrace 0,1, ,…,j(i) \rbrace .$% Для точек (i,j) выделенной области определим величину $% s(i,j) $% соотношениями: $$ s(0,0)=0, s(i,0)=s(i-1,0)+ p(i-1,0), s(0,j)=s(0,j-1)+ q(0,j-1);; $$ при $% i \ge 1, j \ge 1: s(i,j)= min \lbrace s(i-1,j)+ p(i-1,j), s(i,j-1)+ q(i,j-1) \rbrace, $% а также конечную точку: $% (m,j_m), $% где $% j_m = argmin_j s(m,j). $% $$$$ 4.3. Оптимальный путь в точки $% v(i,j) $% определен соотношениями: $% v(0,0)=(0,0), v(i,0)= v(i-1,0) ) \to (i,0), v(0,j)= v(0,j-1) ) \to (0,j) $% для $% i \ge 1, j \ge 1: $% $% v(i,j)=v(i-1,j) \to (i,j) $% при $% s(i-1,j)+ p(i-1,j) \le s(i,j-1)+ q(i,j-1) $% , и $%v(i,j)=v(i,j-1) \to (i,j) $% - в противном случае,
Оптимальный путь $% v(m,j_m) $% в конечную точку $% (m,j_m) $% определяет искомый оптимальный алгоритм.

ссылка

отвечен 27 Сен '13 13:20

изменен 29 Сен '13 21:21

2) "максимальный рост A при минимальных затратах" не годится

Для любого конкретного А найти алгоритм (последовательность улучшений параметров), минимизирующий суммарные затраты. Так годится?

3) Задачи такого типа решаются на основе алгоритмов динамического программирования

Да, я это понимаю, но пока что у меня еще не получилось удачно применить ДП для этой задачки. Я пробовал применять его непосредственно (т.е. для каждого хода), также пробовал ввести функцию B=B(A), вычислять суммарную погрешность P так $$dP={k^A\over{A+B(A)+c}}dA+{k^{B(A)}\over{A+B(A)+c}}dB$$ и применять ДП уже к этому.

(27 Сен '13 13:37) chameleon

@Chameleon, "Для конкретного A..." - да, так годится. При этом временной интервал оговаривать не нужно. Далее ДП для заданного значения A... Пока не берусь - измучен одной "задачкой".

(27 Сен '13 13:48) Urt
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×76
×54

задан
25 Сен '13 13:58

показан
752 раза

обновлен
29 Сен '13 21:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru