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

О переборе и речи нет. Я привел рекурсивную формулу вычисления точки $r^{(k+1)}$ по точке $r^{(k)}$. Строиться последовательность точек $r^{(0)}, r^{(1)}, r^{(2)}, r^{(3)}, ... , $ которая сходится к искомой точке.

и будет ли иметь тот же смысл если сделать последовательность k(0)r(0),k(1)r(1),k(3)r(2),k(3)r(3),..., где k - вес точки... свободное число, при решении задачи, которое будет известно..

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

Решил проверить формулу, предложенную господином vpro . Проверял, конечно, не вручную, а с помощью проги, написанной в Maple. Вот её текст:

P:=proc(L, eps) # L - список вершин многоугольника, eps - точность
local n, ro, r, k;
n:=nops(L);
ro:=(a,b)->sqrt((a[1]-b[1])^2+(a[2]-b[2])^2);
r[-1]:=<infinity, infinity>;
r[0]:=add(L, i=1..n)/n;
for k while is(ro(r[k-2],r[k-1])>=eps) do
r[k]:=evalf(add(L/ro(r[k-1],L),i=1..n)/add(1/ro(r[k-1],L),i=1..n));
od;
print(k-1,evalf(add(ro(r[k-1],L),i=1..n)),convert(r[k-1],list));
end proc:

Процедура возвращает последовательность из 3 объектов (число итераций, минимальное значение целевой функции, координаты точки, реализующей минимум.
Простой модельный пример (с заранее известным ответом) показывает, что всё работает прекрасно! Вершины треугольника лежат на трёх лучах под углом в 120 градусов, выходящих из точки $(1,\,\frac{1}{\sqrt{3}})$:

P([<0,0>, <1,4>, <3,-1/sqrt(3)>], 10^(-10));
52, 6.88675134594814, [1.00000000015971, 0.577350269258044]

В Maple этот же пример легко можно решить встроенной функцией Optimization[Minimize]:

Optimization[Minimize](sqrt(x^2+y^2)+sqrt((x-1)^2+(y-4)^2)+sqrt((x-3)^2+(y+1/sqrt(3))^2));
[6.88675134594812910, [x = 0.999999999991446, y = 0.577350269192024]]

Как видно, результаты практически идентичны.

Формула, предложенная господином vpro , может и не работать, если многоугольник не будет выпуклым. Вот пример:

P([<0,0>, <2,0>, <0,2>, <2,2>, <1,1>], 10^(-10));
Error, (in P) numeric exception: division by zero

Уважаемый zklb (Дмитрий) ! Если Вам непонятны какие-нибудь коды, это ещё не значит, что они бессмысленные.

Цитата
kitonum
...
Формула, предложенная господином vpro , может и не работать, если многоугольник не будет выпуклым. Вот пример:
...

Конечно может не работать. Но дело здесь не в выпуклости. Во первых, нужно проверять, не попадаем ли мы в одну из заданных точек, чтобы не было деления на 0. Вы как назло придумали именно такой пример, в котором $r^{(0)}=(1,1)$. Эта точка и является ответом. Чтобы избежать этого нужно ввести еще одно условие остановки: ro(r[0],L)<eps.
Во- вторых, я предложил самую простенькую модификацию метода сжимающих отбражений $r^{(k+1)}=\phi(r^{(k)})$. Для того чтобы это работало, как известно, должны выполняться условия на частные производные правой части $\left| \phi'_x \right|<1, $$\left| \phi'_y \right|<1$. Хорошо бы их проверять и при необходимости нормализовать метод.
Но до таких подробностей здесь дело не дошло. TC, судя по всему, учился уже при Фурсенке...



Редактировалось 2 раз(а). Последний 12.04.2012 21:52.

да я не против расчетов (если они нужные) - я против кодов программ, наличие которых на матфоруме бессмысленно. а потом мы с вами немало уже видели "расчетчиков", которые удивляются, что у них компьютер неточно считает.

без математических выкладок на математическом формуме)

Цитата

Kitonum
Понимаете в чем дело, ув. Дмитрий: приведение только результатов расчетов, без самой программы, вот это будет действительно бессмысленным. Это как привести ответ задачи, без выкладок его получения. Принцип верификации в науке рулит.

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