Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Тут Вы ошибаетесь. Запустите несколько раз, алгоритм paul иногда выдает другие результаты, что впрочем не удивительно, если к нему присмотреться (ведь модуль разности векторов и разность модулей - это не одно и то же). А вот в этом, специально построенном примере, уже Игоря метод выдает другой результат.
|
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Нет, идея верна, ее именно что надо подправить. Квадраты лучше кругов тем, что позволяют для отбора содержащихся в нем точек использовать заранее созданные индексы. Нужно таким способом найти минимальный квадрат, в котором есть точка, описать вокруг него круг. В нем заведомо будет точка, на которой достигается минимум. Затем надо вокруг этого круга описать еще один квадрат. Его сторона будет в sqrt(2) раз больше стороны первого квадрата и минимальная точка будет заведомо внутри него. Отбираем все точки внутри этого квадрата (с помощью того же индекса!) и далее уже используем перебор. |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
В градиентном методе вычисляются частные производные в заданных точках, на основании которых определяется, в какую сторону и какой величины сделать шаг. Он вовсе не обязан попадать в какую-либо заранее определенную сетку. Он может попасть в любую точку. Там сетки, как таковой, вообще нет. Цитата:Вовсе не единственный. Метод, который я описал в предыдущем посте, тоже дает однозначное решение, но не предполагает полного перебора. |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
Леонид. Как в градиентном методе на основе экспериментальных (дискретных) точек строится функционал - обычно методом МНК, те задаётся вид полинома и вычисляются его коэффициенты, это первое. Второе, от гипотизы полинома зависит совпадут ли значения в узловых точках с заданной точностью, в простейшем случае применяют кусочно-линейную апроксимацию, те между точками строится "прямая-плоскость-итп". Поэтому, тангенс угла наклона будет определяться узловыми точками, собственно "нафига" вычислять градиент с шагом меньше чем шаг узлов - это только создавать себе трудности полагаясь на правильность гипотезы. Более того, принятие решения о направлении движения больше узлового диапазона - это уже фактически метод случайного поиска. Частные производные я намереннно не упоминал, поскольку принцип от этого не меняется, только возникают дополнительные тонкости в виде пространственных "сёдел" итп, кстати и в одномерном можно получить "седло".
Ссылку приведи. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Метод градиентного спуска Цитата:Собственно "в предыдущем посте" это и была ссылка. |
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Леонид, ты совершенно прав, просто туго соображаю в 2 часа ночи.
1) Отсекать нужно именно квадрат, а не прямоугольник. потому что... 2) После отсечения квадрата искать нужно ТОЛЬКО внутри вписанного в него круга (ну или чуть перефразируя - принимать в расчёт только те точки, для которых расстояние до искомой <=Delta) - т.к. действительно точки в "углах" квадрата могут быть не ближайшими. 3) Если в результате "поиска в круге" ничего не найдено, то следующий шаг должен быть в умножении Delta на SQRT(2) - т.е. переходим к "описанной" окружности и соответсвенно описанному вокруг этой описанной окружности квадрату - в нём уже гарантировано будут точки. Альтернативно (и чуть более оптимально) - таки определить на шаге 2 минимальное расстояние внутри квадрата (всей его площуди полностью), НО если это расстояние окажется > Delta то расшиить квадрат поиска до величины этого расстояния (т.е. добавить те "потенциальные" области вне первого квадрата) в которых могут быть более оптимальные точки. Замечание насчёт Locate принимается - да, это может дать очень неплохой выигрыш - более того, можно улучшить алгоритм, проводя после "нахождения" точек внутри квадрата несколько операций "уменьшения" квадрата поиска - причём сами коэффициенты как "расширения" так и "сужения" области поиска можно подбирать - не обязательно именно "удваивать" размер - я даже склоняюсь к увеличению дельты более чем в 2 раза за шаг - а то в моём примере пришлось проводить 11 расширений зоны поиска, прежде чем был найден первый "непустой" квадрат. ------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 02.03.10 15:34 |
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Вот полный вариант этой идеи.
------------------ WBR, Igor |
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
В дополнение: на обработке "второго квадрата" можно сэкономить, если рассматривать не все его точки, а только "новые" - т.е. добавив в условие отбора AND id NOT IN (SELECT id FROM t2) - но при этом конечно же надо заполнить результат поиска в первом квадрате и сравнивать с ним... Хотя для "равномерно" заполненного поля и поиска внутри этого поля по идее существенного выигрыша не будет - там и так немного точек попадает в квадрат.
Плюс к тому алгоритм находит лишь первую подходящую точку - можно его чуть изменить, чтобы он находил ВСЕ "равноудалённые". ------------------ WBR, Igor |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
И-и-и что, это я изучал в 1981 -82г в курсе вычислительной математики (смотрика, ещё кое что помню из "верхней" школы ) В чем противоречие между моими словами и приведенной ссылкой? А так же, чем отличается ЧИСЛЕННОЕ "решение" градиента для непрерывной ф-ии и для ф-ии заданной дискретами? ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Да. Кое что... Цитата:Для "ф-ии заданной дискретами" (заметим, что в нашем случае - это совершенно произвольное множество точек, без какой либо сетки и какого либо шага) метод градиентного спуска, который Вы называете '"решение" градиента', вообще не определен, поскольку для таких функций не определено понятие градиента, да и экстремума, кстати, тоже. Цитата: Вот в этом и состоит. Но если после прочтения ссылки это все еще не понятно, то подумайте, как Вы будете считать частные производные для таких функций, хотя бы приближенно? |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
Строго говоря ДА. Но ищем-то мы численным методом, те берём начальную точку (в ней значение ф-ии известно), берём приращение, вычисляем в нём значение ф-ии, ищем градиент, делаем новый шаг, проверяем на min/max. В простейшем случае кусочно-линейная апроксимация, где фактически градиент уже определён, приращения известны, значение ф-ии известно.
А как будет считаться частная производная для аналитической ф-ии и чем этот расчет в принципе будет отличаться от заданных дискретов (только шагом приращения)? ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Игорь, в реальной задаче искомая точка будет не сильно далеко от существующих, так что алгоритм в самый раз.
Но зачем уменьшать квадрат? Время на уменьшение тратится больше, чем на перебор всего квадрата. А для того, что б искомая точка точно оказалась в квадрате достаточно после находжения хоть одой точки увеличить delta на sqrt(2). И, да, важно сбросить индекс с points перед locate В этом варианте скорость поиска увеличивается на 20-40%:
------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Кстати, в математике как раз и принято говорить строго. Цитата:Не определен он там и в помине. Цитата:Простите, а Вы знаете хотя бы, что такое аналитическая функция? |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
X Y 1 1 2 2 4 4 3 3 0 0 X - аргумент, Y значение ф-ии, как думаете известен ли тангенс угла наклона (градиент) для ф-ии проходящей через эти точки и можно ли для нахождения экстремума использовать градиент
Э-э-э, определение не помню, можно посмотреть в инете, но лень Хорошо, переформулирую вопрос: А как будет считаться частная производная для ф-ии заданной в аналитическом виде и чем этот расчет в принципе будет отличаться от заданных дискретов. ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Увы. Тангенс угла наклона - это скаляр, а градиент - вектор. Нельзя путать скаляры и векторы. Два балла. Переэкзаменовка осенью. |
Re: Поиск ближайшей точки | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
Это справедливо В приведенном примере это роли не играет, тангенс угла наклона умноженный на единичный вектор даст градиент. Ладно, спасибо за реплики, до осени ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Вообще градиент определяется для функций от двух и более переменных. И метод градиентного спуска именно для таких используется. И шаг там делается не вдоль координатных линий (это метод покоординатного спуска), а под углом, который определяется градиентом. Если функция определена на сетке, то шагая под произвольным углом в узел сетки фиг попадешь. На сетке другие методы используют. А вот для поиска минимума функции, заданной на произвольном дискретном множестве (как в нашем случае), думаю, кроме полного перебора, вообще никакой теории не существует. Хоть это вовсе не означает, что в каждом конкретном случае нельзя найти что-нибудь получше.
|
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Квадрат уменьшать не обязательно, но в зависимости от таблицы это может дать большой выигрыш. Другое дело КАК его уменьшать - мне было лень изобретать какой-нить "метод половинного деления" или ещё чего для обратного уменьшения - а вот коэффициент подобрать - это да, это имеет смысл - 0.7 слишком плохой, всего на 1 шаг его хватит, 0.8 и то лучше...
Зачем это вообще нужно - формально для уменьшения пространства "перебираемых" точек. Более "человеческим" языком - на примере. Предположим, что ближайшая точка от искомой расположена в квадрате с "полу-шириной" 1025 единиц - более того, расположена она именно на расстоянии 1025 единиц (т.е. она есть оптимум). Если мы начинали поиск с 1 и "удваивали" дельту, то "найдём" мы её на 12 шаге, в квадрате "полушириной" 2048 единиц. Вполне может оказаться, что в таком большом квадрате будет несколько тысяч точек, тогда как в квадрате размером скажем 1050 (всего-то 3 шага редукции с коэффициентом 0.8) точек будет всего пару штук. Если же отказаться заодно и от 2-х ступенчатого поиска, а сразу перейти к квадрату размером Delta*SQRT(2) что уже составит 2900 точек. Уменьшая размер квадрата поиска, мы тем самым уменьшаем количество точек подвергаемых перебору! Всё это исходит из той особенности, что LOCATE по полностью оптимизируемому условию работает быстрее как отбора по этому условию, так и конечно же последующей проверки "лишних" точек - в случае если под условие попадает не 1-2, а скажем порядка тысячи точек. Конечно же если у нас "идеально равномерное" заполнение поверхности, то это не играет особой роли (если до шага N ничего не было найдено, то маловероятно что на шаге N будет найдено сразу много тысяч точек) - но вот если на поверхности есть "скопления точек" и есть достаточно большие "совершенно пустые" области - тогда этот шаг будет не лишним - в худшем случае он ничего не изменит, зато в "лучшем" он "уполовинит" плотное скопление точек. А цена - всего-то 2-3 очень быстрых поиска (по сути проверки). P.S. Про индекс - точнее про то, что в момент работы процедуры поиска НЕ должно быть никакого активного тега - это совершенно верное уточнение - иначе LOCATE будет уже не таким "мгновенным"... ------------------ WBR, Igor |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Логично.
Экспериментировал с равномерно заполненными полями и поэтому не подумал о возможности "кучкования". Думаю, можно считать задачу решённой. Всем спасибо за идеи и замечания. Игорю отдельное спасибо. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер Исправлено 1 раз(а). Последнее : Goodwin, 04.03.10 11:16 |
Re: Поиск ближайшей точки | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Приведенное решение конечно замечательно. Но, как выяснилось, и близко не лежало рядом с теорией.Когда я говорил о предварительном нахождении областей, содержащих точки, расстояние от которых до заданной точки минимально по сравнению с расстояниями до других точек множества - мысль была оказывается в нужном направлении, это так называемые многоугольники Вороного. С их помощью по теории данная задача - "задача о поиске ближайшего соседа" - решается оптимальным образом. Интересующихся отсылаю к книге "Вычислительная геометрия:введение" Ф.Препарата, М.Шеймос, глава 5
|
© 2000-2024 Fox Club  |