Rocket Science for Fun and Fun

Есть такая замечательная кроссплатформенная игрушка - Kerbal Space Program - симулятор космической программы, где нужно конструировать космические корабли и бороздить ими просторы вселенной, летая к другим планетам, строя космические станции и т.д. Для строительства кораблей доступно множество готовых частей (двигатели, топливные баки, кабины для космонавтов, вспомогательные маневровые двигатели, парашюты для посадки, крылья и закрылки, лестницы, солнечные батареи и всякое прочее), которые можно комбинировать множеством способов. Ваша задача - написать программу, которая получит на вход два ключевых параметра (масса полезного груза и delta-V бюджет) и придумает ракету наименьшей массы, способную поднять этот груз в космос и доставить его до цели, обеспечив требуемый бюджет скорости.

Delta-V бюджет

Для космического корабля с выключенными двигателями, находящегося в гравитационном поле планеты или звезды, его дальнейшая судьба определяется только его скоростью и не зависит от массы и формы корабля. Если скорость не слишком велика, то в каждый момент времени он движется по орбите вокруг захватившего его небесного тела. Чтобы переместиться от одной планеты к другой, необходимо как минимум дважды поменять текущую орбиту: сперва перейти на эллиптическую орбиту, проходящую мимо обеих планет, затем перейти на орбиту вокруг новой планеты. Каждая такая смена орбиты есть изменение текущей скорости: к старому вектору скорости прибавляется некоторый корректирующий вектор ∆v и получается новый вектор скорости, соответствующий новой орбите. В промежутках между сменами орбит корабль летит по инерции и топливо не тратит. Стоит заметить, что эта ∆v не зависит от характеристик корабля и зависит только от маршрута: в каком месте с какой орбиты на какую переходим. При планировании межпланетной миссии составляется план маневров, и ∆v всех маневров суммируется в общий ∆v бюджет, который определяет, сколько нужно топлива: если его будет меньше, то пролететь по маршруту не получится, а если слишком много, то корабль выйдет излишне тяжелым и дорогим.

Расчет ∆v

Для расчета изменения скорости при использовании ракетного двигателя используется уравнение Циолковского:

∆v = log (m_start / m_end) * Isp * 9.816

где:

m_start - общая масса корабля в начале маневра (в момент включения двигателя)
m_end - общая масса корабля в конце маневра (в момент выключения двигателя)
Isp - удельный импульс - характеристика эффективности двигателя
9.816 - используемая в игре константа для g.
логарифм натуральный

Разница между m_start и m_end - это масса потраченного во время маневра топлива. В m_start и m_end входит и масса полезного груза, и масса двигателей, соответственно, чем легче корабль, тем больше будет ∆v при тех же затратах топлива и том же двигателе, или, другими словами, тем меньше нужно топлива для достижения заданного ∆v. Когда ракета состоит из нескольких ступеней, отстреливая отработавшую ступень, мы резко уменьшаем общую массу корабля и тем повышаем эффективность двигателей очередной ступени. Разные двигатели имеют разную массу и разную эффективность - удельный импульс. Еще один важный параметр двигателей - сила тяги, выражаемая в Ньютонах. Некоторые двигатели имеют небольшую массу и большой удельный импульс, что делает их чрезвычайно эффективными по топливу, но при этом они могут иметь совсем небольшую тягу. И если двлеко в космосе это может быть приемлемо, то при взлете с планеты этой тяги может быть недостаточно, чтобы оторваться от поверхности. Кроме того, удельный импульс двигателя может быть различным в вакууме и в атмосфере. Для простоты будем считать, что самая первая ступень ракеты (которая включается при старте) работает в атмосфере, а остальные ступени будем расчитывать с удельным импульсом в вакууме.

Структура ракеты

Игра позволяет строить весьма разнообразные и причудливые корабли, но для упрощения расчетов и сужения пространства поиска мы введем ряд ограничений на их структуру. Ракета состоит из нескольких ступеней: при старте начинают работать двигатели первой, самой нижней, ступени, используя топливо из баков первой ступени. Когда топливо в них заканчивается, первая ступень (пустые баки и двигатели) отстреливаются специальным разделителем, после чего тут же начинают работу двигатели второй ступени. И так далее, пока не будет отброшена последняя ступень ракеты-носителя и не останется один лишь полезный груз (это может быть посадочный модуль со своими двигателями, но в рамках данной задачи это для нас неважно, важна лишь его масса). Каждая ступень состоит из опциональной центральной части (топливные баки и, вероятно, двигатель), являющейся частью "ствола" ракеты и 0, 2, 3, 4 или 6 боковых частей, также состоящих из топливных баков и опционального двигателя. Т.е. всего возможны три формы ступени:

только центральная часть (ствол)
центральная часть + боковые части вокруг него
только боковые части

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

Каждая часть ступени (центральная или боковые) состоит из 1-3 топливных баков, поставленных вертикально друг на друга, и, опционально, двигателя под ними. В ступенях первой и третьей формы двигатели обязаны быть во всех частях. В ступени второй формы, состоящей из центральной части и N боковых, двигателей может быть либо 1 (только в центре), либо N+1 (везде). В пределах одной ступени все топливные баки и все двигатели одинаковые. Число баков во всех частях ступени тоже одинаковое.

Параметры всех двигателей и топливных баков перечислены здесь:
http://wiki.kerbalspaceprogram.com/wiki/Parts
В данной задаче используем только Liquid Fuel Engines размера Small и Large, а также топливные баки размера Small и Large. Другие двигатели и баки не используем, всякие твердотопливные бустеры тоже игнорируем.

Между собой ступени соединяются разделителями. Вертикально они соединяются в стволе. Если двигатель верхней ступени и бак нижней ступени оба размера Large, то используется "Rockomax Brand Decoupler" массой 0.4 тонны. В противном случае используется "TR-18A Stack Decoupler" массой 0.05 тонны. Для горизонтального отделения боковых частей (разделения ступеней первой и третьей форм) используетя "TT-38K Radial Decoupler" массой 0.025 тонны. Масса разделителя прибавляется к общей массе нижней (отделяемой) ступени.

Замечание: двигатель "Toroidal Aerospike Rocket" не соединяется с разделителями, поэтому его нельзя использовать в центральной части, под которой будут другие ступени. Можно в боковых частях и можно в центральной части самой нижней ступени (хотя там он вряд ли пригодится).

Остальные запчасти из того списка в вики игнорируйте, масса всех необходимых деталей будет включена в массу полезного груза.

Формат решения

Программа должна получать на вход два вещественных числа: массу полезного груза в тоннах и Delta-V бюджет в м/с. На выход она должна выдать конфигурацию ступеней в порядке сверху-вниз (первой выводится ступень, отрабатывающая позже всех, последней выводится ступень, отрабатывающая раньше всех) в формате JSON-списка. Параметры одной ступени:

"fuel" - название топливного бака, используемого в этой ступени, строка
"engine" - название двигателя, строка
"central" - есть ли в этой ступени центральная часть (true/false)
"numSideParts" - кол-во боковых частей в этой ступени: 0, 2, 3, 4 или 6.
"numEngines" - число двигателей в ступени (число: 1, numSideParts или numSideParts + 1)
"height" - число топливных баков в одной части (1, 2 или 3).

Пример конфигурации:

[
 {"fuel": "FL-T400 Fuel Tank",
  "engine": "LV-N Atomic Rocket Engine",
  "central": true,
  "numSideParts": 3,
  "numEngines": 1,
  "height": 1},
 {"fuel": "Rockomax X200-16 Fuel Tank",
  "engine": "LV-T30 Liquid Fuel Engine",
  "central": true,
  "numSideParts": 2,
  "numEngines": 3,
  "height": 1},
 {"fuel": "Rockomax X200-8 Fuel Tank",
  "engine": "Rockomax \"Skipper\" Liquid Engine",
  "central": true,
  "numSideParts": 4,
  "numEngines": 5,
  "height": 1} 
]

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

Общий запас delta-V для ракеты определяется как сумма delta-V всех ступеней. При расчете ∆v одной ступени следует учитывать, что m_start есть сумма массы полезного груза, массы всех следующих (по времени) ступеней и массы текущей ступени при полных баках. m_end - то же, но уже с пустыми баками текущей ступени. Суммарное значение ∆v должно получиться больше или равным заданному на входе требуемому бюджету. При этом следует минимизировать суммарную массу всей ракеты. При расчете ∆v следует брать Isp двигателя в вакууме для всех ступеней кроме стартовой (последняя в выводимом списке), для которой следует использовать значение Isp в атмосфере. Считаем, что первые 5000 м/с бюджета тратятся на подъем с ~~Земли~~ Kerbin'a и выход на его орбиту. Поэтому ступени, работающие на этом участке, обязаны давать тягу такую, которая в невесомости бы дала ускорение 15 м/с. Тяга для ступени считается как произведение числа двигателей на тягу (thrust) одного двигателя (взять из таблички в вики). Поскольку тяга - это сила, F = m*a, F/m = a, отношение тяги к массе m_start должно быть не меньше 15 для тех ступеней, что дают первые 5000 м/с ∆v. Для последующих ступеней минимально допустимое ускорение равно 5 м/с, т.е. отношение тяги к m_start таких ступеней должно быть не меньше 5.

В игровую физику также входит сопротивление воздуха, но мы им в этой задаче пренебрежем.

Проверить решение и сравнить расчеты по ракете можно здесь: (ссылка будет добавлена)

Решение ваша программа должна находить за 2 минуты. Присылайте конфигурации, найденные вашей программой для таких параметров:

m = 10.4, ∆V = 7000
m = 1.5, ∆V = 12000
m = 13.8, ∆V = 6000
m = 18.2, ∆V = 8000

а также исходники и время, за которое программа нашла решение, а вы нашли программу. :)