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

задан 9 Апр '12 12:01

изменен 9 Апр '12 12:40

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
1

Это Задача Штейнера, решается построением дерева Штейнера.

Ответ на комментарий. Т.к. Вы не накладываете на свой многоугольник никаких условий, не требуете, например, чтобы он был выпуклым, то вершины многоугольника - это просто набор произвольных точек, и задачу можно переформулировать так: "Даны n произвольных точек, нужно найти такую точку, чтобы сумма расстояний от нее до этих точек была минимальной". Это и есть задача Штейнера (см. исходную задачу про 3 деревни). Узлы, появляющиеся в процессе построения дерева, - это просто последовательные итерации, искомая точка получается в конце итерационной процедуры - это центральная вершина минимального графа.

Дополнение. Вообще-то эта задача достаточно сложная. Но можно сформулировать другую задачу - очень похожую, но имеющую простое решение - "Даны n произвольных точек, нужно найти такую точку, чтобы сумма КВАДРАТОВ расстояний от нее до этих точек была минимальной". Решение этой задачи - центр тяжести $%(x_c,y_c)$%, где $%x_c=\frac{\sum_{k=1}^{n}x_k}{n}$%, $% y_c=\frac{\sum_{k=1}^{n}y_k}{n}$%.

ссылка

отвечен 9 Апр '12 15:16

изменен 10 Апр '12 0:16

Ну, тогда изучайте литературу по задаче Штейнера - ей серьезно занимались.

(10 Апр '12 12:40) Андрей Юрьевич

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

(10 Апр '12 14:21) elousiren

Конечно, нет. Мало ли где может быть эта новая точка, например, на бесконечности...

(10 Апр '12 15:15) Андрей Юрьевич

А.Ю., видимо, понял вопрос об еще одной точке. Я - нет. что значит "дополнительную производную ...". "по логике Штейнера построить путь" - какой? Для каких исходных точек?

(10 Апр '12 21:46) DocentI

Я понял вопрос так: если построить минимальный граф для n+1 точки, а затем взять любые n из них, то будет ли соответствующий подграф минимальным?

(11 Апр '12 23:56) Андрей Юрьевич

да про минимальную точку действительно не сходится... у треугольника же 1 точка ферма.. вот тут предлагают интересное решение через последовательность http://www.mathforum.ru/forum/read/1/49685/page/2/

(12 Апр '12 12:11) elousiren

О.о но в голову ни как не лезит... как используется эта последовательность... Через вектора кстати, для N-угольникак не получается)) через вектора находится точка равноудаленная от всех вершин.. Про точку я хотел взять любую точку принадлежащую многоугольнику.. и чтоб от нее находить уже решение..

(12 Апр '12 12:13) elousiren

Про последовательность мне тоже понравилось, хотя не читала внимательно. Новая точка получается как точка с барицентрическими координатами, пропорциональными обратным расстояниям от $%r_k$% до вершин. Но почему она должна приближаться к искомой точке - пока непонятно...

Оформляйте, пожалуйста, ссылки по правилам!

(12 Апр '12 13:08) DocentI

= насчет правильного оформления то не знал не читал извините... хотя тут как то не удобно совсем я даже не понимаю по какому принципу тут можно добавить комментарий... ну да ладно... может потом и разберусь.) после...= жаль он не показал на примере то как получается его ответ... если вам знакома эта тема не могли бы попробовать сделать пример? хотя бы с 2 точками...

(12 Апр '12 15:45) elousiren
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
1

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

Запишем искомую величину в координатах, $%S(x,y)=\sum \sqrt{(x-x_i)^2+(y-y_i)^2}$%. Производная по x равна $%S_x'=\sum \frac{x-x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$%. Приравняем ее к 0. Равенство можно переписать в виде $$\sum \frac{x}{\sqrt{(x-x_i)^2+(y-y_i)^2}}=\sum \frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$$.
Вынося в левой части x, получаем равенство $$x=\frac{\sum \frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}{\sum \frac{1}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}.$$ Такое же равенство можно построить для y. Объединяя их в пару (x,y) получим векторную запись равенства (которая и приведена автором метода).

Идея рекуррентного соотношения: в правую часть подставляем k-ое приближение, в левой получаем (k+1)-ое. Я запрограммировала этот процесс для одного 10-угольника и 2 начальных точек, процесс сходится достаточно быстро:

alt text

Красная последовательность началась с точки (0,0), а зеленая - с точки (10, 12)

Вариант расчета для случайных точек. Синим показан центр тяжести (среднее арифметическое вершин). alt text

Если каждой вершине присвоены коэффициенты $%k_i$%, так что минимизируется взвешенная сумма расстояний, то исследуемая функция принимает вид $%S(x,y)=\sum k_i\sqrt{(x-x_i)^2+(y-y_i)^2}$%.
Производная по x равна $%S_x'=\sum k_i\frac{x-x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$%. Равенство производной нулю можно переписать в виде $$\sum k_i\frac{x}{\sqrt{(x-x_i)^2+(y-y_i)^2}}=\sum k_i\frac{x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}$$.
Вынося в левой части x, получаем равенство $$x=\frac{\sum \frac{k_i x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}{\sum \frac{k_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}}.$$

Из этого равенства можно сделать рекуррентное соотношение.

ссылка

отвечен 12 Апр '12 23:54

изменен 15 Апр '12 21:51

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

(13 Апр '12 12:50) Андрей Юрьевич

О.о у меня есть опосения что это не работает... может конечно не оправданные, но все же... если придать коэфициенты веса вершинам... и рассмотреть на примере двух точек... то сойдется ли последовательность в точке с наибольшим коэфициентом(весом)? либо она покажет точку, о которой говорит Адрей Юрьевич(центр тяжести).

(13 Апр '12 16:38) elousiren

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

(14 Апр '12 2:33) Андрей Юрьевич

Я пробовала разные случайные и не очень токи, получается близко. Если и есть серьезное отклонение, его надо строить специально.

(14 Апр '12 15:12) DocentI

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

(15 Апр '12 3:02) Андрей Юрьевич

интересно что за задача?)) не совпадает ли наша Андрей Юрьевич миссия... а может подскажете DocentI)) как можно очевидным образом сюда ввести коэффициенты?

(15 Апр '12 14:55) elousiren
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
0
ссылка

отвечен 9 Апр '12 19:34

изменен 9 Апр '12 20:36

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

=( а тут всего лишь частные элементарные методы...

(10 Апр '12 4:36) elousiren

Скорее всего, задача решается в каждом случае численно, приближенно. Вряд ли здесь могут быть "формулы". Тем более, в задаче с весами (в таком виде она теряет геометрическую интерпретацию!)

(10 Апр '12 8:33) DocentI

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

(10 Апр '12 16:56) elousiren

Тогда и решать надо физически, т.е. экспериментально ;-)) Только причем же тут равновесие? Вы говорите о сумме длин, а не самих векторов!

(10 Апр '12 21:44) DocentI

=) хм... а физически О.о вроде получается..

(11 Апр '12 18:01) elousiren

ну проверить наверника сложно... но для точки фрема,(треугольника) для 2 точек решение получается..) возможно и работает с N количеством точек

(11 Апр '12 18:03) elousiren

Точка Ферма в треугольнике? Проверьте для четырехугольника (точка известна) и правильного многоугольника с четным числом сторон (точка известна).

(13 Апр '12 17:53) Anatoliy

Насчет коэффициентов добавлю в ответ

(15 Апр '12 21:43) DocentI
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,478

задан
9 Апр '12 12:01

показан
2843 раза

обновлен
15 Апр '12 21:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru