thirteen

(san) Новые подробности детектива.

июня 30, 2009 в 19:29 | Новости |

Всплывают в памяти новые подробности.

В самом начале в четвертой задаче мы решали задачу минимизации топлива. Это позволяло нам вертеться не спеша вокруг Земли, вылавливая спутники по очереди, и дало высокий счёт. Но больший счет был бы достигнут при более быстром их облете. Было решено сделать следующий вариант: полностью израсходовать топливо, но очень быстро облететь все спутники. Этот вариант требовал возвращения на базу каждый раз после полета к спутнику, потому что полет был наиболее эффективным и съедал всё топливо (почти, чтобы уложиться суммарно). Но возникли проблемы с возвращением на базу (плохо сходился градиентный алгоритм расчета траектории возврата, то есть он иногда сходился очень, неприемлемо медленно). Чтобы минимизировать это “иногда”, я стал решать более полную задачу - летать за спутниками более эффективно с точки зрения по топливу, чтобы 3-4 спутника облететь за один раз. Эта задача была решена, но возвращения на базу остались проблемными - для нахождения точного импулься требовалось слишком много циклов перебора при градиентном спуске.

И сейчас я понимаю, почему. Потому что при возвращении вниз к земле очень малое изменение направления в начале траектории очень сильно влияет на конечную точку вблизи земли. Вспомните, с какой скоростью спутники вращаются вокруг земли! Там время как бы “идет быстрее”.  Оптимальная “дырка” в плоскости решений становится очень маленькой, на порядки меньше, оттого и время для ее решения. Обратная задача, при взлете, или при переходе с орбиты на орбиту - более простая.

В результате мы не смогли реализовать оптимизацию высокоуровневого алгоритма, который бы регулярно возвращался на базу, по причине медленности его отладки! Наша ошибка в том, что мы недооценили серьезность неумения возвращаться на базу, а этот алгоритм нужен был очень часто, и он был самым слабым местом, которое мы так и не починили.

Пример его использования: при выборе очередного спутника нам надо было знать, а хватит ли у нас топлива вернуться на базу? Для этого требовалась симуляция полета на спутник (с уточнением, которое сходилось бы быстро - см выше) а затем симуляция возвращения на базу - которая часто не сходилась!. Поэтому вместо этого делалось грубое прикидывание Ламбертом, которое регулярно оказывалось неверным из-за погрешностей, и на базу мы не возвращались. Возможно, уточнение первой половины помогло бы, но я не уверен, и не успел реализовать.

В результате его неиспользования, мы прекрасно облетали 4-5 спутников за один круг (!!! это выглядело великолепно на визуализаторе!!), и залетев однажды на базу (получалось!) набирались топлива, после чего нам надо было поймать следующие спутники, часто на более высоких орбитах (втч вытянутых), таким образом на базу нужно было возвращаться всё чаще (раз 5-6 всего), и на этом месте нас застал финальный свисток.

Далее, баг с посещением всех спутников, но необъявлением нам результатов, о чем Rst написал.  На самом деле баг со счетом состоял в том, что надо было подождать 2 миллиона секунд, пока прийдет счёт. Так что 4-я проблема была таки решена верно, и мы добавили просто ожидание.

В обед третьего дня (см внизу) RST был разбужен решением другой проблемы, а именно:  на сервере организаторов, после сабмита, наши прекрасно решенные проблемы 2000 и 3000 уходили в бесконечность (timeout), что означало, что условие остановки не достигнуто, и спутник улетел мимо, и крутится себе где-то на левой орбите. Нашим возмущениям не было предела: у нас решаются задачи о посложнее, значит VM реализована правильно, а наше решение считается неверным у организаторов. В задачах 4000 мы получали около 260 очков, что означало что мы-таки что-то ловим, но не всё.

Была предпринята попытка проанализировать код VM на предмет ошибок, но буква в букву спецификация сходилась. Была попытка обратить внимание организаторов на вопиющее безобразие. Но они качественно отморозились.

Тогда я понял, что нужна VM сторонних производителей, и пошел на jabber просить милостыню. Там добрая лисперская душа дала мне ссылку на чей-то java интерпретатор (не компилятор), и я его прикрутил, и увидел, что в 4000 задаче нашим решением ловятся только первые 2 спутника, а потом мы гуляем безрезультатно. Это был уже результат: проблема была изолирована. Я стал смотреть код, и он был почти точной копией нашего компилятора. Нет, он был совсем точной!. Ошибок быть не могло. И тут на меня стало снисходить озарение, что ошибки-то в числах! Я внезапно стал уверен, что десятичное представление плавающего числа, каким мы его перенесли в наш симулятор из бинарника (initialization of member variables), в начале работы программы было скомпилено из java кода в другую константу, отличную в битовом представлении от тех, которые в были бинарнике.  Решение было тривиальным, и я пошел будить RST7.