точки на плоскости..

Discussion in 'WASM.A&O' started by al_4, Dec 18, 2007.

  1. al_4

    al_4 New Member

    Blog Posts:
    0
    Joined:
    Dec 18, 2007
    Messages:
    9
    даны n - точек на плоскости, надо найти какую-нибудь точку чтобы суммарное расстояние от неё до n точек было минимальным
    в принципе задачу можно упростить до n = 3 или n = 4, но желательно что бы для любого n.
    Не подскажите формулу, алгоритм?
     
  2. crypto

    crypto Active Member

    Blog Posts:
    0
    Joined:
    Dec 13, 2005
    Messages:
    2,533
    al_4
    Хм, это не центр масс системы из N материальных точек случаем?
     
  3. al_4

    al_4 New Member

    Blog Posts:
    0
    Joined:
    Dec 18, 2007
    Messages:
    9
    хм.. честно хз)

    щас определение глянул, вроде нет, не оно)
    хотя щас посмотрю внимательной, может чего полезного найду)
     
  4. t00x

    t00x New Member

    Blog Posts:
    0
    Joined:
    Feb 15, 2007
    Messages:
    1,921
    ... до n-1 точек было минимальным?
     
  5. halyavin

    halyavin New Member

    Blog Posts:
    0
    Joined:
    May 13, 2005
    Messages:
    252
    Location:
    Russia
    Используй алгоритмы минимизации выпуклых функций. Точного выражения этой точки для n>4 вроде как нет.
     
  6. crypto

    crypto Active Member

    Blog Posts:
    0
    Joined:
    Dec 13, 2005
    Messages:
    2,533
  7. maxdiver

    maxdiver Max

    Blog Posts:
    0
    Joined:
    Jul 18, 2006
    Messages:
    308
    Location:
    Саратов
    Кстати да, очень интересная задача. Мне известен только численный метод.
    Кстати, на algolist.ru утверждается, что ответом будет центр масс, что очевидно неверно.
    Например, для точек на прямой: x=0, x=2, x=10. Ответ x0=2 (средняя точка после сортировки), а центр масс даст x0=4.
     
  8. al_4

    al_4 New Member

    Blog Posts:
    0
    Joined:
    Dec 18, 2007
    Messages:
    9
    >Для треугольника - это точка Торричелли:

    спасибо) кстати, три точки могут быть и на одной прямой. )

    >до n-1 точек было минимальным?

    эм.. слегка не понял вопрос)

    >алгоритмы минимизации выпуклых функций
    спс) гляну)

    >на algolist.ru утверждается,
    уу) забыл про него совсем, щас там поглядим.)
    >Мне известен только численный метод.
    Если не затруднит, то расскажите поподробней пожалуйста)


    всем спасибо, куда "копать" понял)
     
  9. t00x

    t00x New Member

    Blog Posts:
    0
    Joined:
    Feb 15, 2007
    Messages:
    1,921
    al_4
    думал надо искать не новую точку, а точку из n данных.
     
  10. RElf

    RElf New Member

    Blog Posts:
    0
    Joined:
    Dec 25, 2004
    Messages:
    159
    см. http://en.wikipedia.org/wiki/Geometric_median
     
  11. maxdiver

    maxdiver Max

    Blog Posts:
    0
    Joined:
    Jul 18, 2006
    Messages:
    308
    Location:
    Саратов
    RElf
    Спасибо, самому что-то не удалось найти эту страницу )
    Жаль только, что подтвердилось, что кроме последовательных приближений алгоритма не найдено, и большой вопрос, существует ли он...