Нашёл такую "старинную" игру проглядывая "старинную" книжку. Если я правильно помню, клоны её публиковались в "Технике Молодёжи" для программируемого калькулятора.
Игрок управляет ракетой которая мчится к Луне. Ему показывают текущие высоту и скорость, а также количество остающегося топлива.
Нужно задать скорость подачи топлива на ближайшие 10 секунд (этим определяется скорость торможения) — после которых снова показываются высота и скорость и т.п.
Цель игры аккуратно посадить ракету — т.е. достигнуть высоты 0 со скоростью не больше, скажем, 10 м/с.
Физика игры примерно ясна: высота за каждые 10 сек уменьшается примерно на значение скорость * 10. Скорость сама по себе меняется в зависимости от ускорения силы тяжести (увеличивается) и работы двигателей (уменьшается).
Идея мне понравилась и я её заюзал для простенького упражнения на своём сайте. Кроме того я написал клон игры в качестве демонстрации и прилепил его туда же:
Демонстрашка и чуть больше пояснений здесь
После этого я стал играть сам и обнаружил что посадить ракету вообще не так легко!
Часто оказывалось что я сжёг всё топливо пока находился ещё достаточно высоко, ракета теряла скорость, потом начинала набирать её снова и БАЦ :(
В иной раз я наоборот слишком берег запас и ракета радостно врезалась в поверхность имея ещё полторы тонны горючего.
Отсюда я заинтересовался вопросом:
Как тут можно алгоритмически по заданным начальным данным посчитать оптимальную последовательность сигналов управления (задающих когда сколько топлива подать) — с тем чтобы во-первых сесть с требуемой небольшой скоростью, а во-вторых по возможности истратить поменьше топлива.
I'm not sure, but I think this is a problem in Optimal Control theory. Usually it is solved using mathematical tools for optimization, like Matlab. I'd be surprised to know that there is a regular algorithm to do this task.
Yeah, I did not mean "regular algorithm" like "some dp approach" etc.
However I'm seeking for some idea for at least iterative, non-exact approach since it does not look idea-less brute-force will do :(
RodionGork — "Нет времени объяснять! Кто-нибудь знает как посадить ракету?!" :D
Вообще мне показалось что это задача на функциональный анализ, которую видоизменили для решения на калькуляторе, дополнив условие фразой "Вы можете менять скорость торможения только каждые 10 секунд, а не каждый момент времени".
Более формально, имеем набор
(H,M,g,v)гдеH— высотаM = Mr + Mf— общая масса (тело+топливо)g = C / (h+r)^2— гравитация, или положительное ускорение (C это масса Луны на грав. постоянную, r — радиус)v— текущая скоростьНадо дойти до
(0,M',g',v'), гдеMr <= M', g' = C / r^2, 0 <= v' <= 10Вот подумал как бы это можно было решать, но блин такая куча случаев. Проще было бы ввести условие "при посадке топливо должно закончиться и скорость должна быть равна нулю", было бы еще туда-сюда, можно было бы оптимизировать функцию скорости торможения от массы топлива и высоты
V = f(mf,h), mf = 0..Mf, H = 0..h(масса ракеты и начальная скорость — константы, оптимизировать надо по конечной скорости). Но блин нет — тогда иногда придется висеть со скоростью 0 на высоте 0 (при этом сила торможения будет плавно уменьшаться, т.к. будет уменьшаться общая масса ракеты :D). А уж когда вспомнишь про то что высота у нас меняется скачкообразно (по 10 сек), тогда уж совсем ниче не понятно как делать (ее вроде как не получится оптимизировать стандартными численными методами, производные брать уж точно). В общем жаль что я не умею делать научные расчеты.О... это не имелось в виду — просто мне казалось что для самой игры подробные физические детали не слишком важны — сам я их подробно осознал только когда код писал. В то же время многие наверняка лучше меня в этом разбираются (почему я и пришёл жаловаться).
И тут мне становится совсем стыдно потому что от функционального анализа я знаю только название — и соответственно часть написанного Вами понимаю довольно смутно :(
Ну я сейчас пробую пародии на генетический алгоритм... Тут же вообще у нас вектор параметров:
Его можно инициализировать произвольными значениями и дальше либо рандомно по чуть-чуть менять, либо производные смотреть и осознанно эти параметры шевелить.
Только вот я не пойму есть ли при этом непрерывность результата. :(
Ну и конечно это такой способ... тыканье вслепую за отсутствием лучших идей.
на кукан посадите лол.