Конечная задача типична для приложений, в которых обрабатываются географические или геометрические данные. Входные данные состоят из двух частей. Первая часть: множество (set) S, состоящее из 5000 точек на поверхности сферы. Каждая точка определяется долготой и широтой. После помещения точек в некоторую структуру данных программа считывает вторую часть входных данных: последовательность из 20 000 точек (заданных долготой и широтой). Для каждой из точек последовательности требуется определить ближайшую к ней точку множества S. Расстояние измеряется по дуге большого круга (или как угловое расстояние между лучами, проведенными из центра сферы в заданные точки).
Маргарет Райт пришлось решать аналогичную задачу в Стенфордском университете в начале 80-х, когда она работала с картами, на которых представлялись данные о распределении некоторых генетических особенностей. Она решала задачу «в лоб», представив S в виде массива значений ширины и долготы. Ближайшая к данной точка находилась путем перебора всех точек и вычисления расстояния до них по сложной геометрической формуле с десятью синусами и косинусами. Программа была простой в написании и выдавала хорошие карты для небольших наборов данных, но для больших карт требовалось несколько часов работы большого компьютера, что выходило далеко за рамки бюджета проекта.
Мне случалось работать с геометрическими задачами и раньше, поэтому Райт попросила меня помочь ей в этом. Потратив на это воскресенье, я придумал несколько причудливых алгоритмов и структур данных для решения задачи. К счастью, как это теперь ясно, для каждого из них потребовалось бы написать много сотен строк кода, потому я пе попытался их закодировать. Когда я описал структуры данных Эпдрю Эппелю (Andrew Appel), ему пришла в голову замечательная идея. Вместо того чтобы решать проблему на уровне структур данных, следовало использовать простейшую структуру для хранения точек (массив), но заняться стоимостью вычисления расстояний между точками. Как бы вы воспользовались этой идеей?
Опубликовал vovan666
April 17 2013 00:01:08 ·
0 Комментариев ·
3582 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
