Ближайшая пара точек: проверяем меньше расстояний
Статья и интерактив: https://grundyjs.ru/r/closest-pair/ Какие две точки ближе всего друг к другу? Для 12 точек полный перебор требует 66 вычислений расстояния. Разбираем другой подход — «разделяй и властвуй»: сортируем точки слева направо и делим задачу пополам. Находим ответы половин и проверяем узкую полосу у границы. Если более близкая пара состоит из точек по разные стороны границы, обе точки лежат в этой полосе. Просматриваем их снизу вверх и пропускаем пары, которые не могут улучшить ответ. На этом наборе оба метода находят пару E–F с расстоянием примерно 4,472. При разделении задачи получаем 21 вычисление расстояния вместо 66. Сортировка в этот счётчик не входит; числа относятся к показанному набору из 12 точек. В интерактиве можно двигать, добавлять и удалять точки, выбирать примеры и сравнивать методы по шагам. После правки нажмите «Сначала», затем «Старт». Свой набор можно передать по ссылке. Визуализация — AlgiViz, запись — CanvasTake. Авторская озвучка, без музыки. #ближайшаяПараТочек #геометрия #алгоритмы #ClosestPair #AlgiViz
Название:
Ближайшая пара точек: проверяем меньше расстояний
Категория:
Обучение