Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
Задачка не пятничная, так как еще не смог реализовать ни одно из решений ее.
Имеем список id с их координатами GPS.
Нужно разбить 51(кол-во изменяемое) ID на 5(кол-во изменяемое) примерно равных по кол-ву ID группы, по принципу наиболее приближенных координат друг к другу (приоритет при разбивки отдан в сторону максимального приближения по кол-ву id в каждой группе - чтоб были максимально равно по кол-ву.).
with t as
(Select 1 as ID, '55,77258' as LATITUDE, '37,57602' as LONGITUDE from dual union all
Select 2 as ID, '55,71963' as LATITUDE, '37,41848' as LONGITUDE from dual union all
Select 3 as ID, '55,74752' as LATITUDE, '37,58123' as LONGITUDE from dual union all
Select 4 as ID, '55,72552' as LATITUDE, '37,75491' as LONGITUDE from dual union all
Select 5 as ID, '55,65543' as LATITUDE, '37,57204' as LONGITUDE from dual union all
Select 6 as ID, '55,63011' as LATITUDE, '37,47448' as LONGITUDE from dual union all
Select 7 as ID, '55,64064' as LATITUDE, '37,53073' as LONGITUDE from dual union all
Select 8 as ID, '55,57735' as LATITUDE, '37,47615' as LONGITUDE from dual union all
Select 9 as ID, '55,87732' as LATITUDE, '37,55912' as LONGITUDE from dual union all
Select 10 as ID, '55,76529' as LATITUDE, '37,65536' as LONGITUDE from dual union all
Select 11 as ID, '55,77312' as LATITUDE, '37,65463' as LONGITUDE from dual union all
Select 12 as ID, '55,78814' as LATITUDE, '37,61266' as LONGITUDE from dual union all
Select 13 as ID, '55,82432' as LATITUDE, '37,63205' as LONGITUDE from dual union all
Select 14 as ID, '55,71549' as LATITUDE, '37,39625' as LONGITUDE from dual union all
Select 15 as ID, '55,80336' as LATITUDE, '37,61871' as LONGITUDE from dual union all
Select 16 as ID, '55,86987' as LATITUDE, '37,65716' as LONGITUDE from dual union all
Select 17 as ID, '55,85339' as LATITUDE, '37,35167' as LONGITUDE from dual union all
Select 18 as ID, '55,76142' as LATITUDE, '37,56828' as LONGITUDE from dual union all
Select 19 as ID, '55,80824' as LATITUDE, '37,52792' as LONGITUDE from dual union all
Select 20 as ID, '55,72718' as LATITUDE, '37,60694' as LONGITUDE from dual union all
Select 21 as ID, '55,66829' as LATITUDE, '37,76403' as LONGITUDE from dual union all
Select 22 as ID, '55,58782' as LATITUDE, '37,67063' as LONGITUDE from dual union all
Select 23 as ID, '55,75198' as LATITUDE, '37,59299' as LONGITUDE from dual union all
Select 24 as ID, '55,81632' as LATITUDE, '37,81107' as LONGITUDE from dual union all
Select 25 as ID, '55,80462' as LATITUDE, '37,51353' as LONGITUDE from dual union all
Select 26 as ID, '55,84534' as LATITUDE, '37,4387' as LONGITUDE from dual union all
Select 27 as ID, '55,98404' as LATITUDE, '37,17615' as LONGITUDE from dual union all
Select 28 as ID, '55,77271' as LATITUDE, '37,66116' as LONGITUDE from dual union all
Select 29 as ID, '55,70301' as LATITUDE, '37,53101' as LONGITUDE from dual union all
Select 30 as ID, '55,74793' as LATITUDE, '37,70117' as LONGITUDE from dual union all
Select 31 as ID, '55,86069' as LATITUDE, '37,48288' as LONGITUDE from dual union all
Select 32 as ID, '55,7703' as LATITUDE, '37,84249' as LONGITUDE from dual union all
Select 33 as ID, '55,84743' as LATITUDE, '37,34974' as LONGITUDE from dual union all
Select 34 as ID, '55,75218' as LATITUDE, '37,5456' as LONGITUDE from dual union all
Select 35 as ID, '55,75869' as LATITUDE, '37,63273' as LONGITUDE from dual union all
Select 36 as ID, '55,65896' as LATITUDE, '37,75591' as LONGITUDE from dual union all
Select 37 as ID, '55,85718' as LATITUDE, '37,43204' as LONGITUDE from dual union all
Select 38 as ID, '55,76186' as LATITUDE, '37,62259' as LONGITUDE from dual union all
Select 39 as ID, '55,7243' as LATITUDE, '37,57725' as LONGITUDE from dual union all
Select 40 as ID, '55,75954' as LATITUDE, '37,65826' as LONGITUDE from dual union all
Select 41 as ID, '55,77588' as LATITUDE, '37,66039' as LONGITUDE from dual union all
Select 42 as ID, '55,73834' as LATITUDE, '37,41064' as LONGITUDE from dual union all
Select 43 as ID, '55,65471' as LATITUDE, '37,76525' as LONGITUDE from dual union all
Select 44 as ID, '55,60931' as LATITUDE, '38,08095' as LONGITUDE from dual union all
Select 45 as ID, '55,80045' as LATITUDE, '37,3961' as LONGITUDE from dual union all
Select 46 as ID, '55,88579' as LATITUDE, '37,66005' as LONGITUDE from dual union all
Select 47 as ID, '55,65421' as LATITUDE, '37,75856' as LONGITUDE from dual union all
Select 48 as ID, '55,89739' as LATITUDE, '37,61464' as LONGITUDE from dual union all
Select 49 as ID, '55,71072' as LATITUDE, '37,61329' as LONGITUDE from dual union all
Select 50 as ID, '55,76063' as LATITUDE, '37,61495' as LONGITUDE from dual union all
Select 51 as ID, '55,78619' as LATITUDE, '37,67849' as LONGITUDE from dual )
select * from t
9 апр 10, 14:30    [8605446]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
буду признателен за любые мысли, которые помогут решить задачу. Сейчас пробую задавать некую абстрактную точку и высчитывать расстояние до нее для каждого id - но сама идея, на мой взгляд, кривая - а других у меня просто нет. Выручайте. Заранее признателен.
9 апр 10, 14:44    [8605618]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
в поисках,

