Введение
Задача - очень интересный вариант игрового ипподрома и эти две задачи:
Источник этой задачи здесь (на немецком языке): c't-Racetrack
Эта задача особенно интересна (и отличается от двух вышеупомянутых проблем), поскольку она объединяет огромное пространство поиска с некоторыми точными условиями, которые должны быть выполнены. Из-за огромного пространства поиска трудно использовать исчерпывающие методы поиска, из-за точных условий приближенные методы также не легко использовать. Из-за этой уникальной комбинации (плюс основополагающая интуиция из физики) проблема увлекательна (и все, что связано с гоночными автомобилями, в любом случае увлекательно ;-)
Вызов
Посмотрите на следующую трассу ( источник ):
Вы должны начать (120,180)
и закончить точно в (320,220)
(«Ziel» на немецком языке), не касаясь одной из стен.
Автомобиль контролируется векторами ускорения вида (a_x,a_y)
- в качестве примера:
(8,-6)
(10,0)
(1,9)
Первое число - ускорение для вектора x, второе - для вектора y. Они должны быть целыми числами, потому что вам разрешено использовать только целые точки на сетке. Дополнительно должно быть выполнено следующее условие:
a_x^2 + a_y^2 <= 100,
Это означает, что ускорение в любом направлении должно быть ниже или равно 10
.
Чтобы увидеть, как это работает, взгляните на следующую картинку ( источник ):
В качестве примера: начиная с (120,180)
ускорения по 8
оси X и по -6
оси Y. Для следующего шага это ваша скорость, где вы добавляете свое ускорение, (10,0)
чтобы получить (физически правильное) ваше следующее результирующее движение (к точке (146,168)
. Результирующее движение - это то, что имеет значение, когда дело доходит до того, касались ли вы одной из стен. На следующем шаге. Вы снова добавляете свой следующий вектор ускорения к текущей скорости, чтобы получить следующее движение и т. д. Таким образом, на каждом шаге у вашего автомобиля есть положение и скорость. (На иллюстративном рисунке выше синие стрелки обозначают скорость, оранжевые стрелки). для ускорения и темно-красные стрелки для результирующего движения.)
В качестве дополнительного условия у вас должна быть (0,0)
конечная скорость, когда вы находитесь на финишной точке (320,220)
.
Выходными данными должен быть список векторов ускорения в вышеупомянутой форме.
Победителем становится тот, кто предоставляет программу, которая находит решение с наименьшим вектором ускорения.
Tiebreaker
Кроме того, было бы здорово показать, что это оптимальное решение и является ли это единственным оптимальным решением или существует несколько оптимальных решений (и какими они являются).
Также было бы хорошо, если бы вы могли дать общее представление о том, как работает ваш алгоритм, и прокомментировать код, чтобы мы могли его понять.
У меня есть программа, которая проверяет, является ли данное решение действительным, и я буду давать отзывы.
Приложение
Вы можете использовать любой язык программирования, но я был бы особенно рад, если бы кто-то использовал R, потому что я часто использую его в своей повседневной работе и как-то привык к нему :-)
Приложение II
Впервые я учредил награду - надеюсь, что этот мяч зашкаливает (или лучше: за рулем автомобиля :-)
print "(10,42)\n(62,64)..."
?Ответы:
Python, 24 шага (работа в процессе)
Идея состояла в том, чтобы сначала решить непрерывную задачу, значительно сократив пространство поиска, а затем квантовать результат в сетке (просто округляя до ближайшей точки сетки и просматривая окружающие 8 квадратов)
Я параметризирую путь как сумму тригонометрических функций (в отличие от полиномов, они не расходятся и их легче контролировать). Я также управляю скоростью напрямую, а не ускорением, потому что легче выполнить граничное условие, просто умножив весовую функцию, которая стремится к 0 в конце.
Моя целевая функция состоит из
-экспоненциальной оценки для ускорения> 10-
полиномиальной оценки для евклидова расстояния между последней точкой и целью
-высокой постоянной оценки для каждого пересечения со стеной, уменьшающейся к краям стены
Чтобы минимизировать счет, я добавляю все это в оптимизацию Nelder-Mead и жду несколько секунд. Алгоритму всегда удается дойти до конца, остановиться на нем и не превысить максимальное ускорение, но у него есть проблемы со стенами. Тропа либо телепортируется через углы и застревает там, либо останавливается рядом со стеной с целью прямо напротив (левое изображение)
Во время тестирования мне повезло, и я нашел путь, который был многообещающим (правильное изображение), и после дополнительной настройки параметров я мог бы использовать его как начальную догадку для успешной оптимизации.
Квантование
После нахождения параметрического пути пришло время удалить десятичные точки. Просмотр окрестности 3x3 уменьшает пространство поиска примерно с 300 ^ N до 9 ^ N, но все еще слишком велик и скучен для реализации. Прежде чем идти по этому пути, я попытался добавить термин «Привязать к сетке» к целевой функции (закомментированные части). Чтобы получить решение, потребовалось еще сто шагов оптимизации с обновленной целью и простым округлением.
Количество шагов было фиксированным и не являлось частью оптимизации, но поскольку у нас есть аналитическое описание пути (и поскольку максимальное ускорение значительно ниже 10), мы можем использовать его в качестве отправной точки для дальнейшей оптимизации с меньшим числом временные шаги
To Do: GUI, который позволяет вам нарисовать начальный путь, чтобы получить грубое чувство направления. Все лучше, чем случайная выборка из 14-мерного пространства
источник