На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Прямая и три точки на плоскости
    Итак, даны прямая и три точки на плоскости. Точки лежат вне прямой.
    Нужно найти на прямой точку сумма расстояний от которой до данных точек минимальна.
    Подходящим ответом будет сведение этой задачи к уравнению степени меньше 5.
    Прямой можно считать ось Х.
    Для двух точек задача решается легко. А для трёх у меня получается уравнение 6-й степени.
    Коэффициенты не расписывал, может там что-то сокращается.
      Нет желания минимизировать вместо этого сумму квадратов расстояний? ;) ;)

      Судя по описанию задачи с двумя степенями свободы по минимизации суммы расстояний, функционал выглядит гладким, и численные методы должны неплохо сходиться.
      Сообщение отредактировано: MBo -
        Как нам в своё время объясняли, минимизация суммы квадратов - это игра в метрике L2, а вот минимизация суммы - игра в метрике L1, что является более естественным для глаза, сколь бы неожиданным это ни казалось. Ну и широко известно, что в гильбертовом то пространстве (L2) всё решается намного легче. :)
          Не понимаю, как на такой фигне можно получить аж шестую степень... речь идёт о тривиальнейшем поиске минимума квадратичной функции...
            Цитата Akina @
            речь идёт о тривиальнейшем поиске минимума квадратичной функции...
            У него сумма не квадратов расстояний, а самих расстояний.
            То есть сумма трёх квадратных корней от квадратичных функций. Избавляясь от корней, он и получает выражение шестой степени.

            MBo, все встречавшиеся мне когда-либо задачи на минимизацию суммы расстояний (в метрике L1) имеют гладкий вид. За исключением заданных точек, где их гладкость нарушается.
            Впрочем, причина тривиальна. Само расстояние от точки - функция, гладкая везде, кроме самой этой точки. А сумма гладких функций является гладкой функцией.
              Цитата amk @
              У него сумма не квадратов расстояний, а самих расстояний.
              То есть сумма трёх квадратных корней от квадратичных функций.

              Упс...

              Цитата amk @
              Избавляясь от корней, он и получает выражение шестой степени.

              Ему нужен минимум функции вида f(x) = SUM(SQRT(x+a)*SQRT(x+b)) - аналитически это получится вроде как 5 степень.
                Цитата MBo @
                численные методы должны неплохо сходиться.

                Численными методами я результат нахожу. Но появился спортивный интерес, ведь для похожей задачи ( без требования, чтобы точка лежала на прямой ) есть геометрические решения для трёх и четырёх точек.
                  Цитата prografix @
                  А для трёх у меня получается уравнение 6-й степени.

                  Я ошибся. Уравнение получается 12-й степени.
                    Цитата prografix @
                    Уравнение получается 12-й степени.

                    Этого не может быть! ищи ошибку.
                      Да, у меня тоже 12-ой. Ещё и думал, как это вы до 6-й скостили... :whistle:
                        Цитата prografix @
                        Численными методами я результат нахожу. Но появился спортивный интерес, ведь для похожей задачи ( без требования, чтобы точка лежала на прямой ) есть геометрические решения для трёх и четырёх точек.
                        Причём решения принципиально разные. А для пяти точек такого решения уже нет.

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

                        Добавлено
                        У меня, кстати, тоже к 12 степени всё сводится.
                          Цитата amk @
                          Причём решения принципиально разные. А для пяти точек такого решения уже нет.

                          А где про это почитать можно?
                            Цитата OpenGL @
                            А где про это почитать можно?
                            Где почитать можно не знаю, а насчёт пяти точек - правильнее было сказать, что я просто нигде так и не нашёл упоминания о таком решении, в отличие от 3 точек. Для 4 и 2, решения тривиальны. При этом оба могут быть найдены из условия равновесия сил - есть такой «физический» способ решения - берём лист, в заданных точках сверлим отверстия, пропускаем через них невесомые верёвочки, связываем их над столом, к свободным концам привязываем одинаковые грузы. Если в отверстиях не будет трения, узел окажется над искомой точкой. Для 2, 3 и 4 точек получаем способ нахождения точки, а для 5 ответ получить уже не получается.
                              Цитата OpenGL @
                              А где про это почитать можно?

                              http://www.mccme.ru/free-books/mmmf-lectures/book.31.pdf
                              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                              0 пользователей:


                              Рейтинг@Mail.ru
                              [ Script execution time: 0,0325 ]   [ 15 queries used ]   [ Generated: 29.03.24, 05:55 GMT ]