Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Сортировка по географической близости
 
#1
13.02.2019 17:51:10
Добрый вечер
Есть таблица с данными географических точек (строка - точка), столбец с широтой, столбец с долготой. Необходимо сортировать таблицу таким образом, чтобы каждая следующая строка (точка) была ближайшей географически к предыдущей.
 
 
 
#2
13.02.2019 18:01:54
mutkoti, а начальной точкой будет та что в первой строке?
Вот горшок пустой, он предмет простой...
 
 
 
#3
13.02.2019 18:10:09
Да
 
 
 
#4
13.02.2019 18:12:40
Также интересен вариант, со сравнением расстояния до первой точки, а не предыдущей строки
 
 
 
#5
13.02.2019 18:36:33
Доброе время суток.
При таком условии
Цитата
mutkoti написал:
Необходимо сортировать таблицу таким образом, чтобы каждая следующая строка (точка) была ближайшей географически к предыдущей
и дополнительном ограничении
Цитата
PooHkrd написал:
начальной точкой будет та что в первой строке
имеет ли задача решение?
Пусть даны координаты точек на прямой a 0, b -1, c 2, d 3, e -2. Начальная точка a. Покажите, как расставить точки после а, строго следуя вашему условию?
 
 
 
#6
13.02.2019 22:41:33
mutkoti,
Добро времени суток!
Если применить в расчете тригонометрическую формулу нахождения расстояний между точками на сфере, то можно легко ответить на второй вопрос:
Цитата
со сравнением расстояния до первой точки, а не предыдущей строки
Задача с нахождением каждой последующей ближайшей точки потребует макрос с итерациями по перебору и подстановке в новую цепочку точек с минимальным расстоянием.
 
 
 
#7
14.02.2019 07:12:44
Андрей VG,
Другой вариант это не дополнительное условие, другая задача. Она попроще первой.
 
 
 
#8
14.02.2019 08:08:06
Цитата
mutkoti написал:
чтобы каждая следующая строка (точка) была ближайшей географически к предыдущей.
По своей формулировке задача похожа на задачу коммивояжера.
Сколько всего координат? В зависимости от количестве можно применять разные решения от полного перебора (до 12-13 точек), динамического программирования (20-25 точек), МВиГ (применяемость зависит от графа), до жадного (от 30 и выше) с небольшой оптимизацией или применять генетические алгоритмы, муравьиных колоний и др.

PS: решал задачу коммивояжера для нескольких сотен точек, отклонения от оптимальных решений не более 1-2%
Изменено: MCH - 14.02.2019 08:33:50
 
 
 
Страницы: 1
Наверх