|
В деревне есть $%3$% дома с координатами $%(0, 0), (1, 0), (0.5 , \frac{\sqrt{3}}{2})$%, в которых живут соответственно $%N, P$% и $%Q$% человек. Где стоит построить колодец, чтобы суммарная длина пути всех людей до колодца была минимальна? Если таких точек много, то выберите ту, у которой максимальная длина пути минимальна. Я бы сам решил, если бы не было дано еще условие о жильцах - это сильно усложняет задачу. задан 28 Янв '14 17:43 
kirill1771
показано 5 из 8
показать еще 3
|
|
Мне предложили метод решения этой задачи через центры масс материальных точек: $$x=\frac{x_1m_1+x_2m_2+x_3m_3}{m_1+m_2+m_3}$$ $$y=\frac{y_1m_1+y_2m_2+y_3m_3}{m_1+m_2+m_3},$$ где $%m_i$% - количество жильцов отвечен 31 Янв '14 16:47
kirill1771 @kirill1771: я отредактировал Ваш текст, убрав оттуда все лишние символы, чтобы он правильно читался редактором. Что касается формул для системы точек с массами, то я думаю, что этот подход не работает. То, что он неприменим в общем случае, не вызывает никаких сомнений, потому что при $%m_1=m_2=m_3=1$% должна получиться точка Торричелли, а не точка пересечения медиан. И даже для случая равностороннего треугольника легко построить контрпример. Скажем, при $%m_2=m_3=1$% и $%m_1 > 2$% колодец должен быть расположен в (0;0), а формулы указывают на нечто другое.
(31 Янв '14 17:49)
falcao
|
@falcao, на составление программы, но я не могу определить, насколько переменные P,N,Q будут влиять на точку
Здесь аналитически вряд ли есть какая-то "красивая" формула. Даже для обычной точки Торричелли, которая легко строится геометрически, выражения для координат не самые простые.
Если это задача по программированию, то должна быть, наверное, задана точность десятичного приближения? Может, тогда её надо решать на "сетке", или при помощи численных методов?
@kirill1771: это один из возможных методов. Всё зависит от того, какая точность десятичного приближения здесь нужна. Допустим, она составляет порядка $%10^{-3}$%. Тогда "сетка" будет иметь порядка $%10^6$% "узлов". Перебрать такое число вариантов для программы -- дело нехитрое. Вид функции, которая при этом минимизируется, довольно простой. Если нужна более высокая точность, то можно сначала получить квадрат со стороной порядка $%10^{-3}$% первым способом, а потом уже его разбивать на более мелкие квадраты.
@falcao,спасибо, я почти разобрался (скоро выложу код программы). У меня только один вопрос остался: как понять "Если таких точек много, то выберите ту, у которой максимальная длина пути минимальна"?
@kirill1771: я не знаю примеров, чтобы в этой задаче точка не была единственной. Правда, я не пытался доказывать соответствующее утверждение. "На вскидку", оно представляется верным. Мне кажется, поскольку априори не известно, единственно ли решение, то авторы сделали эту оговорку просто "для порядка". А мог иметься в виду случай типа N=0, когда точек много.
Ещё одно соображение: если в одной из точек находится слишком много человек (столько, сколько их имеется вместе в двух других точках, или больше), то из неравенства треугольника следует, что колодец именно в этой точке и расположен.
@falcao,спасибо, что отвечаете. А если, например, числа жителей во всех домах равны нулю,то получается, что колодец располагать не надо или, что он может быть расположен в любой точке? Просто я сдавал программу на тестирование и она не сработала только в одном случае (я думаю, что в этом).
Если все числа равны нулю, то колодец по условию должен быть в центре -- чтобы минимизировать максимальную длину пути. Если мы отходим от центра, то от одной из точек оказываемся далеко.
@falcao,мне предложили метод решения этой задачи через центры масс материальных точек (сейчас опишу в ответе)