Реализация рекурсивного алгоритма
У меня есть два вида объектов, Ball а также Platform, Шары имеют (x,y) координаты и платформы имеют (x_begin, x_end, y), Там может быть не более 80 платформ.
Меня попросили найти кратчайший путь для любого данного Ball наземь (y=0). Обратите внимание, что на выходе это должно быть только минимальное расстояние.
Учитывая ограничения, я думал, что было бы лучше использовать грубую силу: рассчитать все возможные расстояния до земли, а затем вернуть минимум.
Я думал, что сделаю рекурсивную функцию: сначала вычислю расстояние по вертикали до ближайшей платформы, а затем разветвлюсь вправо и влево и снова обратно. Разрывное условие будет, когда все пути достигают земли.
void calculateDistances(Ball b, vector<Platform> ps, vector<float>* distances)
{
//The idea is to have, for every branch
// distances[i] = vertical distance
// distances[i+1] = distance to right
// distances[i+2] = distance to left
Platform* p = NULL;
float d_y = verticalDistanceToNearestPlatform(ps, p); // "p" now holds the platform the ball is on
if (d_y == 0)
return; //already on floor
distances->push_back(d_y);
d_x_right = distanceToRightEdgeOfPlatform(p);
distances->push_back(d_x_right);
d_x_left = distanceToLeftEdgeOfPlatform(p);
distances->push_back(d_x_left);
}
Проблема здесь очевидна … как же я могу сделать это рекурсивным?
Большое спасибо!
PS: эта проблема должна быть решена примерно через два с половиной часа.
Решение
Рекурсивное решение (скажем, horizontalDistanceToGround(x, y)) будет включать вычисление горизонтального расстояния от некоторой произвольной точки (x, y) до ближайшей точки на земле, следующим образом:
- Если между платформой нет
(x, y)и земля, затем вернуть 0. - Если есть какая-то платформа между
(x, y)и землю, затем найдите ближайшую такую платформу (то есть, которая имеет наибольшуюplatform_yменьше, чемy). Если эта платформа находится на(platform_min_x, platform_max_x, platform_y), затем вернуть минимум(x - platform_min_x) + horizontalDistanceToGround(platform_min_x, platform_y)а также(platform_max_x - x) + horizontalDistanceToGround(platform_max_x, platform_y), Это в основном вычисляет минимальное расстояние, необходимое, чтобы добраться от текущей позиции x до конца платформы и оттуда до земли.
Я оставлю поиск ближайшей платформы между (x, y) и почву (если она есть) вам выяснить.
Кратчайшее расстояние от мяча до земли тогда distanceToGround(ball_x, ball_y) + ball_y,
НОТА: Обновлен согласно полезному комментарию @ MooingDuck относительно вертикального расстояния, не имеющего отношения к рекурсии.
Другие решения
Вы можете преобразовать эту проблему в задачу о графе, а затем использовать любое количество алгоритмов поиска графа для ее решения.
Для этого выполните цикл по всем платформам и создайте узлы для каждого из их ребер и для любых точек непосредственно под ребром другой платформы. Соедините все узлы, которые совместно используют общую платформу. Сделайте также вертикальные соединения.
Выполните ту же операцию для земли, но не добавляйте дополнительные узлы для ребер и не соединяйте наземные узлы
Теперь вы можете использовать алгоритм Дейкстры (реконструктивный вариант) для поиска на вашем графике кратчайшего пути между вершиной и каждый указать на дно. Выберите результат с наименьшим значением, и все готово. Алгоритм Дейкстры работает в O (N ^ 2), где N — узел, для простой реализации и O (E + N log N), где E — преимущество интеллектуальной реализации.
Вы также можете использовать A *, что может быть проще реализовать в крайнем случае.
Поиск, чтобы увидеть, на какую платформу ударится шар, падающий с края, легко. Относитесь к земле как к платформе. Сортировка платформ по высоте. Для каждой платформы проходите линейно через все платформы под ней, начиная с ближайшей. Посмотрите, попадает ли значение x верхней платформы в диапазон, определяемый краями нижней платформы. Это занимает O (P ^ 2). (P — количество платформ.)
Это может не дать прямого ответа на ваш вопрос (то есть это не грубая сила), но я думаю, что это лучшее направление, на которое вы можете указать. Плюс, если вы попытаетесь применить грубую силу во всех направлениях, куда может пойти мяч, то это в конечном итоге будет что-то вроде O (2 ^ P), что является неприятно высокой временной сложностью.
detector