(имхо) исходная постановка критики не выдерживает.
если над ней ещё поработаете, то, может быть, получится интересная задача
9 апр 10, 15:08    [8605864]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
orawish
Да, объяснять я, конечно, не умею... если не трудно: скажите что вам не понятно?!

Из заданного количества Id нужно сделать заданное кол-во групп, каждая из которых будет содержать примерно равное количество id и также в ней будут находиться id максимально близко расположенные друг к другу по координатам GPS. (во)
9 апр 10, 15:15    [8605931]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
Андрей Панфилов
Member

Откуда: Москва > Melbourne
Сообщений: 3778
в поисках,

а какие допущения могут быть? т.е. например в простом линейном случае:
1,2,3,500,998,999,1000
как разбить на 2 или 3 группы?
9 апр 10, 15:18    [8605962]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
AmKad
Member

Откуда:
Сообщений: 5222
в поисках,

Задача кластеризации?
9 апр 10, 15:19    [8605964]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
в поисках,

  xx
xxxxx
xxx
xxxxxxxxxxxxxxxxxx
xxxxxxxx xxxxxxxxx
xxxxxxxxxxxxx
x x
x x

вот такую картину маслом любой ребёнок легко разделит на 5 групп.

а куда тут монтировать ваше
..приоритет при разбивки отдан в сторону максимального приближения по кол-ву id в каждой группе - чтоб были максимально равно по кол-ву..
?
9 апр 10, 15:42    [8606187]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
в поисках
немного упростим что ли: Всего 5 групп, 50 Id. разбить на группы по 10 ID чтоб в каждой группе оказались ID максимально приближенные друг к другу по координатам GPS...
Не?
9 апр 10, 16:02    [8606430]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
4ton
Member

Откуда:
Сообщений: 291
в поисках,

я бы попытался применить генетические алгоритмы (что это такое - можно найти даже в вики).
Генерите некоторое количество случайных решений (т.е они вовсе не обязаны быть хорошими).
Целевой функцией для особи будет сумма по всем группам сумм расстояний между всеми точками в группе
Далее начинаете итерации скрещиваний и мутаций. Количество итераций ограничиваете приемлемым временем.
9 апр 10, 16:14    [8606567]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
бум искать .... спасибо за наводки.
9 апр 10, 19:18    [8608032]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
апну, что ли .. авось у кого то желание появиться порешать такую задачку...
10 апр 10, 17:32    [8609998]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
suPPLer
Member

Откуда: Харків, Україна
Сообщений: 7794
Блог
в поисках,

что должно быть критерием оптимальности? Наименьшее среднее сумм расстояний "от-всех-до-всех" в группах?
10 апр 10, 17:59    [8610065]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
suPPLer
Угу. "Наименьшее среднее сумм расстояний "от-всех-до-всех" в группах"(С)
10 апр 10, 18:27    [8610135]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
в поисках
Guest
ну или выстроить список id так, чтоб каждый следующий был максимально близок к предыдущему (сейчас этим и занимаюсь - чето клеиться...)- хы?
цель задачи: имеем меняющийся список мест(id)- и их нужно посетить, при этом , желательно, распределить id по группам по максимальной приближенности друг к другу, или максимально близкий к предыдущему в группу (это корректнее)...
ну или чтобы в каждой группе общая удаленность точек друг от друга (или следующей от предыдущей) были примерно одинаковы - вроде как более справедливое деление на группы, относительно тех кто будет ехать. -)))
Не знаю, если честно - для меня эта область новее некуда- пытаюсь -экспериментирую....
10 апр 10, 20:00    [8610394]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
miksoft
Member

Откуда:
Сообщений: 38540
в поисках,

А для чего это вам? Для какой предметной области?
Может, стоит не искать абстрактных решений, а поискать решения, подходящие для конкретной предметной области?
10 апр 10, 20:07    [8610410]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
suPPLer
Member

Откуда: Харків, Україна
Сообщений: 7794
Блог
в поисках
ну или выстроить список id так, чтоб каждый следующий был максимально близок к предыдущему?


Представим, что Ваши точки - вершины графа, каждая из которых соединена со всеми остальными. Вы определитесь, что Вам надо сделать: решить задачу коммивояжёра; найти наименьшее остовное дерево (это алгоритмы Прима, Краскала и Радо — Эдмондса) и поделить его на части.

IMHO, для стартовой задачи топика Вам подойдёт алгоритм Краскала как алгоритм по нахождению остовного дерева (в Вашем случае леса не будет) с минимальным весом. Затем можно разбить полученное дерево на заданное количество подграфов.
10 апр 10, 20:33    [8610481]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
GL
Member

Откуда: Харьков
Сообщений: 1513
suPPLer,

Красивый алгоритм. Правда, у меня так и не получилось реализовать его при помощи SQL (без PL/SQL) - не смог реализовать отсечение рёбер, приводящих к циклу.
В model - не силён, но может быть кто-то сможет...

Единственное что - почему не будет леса? Именно лес, на мой взгляд, и будет. И - более того - именно по деревьям в лесу и имеет смысл делить на заданное количество групп.
10 апр 10, 21:31    [8610604]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
suPPLer
Member

Откуда: Харків, Україна
Сообщений: 7794
Блог
GL
Единственное что - почему не будет леса?


Потому что после предложенного мной перевода множества вершин в граф мы получаем связный граф (aka связанный), и компонент связности всего одна - всё множество вершин. После применения алгоритма Краскала мы получим одно остовное дерево. А уж его надо будет превращать самостоятельно в остовный лес путём разбиения дерева на подграфы (необязательно, и даже скорее всего не, связные).


Ещё один алгоритм, как модификация алгоритма Прима:
0. Начать с точки, наиболее близкой к точке с координатами (MINLAT, MINLON), где MINLAT и MINLON - соответственно, минимальные широта и долгота для данного набора точек.
1. Набрать группу точек по алгоритму Прима.
2. Если ещё остались точки, вернутся к пункту 0.
3. Конец.
10 апр 10, 22:04    [8610706]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
GL
Member

Откуда: Харьков
Сообщений: 1513
suPPLer
GL
Единственное что - почему не будет леса?


Потому что после предложенного мной перевода множества вершин в граф мы получаем связный граф (aka связанный), и компонент связности всего одна - всё множество вершин.
Угу, но алгоритм выбирает рёбра. И никто не гарантирует, что выбраны будут связанные рёбра. Например:

(0,0) (1,0) (0,2) (1,2)

Алгоритм очевидно выберет рёбра (0,0)-(1,0) и (0,2)-(1,2), что есть несвязный граф.

Собственно, мы отклонились от решения и спор уже не по теме
10 апр 10, 22:35    [8610796]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
onstat-
Member

Откуда:
Сообщений: 6941
в поисках

цель задачи: имеем меняющийся список мест(id)- и их нужно посетить, при этом , желательно, распределить id по группам по максимальной приближенности друг к другу, или максимально близкий к предыдущему в группу (это корректнее)...


Задача комивояжера

Вариатов ( алгоритмов) решений - масса.

ps Все уже посчитано до нас :)
10 апр 10, 23:36    [8611056]     Ответить | Цитировать Сообщить модератору
 Re: нахождение ближайших точек по GPS координатам.  [new]
mayton
Member

Откуда: loopback
Сообщений: 49731
Ммм... это не из области графов. Это ближе к нейросетям. Задача автоматической кластеризации грубо решается численными сходящимися методами. Например ввести нелинейную функцию гравитации между точками и заставив их двигаться под воздействием суммарного вектора сил. Применив её несколько раз к множеству мы получим эффект "примагничивания" точек к их центрам масс. Правда в этом случае мы можем получить меньшее или большее количество кластеров чем было задано. Впрочем это решается коррекцией гравитации. Альтернативный вариант - зафиксировать исходные точки (X). Бросить в измеряемое пространство новые точки (Y) - виртуальные центры кластеров (случайным образом). Множество Y может свободно двигаться. Применить нелинейную гравитацию точек X к воображаемым центрам Y. Через несколько эпох центры Y займут положение весьма близкое к искомому.
11 апр 10, 01:04    [8611368]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить