Оригинальная постановка.
подскажите по каким ключевым словам копать или нарисуйте схематично схему движения

Предлагаю обсудить алгоритмику.
Пребор факториала 6000 вариантов не предлагать.

Как я вижу решение, нужно отсортировать массив из 6000 элементов в порядке возростания растояний между точками или по другому не тривиальному критерию.

Предлагайте .

AkinaНу да ну да... пойдите по ссылке, почитайте там, ещё пойдите... там есть оригинальная постановка - там и обсуждайте.

Так усторит ?
постановкаЕсть массив с объектами (id, координаты и "максимальное расстояние зоны влияния" каждой точки).
Всего около 6000 объектов. Максимальное расстояние зоны влияния можно представить как окружность с центром в точке расположения данного объекта. Радиус окружности - та самая зона влияния.

Требуется получить перечень пар всех взаимовлияющих объектов по принципу: расстояние между парой объектов не более, чем сумма их максимальных зон влияния.

поправил
ДохтаРКак я вижу решение, нужно отсортировать массив из 6000 элементов в порядке возростания растояний до ближайшей точки или по другому не тривиальному критерию.



Какие еще есть варианты условий сортировки для оптимизации алгоритма.
или варианты оптимального решения решения без сортировки ?

tanglirДохтаРв порядке возростания растояний до ближайшей точкитак количество расстояний-то там O(n^2), чем это лучше решения ТСа? собственно даже а чем оно от него отличается?


Все растояния не хранятся, хранится одно растояние и( или) координаты до одной ближайшей точки.
Точки имеющие одинаковые растояния до ближайшего соседа, которые с очень большой долей вероятности имеют взаимное влияние друг на друга будут находиться в соседних ячейках массива.

И с очень большой долей вероятности выход из цикла или рекурсии будет происходить гораздо раньше полного перебора всех возможных вариантов путей.

[quot softwarer]ДохтаРКак я вижу решение, нужно отсортировать массив из 6000 элементов в порядке возростания растояний между точками
Хм. Между какими именно точками?

14804201
ДохтаРКак я вижу решение, нужно отсортировать массив из 6000 элементов в порядке возростания растояний до ближайшей точки или по другому не тривиальному критерию.



softwarerДохтаРПредлагайте .
ну, сходу я бы попробовал отсортировать по сумме координат точки и затем каждую точку сравнивать с последующими до тех пор, пока не выполнится условие x2+y2-x1-y1>3*D, где D - максимальная "область влияния".

согласен.

Как развитие идеи
Отсортировать в каком нибудь мультимапе значение области влияния как ключ , и индекс элемента массива как значение.

Следующий вопрос ,
алгоритмика выбора начинала перебора вариантов , от минимального растояния между точками или или от максимальной площади области вляния ?

зы с таким ходом мыслей есть шанс изобрести велосипед на тему стоимостного оптимизатора

miksoftДохтаР,

Каково примерно отношение максимального расстояния между точками к максимальному радиусу охвата?

Нет такого в постановке.
В предыдущем посте я высказал предположение , что в зависимости от этого отношения
алгоритм может по разному проводить перебор вариантов .
Либо начиная с минимального растояния , либо начиная с максимальной площади влияния.

Для этого нужно максимально быстро собрать такую ститистику имея координаты точек и радиус влияния.

С радиусом вроде все просто .
С растоянимями чуть сложнее. Не хочется сравнивать все возможные варианты растояний между всеми 6000 точками .

AkinaПеренос обсуждения сюда заставляет думать, что ТС отошёл от попытки оптимизации в рамках SQL... впрочем. в любом случае нужно больше сведений об исходных данных. Соотношение расстояний к зонам влияния, разброс и того, и другого, равномерность распределения точек, частота изменения исходных данных и пр.


Я, ТС этой темы и ТС в оригинальной постановке ( по ссылке ) разные люди.
Мне интересна общая алгоритмика на любом ЯП,
а не методы реализации и оптимизации на SQL и PL/SQL.

Не вижу проблемы в раздельном обсуждении задачи с разных точек зрения.

miksoftДохтаРС растоянимями чуть сложнее. Не хочется сравнивать все возможные варианты растояний между всеми 6000 точками .А все варианты и не нужно. Достаточно оценки по самым крайним точкам. В минимальном случае можно проверить две-четыре точки - которые имеют минимумы и максимум по каждой из координат. Это, конечно, не точное решение, но достаточно точное, чтобы оценить характер задачи.

Не совсем понял.
Что бы найти минимумы и максимумы растояний для каждой точки нужно как минимум пройтись по массиву. И так для каждой точки , если массив не сортирован.
Выходим на решение в лоб , через факториал( декартово произведение) количества точек

miksoftДохтаРпропущено...


Не совсем понял.
Что бы найти минимумы и максимумы растояний для каждой точки нужно как минимум пройтись по массиву. И так для каждой точки , если массив не сортирован.
Выходим на решение в лоб , через факториал( декартово произведение) количества точекНет, я говорю о приближенном решении, которое выполняется значительно быстрее. Чтобы оценить максимальное расстояние нужно найти лишь те точки, которые имеют минимальную или максимальную одну из координат. Если по координатам нет индекса, то это решается одним проходом по массиву точек (линейное время). Если индексы есть, то еще проще - берутся крайние значения из индекса (константное время).

То есть квадрат на пощади которого находятся все точки участвующие в расчете нужно
ставнивать с площадью круга максимального влияния .
Правильно ?

Поправил
авторТо есть квадрат прямоугольник на пощади которого находятся все точки участвующие в расчете нужно
ставнивать с площадью круга максимального влияния .
Правильно ?


С прямоугольником сложнее, площадь пересечения сферических в вакуме прямоугольника и круга
в большестве случаев ( чуть реже чем всегда ) будет меньше ,
чем у квадрата такой же как у прямоугольника площади и и того же круга.

miksoftДохтаРТо есть квадрат на пощади которого находятся все точки участвующие в расчете нужно
ставнивать с площадью круга максимального влияния .
Правильно ?Наверное, можно и так.
Но я говорил о линейных размерах, а не о площадях. Т.е. сравнивать максимальное расстояние среди крайних 2-4 точек и максимальный радиус влияния.

Исходя из 14804982
про площади я сам додумал , я не уверен , но мне кажется , ИМХО
что будет проще площадями оперировать при поиске приблизительного решения.

Ведь зона влияния уже по сути есть площадь из постановки задачи.

В общем случае задача сводится к поиску факта пересечения площадей нескольких окружностей.

AkinaДохтаРМне интересна общая алгоритмика на любом ЯП,
а не методы реализации и оптимизации на SQL и PL/SQL.

Не вижу проблемы в раздельном обсуждении задачи с разных точек зрения.
Именно от того, какими особенностями обладают исходные данные, зависит применимость или неприменимость того или иного метода оптимизации. Какой смысл кластеризовать точки, если распределение близко к равномерному? Зачем выполнять предфильтрацию по одной координате, если расстояния сравнимы с радиусами? Нахрена каждый раз считать с нуля, если между двумя последовательными расчётами в наборе изменяется только одна точка?

Мне ИМХО кажется что данная задача как раз из тех где проще написать свой велосипед ,
чем заставить работать стоимостной оптимизатор оракла.

miksoftДохтаРплощадь пересеченияа это тут причем?

Это ИМХО предположение.