Липецкие форумы
25 Августа 2019, 08:44:35 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
Страниц: [1]   Вниз
  Печать  
Автор Тема: Алгоритм  (Прочитано 2332 раз)
0 Пользователей и 1 Гость смотрят эту тему.
CTAXAHOB
Заслуженный
****

Рейтинг: -43
Offline Offline

Сообщений: 510



Просмотр профиля
« : 12 Мая 2011, 20:26:18 »

Есть массив (много) точек на плоскости. Дана ещё одна, необходимо найти ближайшую к ней из исходных. Существует какой-нибудь алгоритм, кроме тотального перебора? Или подскажите, как надо спросить у Яндекса/Гугля?
« Последнее редактирование: 12 Мая 2011, 20:27:57 от CTAXAHOB » Записан
Сулико
Гость
« Ответ #1 : 12 Мая 2011, 20:45:47 »

Кинуть вокруг этой еще одной точки эпсилон-окрестность заданного радиуса, в ней методом Монте-Карло найти точки и выбрать ближайшую, а если точек нет, увеличить радиус. Работать хорошо будет при большой плотности точек.
Записан
CTAXAHOB
Заслуженный
****

Рейтинг: -43
Offline Offline

Сообщений: 510



Просмотр профиля
« Ответ #2 : 14 Мая 2011, 17:45:53 »

А как проверять, какие точки уже попали в эпсилон-окрестность? Опять перебором? Нужно же обратное решение - массив задан неизменно, а нужная (которая дана) имеет случайные координаты.
« Последнее редактирование: 14 Мая 2011, 17:50:22 от CTAXAHOB » Записан
OneHalf
Заслуженный
****

Рейтинг: -43
Offline Offline

Сообщений: 612



Просмотр профиля
« Ответ #3 : 14 Мая 2011, 20:28:36 »

я в математике может и не силен, но не представляю можно ли не обращаясь к точке (массиву) узнать попадает ли точка куда либо или нет. Ведь как то нужно проверить ее расстояние до заданной точки, а если не проверишь вдруг она окажется как раз той что нужна.  Перебор как ни крути неизбежен. другое дело можно как то попробовать оптимизировать вычисления, например
пример совсем приблизительный
взять первую точку вычислить расстояние до нужной точки обозначить D. Затем брать перебирать остальные точки и не вычислять расстояние а проверять расстояние между Xами  точек если оно больше D abs(x1-x2)>D то расстояние можно даже не считать иначе проверить и между Y ками  если всетаки входит вычислить снова расстояние и если оно меньше запомнить в D. Но в худшем случае (если точки в массиве с каждым разом все ближе и ближе) к имеющимся вычислениям расстояния а это квадраты корни (накладненько) добавяться еще и вычисления Xов и Yков. Также можно отсортировать массив если сравнение находить придется точку несколько раз для разных точек.
А так что бы не проверять что за точка т.е. не обращаться к данному элементу массива думаю не возможно, а вдруг там окажется как раз нужная. Или что то в условиях задачи не досказанно
« Последнее редактирование: 14 Мая 2011, 20:37:07 от OneHalf » Записан

За Родину! За Гелики ФСБ! За собак Шувалова! За офшор Ролдугина! За Роттенбергов и Пароход Абрамовича! За дворцы Путина и Гундяева!
PozitiFF
Новичок
*

Рейтинг: 0
Offline Offline

Сообщений: 80



Просмотр профиля
« Ответ #4 : 14 Мая 2011, 21:07:21 »

Алгоритм Дейкстры. Теория графов  Подмигивающий
Записан

clever
Новичок
*

Рейтинг: 0
Offline Offline

Сообщений: 47


Просмотр профиля
« Ответ #5 : 14 Мая 2011, 21:16:53 »

если массив типа (x,y). Тогда продублировать в два массива, добавить ссылки на объект (запись, структуру) что бы из можно было обратиться к точке в этих массивах по ссылке, отсортировать первый по x, в второй по y. Ближайшая точка будет среди соседних.
Допустим есть точки 1(1;1),2(2;3),3(2;1),4(1;4),5(3;1)
добавим ссылку (или индекс в исходном массиве) и разделим на два отсортированных массива. Индекс буду писать перед скобкой
первый массив сотрируем по Х (ну и дополнительно по У, хотя это не критично)
1(1;1),4(1;4),3(2;1),2(2;3),5(3;1)
второй по У
1(1;1),3(2;1),5(3;1),2(2;3),4(1;4)
Что бы найти ближайшую, например к 2(2;3) надо рассмотреть всего несколько соседних точек (3,4,5). Причем если квадрат разности по одной координате между точками больше найденного минимального расстояния, то дальше по этой координате можно  не искать.
Если же массив наподобии битмапа, где большой двухмерный массив с флагами есть точка или нет, то там, вероятно, проще перебором.
Записан

Alle Ding' sind Gift, und nichts ohn' Gift; allein die Dosis macht, daß ein Ding kein Gift ist.
Сулико
Гость
« Ответ #6 : 14 Мая 2011, 22:38:50 »

А как проверять, какие точки уже попали в эпсилон-окрестность? Опять перебором? Нужно же обратное решение - массив задан неизменно, а нужная (которая дана) имеет случайные координаты.

Если массив "обычный" и элементы его доступны только через некий абстрактный номер, скорее всего, стоит задуматься о более подходящей структуре для хранения данных - каком-нибудь ассоциированном списке, в котором точки будут доступны через собственные координаты, а не через индекс. Тогда можно будет сгенерировать по ММК кучку координат из заданной окрестности и проверить наличие точек в этих координатах. Или тупо все точки из окрестности проверить. Или по расширяющейся спирали обходить все пространство вокруг заданной точки до встречи с другой.
Записан
CTAXAHOB
Заслуженный
****

Рейтинг: -43
Offline Offline

Сообщений: 510



Просмотр профиля
« Ответ #7 : 15 Мая 2011, 11:24:40 »

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

если массив типа (x,y). Тогда продублировать в два массива, добавить ссылки на объект (запись, структуру) что бы из можно было обратиться к точке в этих массивах по ссылке, отсортировать первый по x, в второй по y. Ближайшая точка будет среди соседних.
Нельзя так делать - правильный ответ получен не будет. Вы предлагаете аналог разбиения плоскости на "подплоскости" с раздельным поиском в каждой "подплоскости", тогда если ближайшая точка от нужной будет в другой части плоскости, подобный алгоритм её не найдёт. Мы ищем ближайшую из массива к одной, массиву не принадлежащей. Возьмите свой собственный пример, и точку Х(3,4). Ближайшей к ней будет точка 2(2,3), а ваш алгоритм её не найдёт. Upd. Заодно отсеялся и метод занесения точки в массив, с поиском в отсортированных массивах.

Алгоритм Дейкстры. Теория графов  Подмигивающий
Вообще не из этой области решение Улыбающийся

Если массив "обычный" и элементы его доступны только через некий абстрактный номер, скорее всего, стоит задуматься о более подходящей структуре для хранения данных - каком-нибудь ассоциированном списке, в котором точки будут доступны через собственные координаты, а не через индекс. Тогда можно будет сгенерировать по ММК кучку координат из заданной окрестности и проверить наличие точек в этих координатах. Или тупо все точки из окрестности проверить. Или по расширяющейся спирали обходить все пространство вокруг заданной точки до встречи с другой.
Все точки так и заданы - координатами. Но они не "нарисованы", проверять цвет пикселя не пойдёт, и для того чтобы проверить, попадает ли какая-либо точка в окрестность нам снова необходимо будет "перебрать" весь начальный массив (бинарный список етц). Это решение не той задачи задачу - если бы была задана одна, а потом добавлялся бы массив, можно было бы проверять, попадает ли новая точка в окрестность заданной, и хранить ближайшую.
« Последнее редактирование: 15 Мая 2011, 12:03:18 от CTAXAHOB » Записан
clever
Новичок
*

Рейтинг: 0
Offline Offline

Сообщений: 47


Просмотр профиля
« Ответ #8 : 15 Мая 2011, 18:58:20 »

Мы ищем ближайшую из массива к одной, массиву не принадлежащей. Возьмите свой собственный пример, и точку Х(3,4). Ближайшей к ней будет точка 2(2,3), а ваш алгоритм её не найдёт.
Ну это существенное замечание, но алгоритм найдет. Точнее я дал идею, а не алгоритм, так что можно учесть в алгоритме это ваше существенное замечание.
Быстрым алгоритмом наподобии бинарного поиска (сложность логарифмическая) ищем ближайшую к М(3,4) в каждом из списков по соответствующей координате точки M.
X_Order = 1(1;1),4(1;4),3(2;1),2(2;3),5(3;1)
Y_Order = 1(1;1),3(2;1),5(3;1),2(2;3),4(1;4)
в  X_Order  - это точка 5, а в Y_Order - точка 4.
Далее начинаем от найденных точек искать ближайшую. В качестве метрику буду брать квадрат расстояния d(Point1,Point1), что бы проще было.
X_Order: d(М,5) = 9. d(М,2) = 2 (это минимальное расстояние). d(M,3) = 10.  d(M,4) = 4. все, дальше можно не искать, т.к. квадрат разности по координате X между 4й точкой и М уже больше минимального расстояния 2.
Пройдясь аналогично по списку Y_Order мы обнаружим ближайшую точку 2 и остановим поиск на точке 5, т.к. квадрат разности по координате Y между 5й точкой и М будет больше найденного минимального расстояния 2.
Возможно, достаточно проверить по одному списку, тут думать надо.
Быстрее будет для разряженных точек, что бы не было много точек с совпадающими координатами. Для некоторых случаев будет быстрее попеременно проверять по двум спискам в обоих направлениях.
И не совсем понятно что именно надо. Надо ли найти первую ближайшую или надо найти все. Будет ли исходный массив динамический меняться или он задан постоянно. Но для указанной задачи в теме, как я ее понял, эта идея подходит.
Записан

Alle Ding' sind Gift, und nichts ohn' Gift; allein die Dosis macht, daß ein Ding kein Gift ist.
fox_
Новичок
*

Рейтинг: 0
Offline Offline

Сообщений: 1


Просмотр профиля
« Ответ #9 : 15 Мая 2011, 21:45:19 »

Хранить в массиве в упорядоченном виде. Тогда при первой встреченной можно прекращать поиск. Как вариант, использовать Б-дерево. В самом дереве достаточно хранить в качестве ключей индекс массива, содержащего данную координату.
« Последнее редактирование: 15 Мая 2011, 21:47:09 от fox_ » Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by SMF 1.1.16 | SMF © 2006, Simple Machines
Minerva Theme | The Simple Machines Forum Directory