Алгоритм нахождения кратчайшего расстояния между объектами

[solandr]

Помогите с алгоритмом расчёта кратчайшего расстояния между точкой и параболой. Объекты (точка и парабола) находятся в двумерной плоскости. Общая задача звучит следующим образом. Требуется под имеющийся в наличии набор экспериментальных данных подобрать аппроксимирующую квадратичную функцию например параболу. При этом при подборе в качестве критерия качества используется минимум потенциальной энергии. То есть при подборе коэффициентов параболы итерационным способом требуется знать кратчайшие расстояния между точками из экспериментального ряда и этой параболой. Заранее благодарю всех откликнувшихся.

[незваный гость]

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

[Vassil]

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

Даны экспериментально наблюдаемые числа координат точек

$$(x_i,y_i) \hspace{5 mm} i=1,...,n $$

Первая под-задача - прибилжение точек "наилучшей" параболой:
Найти $a,b,c $, такие, что если

$$y(x)=a\cdot x^2+b\cdot x+c $$

,
то

$$$$\sum\limits_{i=1}^n \{y(x_i)-y_i\}^2 $$

была бы минимальной.
Это простая задача оптимизации с нелинейной целевой функции (в случае - квадратичной), без каких-то ограничений.
Ее можно решить например в Экселе пользуясь добавочным инструментом (Tool) Solver.
Очень богатый Help можно найти на сайте разработчиков этого инструмента по адрессу
www.solver.com
и в многочисленных публикациях на русском, скажем в очень коротком хорошем практическом руководстве:
И. В Орлова, "Экономико-математические методы и модели.Выполнение расчетов в среде Excel. Практикум", Москва, Финстатинформ, 2000.
После решения первой под-задачи можно перейти к второй под-задачи:

Уже известны не только экспериментально наблюдаемые числа координат точек

$$(x_i,y_i) \hspace{5 mm} i=1,...,n $$

,
но еще и коеффициенты квадратного многочлена параболы
$a,b,c $.
Требуется найти (в один раз все) координаты тех $n$ по своему числу точек из графики параболы, которые соответственно самые близкие к экспериментально наблюдаемым точкам.
Для этого можно еще раз решить другую уже задачу минимизации с квадратичной целевой функцией.
Ищем на этот раз

$$\bar x_i \hspace{5 mm} i=1,...,n $$

(прошу обратить внимение на черточку над $ x_i $),
такие, что

$$\sum\limits_{i=1}^n \{(\bar x_i-x_i)^2+(y(\bar x_i)-y_i)^2\} $$

принимала минимальное значение при ограничениях примерно

$$\bar x_i\leqslant \max{(x_i)\hspace{5 mm} i=1,...,n $$

и

$$\bar x_i\geqslant \min{(x_i)\hspace{5 mm} i=1,...,n $$

Найдя искомые

$$\bar x_i \hspace{5 mm} i=1,...,n $$

и вычисляя при найденных ранее $a,b,c $ еще и

$$\bar y_i=y(\bar x_i ) \hspace{5 mm} i=1,...,n $$

,
то задача окончательно решена.
Остается потенциальный упрек, что так сказать "стреляем гаубицой по белке". Но и задача - решена.

[solandr]

Большое спасибо за ответы!!! Действительно, Vassil, Вы правы. Моя задача более широка - она связана с прогнозированием поведения динамической системы в общем значении этого слова. Задача в полном виде выглядит следующим образом. Имеется экспериментальный ряд данных, полученный при наблюдении за системой. Сначала требуется сделать его аппроксимацию параболой, используя в качестве критерия качества потенциальную энергию. Далее требуется оценить пригодность выборки данных, для которой построена эта аппроксимирующая его парабола, для прогноза. Для этого необходимо оценить сходится ли ряд ошибок аппроксимации к какому-то определённому значению (в смысле не превышает какой-то приемлемый уровень при небольших изменениях коэффициентов аппроксимирующей параболы). В случае если у нас ошибки аппроксимации не имеют нормального распределения (или сильно меняются при небольших изменениях коэффициентов параболы), то мы должны взять другую выборку экспериментальных данных и попробовать повторить тот же самый цикл расчётов для новой выборки данных. В итоге проанализировав множество возможных вариантов экспериментальных выборок и проанализировав ошибки аппроксимации мы должны выбрать такую аппроксимацию (и соответсвенно выборку данных), которая удовлетворяет нашим требования самым экстремальным образом. То есть такая выборка экспериментальных данных и будет пригодна для прогноза состояния динамической системы. Далее мы должны с помощью интегрального метода оценить вероятность продолжения нахождения системы слева или справа от аппроксимирующей параболы. Причём мы должны получить конечные численные характеристики (цель задачи) в виде - вероятность нахождения системы в ближайшее время выше (или слева) от параболы равна например 80%, а соответственно вероятность того, что система будет двигаться в нижнюю часть (или в правую) от этой параболы соответсвенно равна 20%. Так вот мне и хочется получить (найти) алгоритм решения такой задачи. То есть как отыскать ту выборку из экспериментально полученных данных, которая будет пригодна для прогноза состояния динамической системы? Может быть Вы могли бы высказать свои предположения? А возможно Вы знаете где об этом можно было бы почитать? Наверняка это уже кем-то делалось и не хотелось бы тратить время на изобретение велосипеда.

Также если у Вас имеется книжка И. В Орлова, "Экономико-математические методы и модели.Выполнение расчетов в среде Excel. Практикум", Москва, Финстатинформ, 2000. в электронном виде, то буду крайне признателен Вам, если Вы её пришлёте на мой e-mail [e-mail]

[Vassil]

Я готов послать книжку И. В. Орловой (в ней 134 страниц) в адресс Библиотеке Мехмата МГУ, которой купил в Москве за 31 рублей (около 1 доллар США) в книжном магазине "Библио Глобус" на Мясницкой, диагонально (или диаметрально) против магазина Детский мир.
Вместо этого, теперь я в состояние сослать заинтересованных посмотреть то, что на подобной тематике у меня естъ в электронном виде:


http://rapidshare.de/files/18623625/xl-slvr.pdf.html

Это мой материал, который был опубликован как Приложение №1 в учебнике Исследование операций проф. Константина Габровского и др., изданной в третьем переработанном и дополненом издании Университетским издательством "Стопанство" при Университете национального и мирового хозяйства в гор. Софии в 2002-ом году.
К сожалению он на болгарском языке. До сих пор я не успел сделать авторский перевод на русском.
Кроме того, в нем подробно рассматривается только случай линейного программирования.
Независимо от того, думаю что при близости двух славянских языков, быть может это приложение может помочь попробовать и успешно решать оптимизационные задачи в Экселе.
Возвращаясь к моем прежнем ответе в Форуме, дополнительно подумав могу добавить, что и при решении второй оптимизационной под-задаче: о множестве самых близких соответственно точках параболы, два ограничения могут быть конечно пропущены, т.е. можем искать самые близкие точки и слегка вне отрезка по иксов, определяемый экспериментально полученными точками.
Тогда все дело сводиться к решению двух задач с квадратичной целевой функции без ограничениях над неизвестных или искомых.

[master.m]

Также если у Вас имеется книжка И. В Орлова, "Экономико-математические методы и модели.Выполнение расчетов в среде Excel. Практикум", Москва, Финстатинформ, 2000. в электронном виде, то буду крайне признателен Вам, если Вы её пришлёте на мой e-mail

[e-mail]