タスクは100回説明されています。habrahabr.ru/ blogs / icfpc / 63279を参照してください。
一言で言えば：
いくつかの衛星が地球の周りを回っていますが、そのうちの1つを制御しています。 一連のエンジンスタートを記述して、タスクを完了する必要があります。 タスクは仮想マシンシミュレータでチェックされ、そのプログラムは主催者によって提供されました。
なぜなら 私は参加する時間があるかどうかを事前に知りませんでした。チームなしで終わりました。これは意思決定プロセスに深刻な影響を与えました。 一人で勝つことは非常に難しいことは明らかだったので、時間がないことが明らかであっても、ポイントを追いかけるのではなく、「美しい」決定をすることにしました。 また、その過程で、私は定期的に興味深いことに気を取られましたが、ポイントを得るためにあまり重要ではありません。
タスクのリストを思い出させてください（各シナリオ4）
- ある円形軌道から別の円形軌道に移動する
- また、2番目の軌道にのみ別の衛星があり、それに近づいてそれに従う必要があります
- また、両方の衛星の軌道のみ-任意の楕円
- 衛星10個+ガソリンスタンド。 私たちはそれらをすべて訪問しなければなりません（フライバイ）
金曜日26日、夕方。 仕事を辞めると、同僚の肩越しにタスクを読んで、「バーチャルマシン」と「サテライト」というキーワードをいくつかキャッチできました。 電車の帰り道で、私はタスクが何であるか疑問に思い、ほとんどの場合、あるVMの言語でコンパイラを書く必要があると判断しました。 家に帰って最終的に課題を読んだとき、コンパイラの作成がキャンセルされたことに気付きました-VMは簡単なことでした。 コンパイラを書くことはできましたが、反対の方向-VM言語からマシンコードまで。
Pythonが言語として選択されました。 視覚化のために、Mathematicaを使用する予定でした。 なぜなら ライセンスされた数学を備えた稼働中のラップトップは職場で忘れられ、急流からダウンロードされ、インストールされました。
最初は頭をだますことはせず、1時間以内にPythonのOrbital Machineを打ち切りました。 それから彼は、割り当てのテキストで最終的に発見されたとらえどころのないバグを探して1時間を費やしました。 その時までに、主催者は新しいバージョンの仕様を投稿し、比較パラメーターは異なる方法で定義されていました。 「バグ」を修正すると、すべてが機能し、後で失敗することはありませんでした。 その間に、VMのデバッグ中に、オーガナイザーのコードから物理定数の値を取り出しました（これらは仕様とは数ビット異なっていました）。 金曜日の夜が過ぎて、私は寝ました。
土曜日：
タスクは明らかに2つの部分に分かれていました。 まず、衛星運動の物理学がありますが、これは実装するのに悪くないでしょう。 次に、VMは有限の精度で動作するため、正確なソリューションでさえカスタマイズする必要があり、さらに4番目のタスクでは、数値でのみ実行可能なSCORE（燃料、時間）関数のグローバルな最適化の必要性が明確に示されます。 考えた後、私は複雑さを増す中で引用する3つの戦略があると決めました。
1.純粋に数値的なブルートフォース法
2.純粋に分析的なバージョン
3.組み合わせ
方法No. 1、物理学なし：天井から取得した初期パラメーターを使用して軌道をシミュレートします。これは、数値最適化手法（勾配降下法、モンテカルロ法など）によって改善されます。 非常に高速なVMといくつかのヒューリスティックが必要です。 「すべての費用で最大ポイント」を獲得したい独身者に最適です。 彼は最初の3つの問題を100％解決しますが、4日にはすでに緊張しています。 最適化のためのパラメータ空間は巨大であり、アルゴリズムは非常にゆっくり収束します。
方法2、物理のみ+少しのヒューリスティック：条件の最初のバージョンで定式化された形式のすべてのタスクが正確に解決されます（その後、月が4番目のタスクに追加されたため、少し複雑になりました）。 したがって、式に座って「スマート」な決定を下すことができます。 欠点は、上で書いたように、正確な解決策が適切ではなく、調整する必要があることです。
方法番号3は、最初の2つから最適な方法を取ります。 正確な解を使用します（数値的に修正します）。 初期近似を適切に行うと、時間と燃料に関するグローバルな最適化が大幅に加速されます。 欠点は、1人の人にとっては仕事が多すぎることです。
ポイント2から始めて、可能であれば最適なソリューション3に進むことにしました。
最初のステップは、いわゆるウィキペディアと呼ばれるものを論理的に実装することでした。 ゴーマンの移行。 一番下の行は、2つの制御パルスを作成することです。最初のパルスは中間軌道に変換され、2番目のパルスは最終軌道に変換されます。
写真：ターゲット軌道への移行の瞬間、エンジンがオンになっている場所は太字でマークされています。
この問題は将来を見据えて解決され、すぐにかなり高度なOrbitクラスを作成し、その後何度も拡張しました。 興味深いことに、多くの人が本Orbital Mechanicsを見つけて、3つのポイントで軌道を数えました。 しかし、私たちの問題では、位置に加えて、速度も既知であるため、2つのポイントに沿った軌道を考慮することができます。 軌道の標準パラメータに加えて、半軸、離心率、エネルギー、角運動量、回転周期などの有用なものがすぐに検討されました。
先に進むと、私は賢明なインテグレーターが執筆に取り組まなかったと事前に言います。 すべての計算は、VMシミュレーションの最後の2点と3番目（次）の予測マジック関数getNextXYに基づいていました（これは予測インテグレーターの初期段階であると言えます。ループで実行すると、本格的な予測が得られますが、遅い）
私が選んだ座標は、地球を中心にした極です。 これらの座標では、考えられるすべての自由軌道は、3つのパラメーターを持つ1つの方程式で記述されます。
R(PHI)=a*(1-e^2)/(1+e*cos(delta+PHI))
、
ここで、aは半長軸、eは離心率、deltaは軌道の回転角です。
途中で、任意の点での楕円の接線の式と、特定の点で互いに接する楕円の式を推定しました（実際、そのような楕円は無限に多くあります）。 3番目のタスクでは、2つの与えられた軌道で3番目の接線を見つける式を導きたいと思いました。 しかし、Lightning Roundの終わりが近づいており、少なくとも何かをサブミックスすることを決めましたが、ソリューションのシリアル化をファイルに書き込むことができませんでした。
すべてのシナリオの最初の問題で、正確な解決策がファイルなしで機能したことは興味深いことです。 これは非常に印象的でした。シミュレーションの2つのステップが実行され、エンジンの軌道とインパルスがそれらから計算され、フィードバックなしで最後まで実行されました。
ライトニングラウンドの終了後、主催者は新しいバージョンの課題をアップロードし、4番目のタスクで月の形で問題を追加しました。 これにより、彼女は正確に解決可能なクラスから除外されました。 しかし、以来 月は地球よりも軽いので、数回の回転に十分な精度のある近似軌道を計算し、最適化の初期値として使用できます。 実際、これは同じ楕円であり、その軸は時間とともにゆっくりと変化します（回転周期よりもはるかに小さい）。
土曜日の夕方までに、すべてが機能し、最初の4つのシナリオを「2点で」解決し、ソリューションを確認してサーバーにアップロードしました。 最後に、楕円軌道の交点を見つけるための公式を導き出しました。その結果、午前中に非接線の経路に沿ってフライトを追加し、スリープ状態に入りました。
日曜日の朝、条件の次の改訂を読み直し、最初のタスクで最大燃料を燃やすとポイントが増えることがわかったという事実に興味がありました。 これは、さらなる進歩にとって致命的であることが判明しました。
まず、燃料を「燃やす」ための最も簡単なアルゴリズムを書き、それがいくらかかるかを考えてから、余分に費やし、小さなパルスで推力を前後に引き、軌道が0.1％を超えて逸脱する場合は軌道を調整します。 これにより、土曜日よりもほぼ1.5倍のポイントが与えられました。
そして、「最善の方法は何ですか？」 おそらく双曲線軌道！」 そして、私は詰まりました（そして、くさびをする誰もいませんでした）。 日曜日は、ほぼ完成したコードの一般化に費やしました。 作業楕円（後でケースの途中で複数回壊れた）に、双曲線と放物線を追加したかった。 そして日曜日の夕方までに、私のコードはすでに最初の問題を「最適な方法で、2点で」解決し、3番目のステップからすぐに目的の軌道に飛んで、そこで減速しました。
最も困難なことは、2つの軌道（任意の2次曲線）の交点を計算するのではなく、飛行時間を予測することでした。 時間はセクターの面積に比例し、インターネット上で楕円/双曲線セクターの既製の式を見つけることはできず、推測する必要がありました。 複雑な議論の双曲線アークタンジェントであるこの恐怖（数学が助けてくれます）を見たとき、私は椅子から落ちそうになりました。 しかし最終的に、私はそれを解き、楕円の通常のアークタンジェントと双曲線の対数を取得しました（非フラクションから、大丈夫です）。 それはほとんど時間の浪費であったことに注意する価値があります（面白いですが）。 飛行時間は、目標軌道を横切るタイミングを知るために必要でしたが、シミュレーションの各ステップを愚かに確認することができます（高速で双曲線軌道の誤差が大きいため、「最後のメーター」を段階的に飛ばす必要がありました） ）
途中で、サインを台無しにしましたが、うまくいきました。 しかし、軌道を描いたとき、私はほとんど笑い出した。 衛星は目的の軌道に飛んで、そこで突然方向を変えて反対方向に飛んだ。 緑の線は計算された軌道であり、赤の線はそれらがどのように飛行したかを示しています。
日曜日の夜の残りの時間、私は標識で標識を捕まえて過ごしました。 すべての式は、軌道と座標記号の相対位置に強く依存していました。
翌日 （3時間スリープした後）、すでに仕事をしていましたが、私はわずかにコードをクリーンアップし、2番目の問題を素早く解決しました。 しかし、何らかの理由で、私の仲間が900メートル以上の精度で目標を追っていたにもかかわらず、彼らはポイントを与えませんでした。 軌道の自動安定化機能を追加し、数万秒にわたって数センチメートルの精度を達成しましたが、ポイントは得られませんでした。 約15分間麻痺状態になっていたので、私はほとんどかんしゃくを起こしました。 私は「幽霊」のために、あるいはターゲットの反射のために飛んでいることに気付きました。 なぜなら オーガナイザーはタスクで絵を描くのが面倒だったので、サインを台無しにし、ターゲットベクトルは反対でした！ パラメータの読み取りにマイナスを追加すると、すべての問題がすぐに解決しました。
すでにポイントがほとんどないことを考えると、私は最後の時点で1つの非稼働中のソリューションを埋めて、さらに約100を失うことになりました。
結論：
長所：
-楽しみの海を手に入れた（そしてそれが目標だった）
-多数の数式を作成し、それらを部分的に適用した
全員が1つのサブタスクに集中しているチームでは、これらの式は非常に便利です。
短所：
-数値手法のサポートなしでは、式はほとんど役に立ちませんでした（まあ、最初は明確でした）
-なぜなら ナンセンスにしばしば気を取られる「責任の圧力」はなかった
-主催者は異なるアーキテクチャの互換性をより懸念する可能性があり、おそらくオプションはVMで整数演算のみを使用することです（これらの問題は発生しませんでしたが）。 まあ、タスクのバグは喜ばれませんでした。