Минимальное расстояние между линией и точками

[rinaton]

Есть такой рисунок сцылка
подскажите алгоритм в mapbasic, который бы считал минимальную сумму расстояний от главной прямой, до остальных точек, т.е. ∑(Sn)=>min, пример пять точек это населенные пункты, а прямая - линия газопровода, и нам нужно провести газопровод так, чтобы нам потребовалось наименьшее количество труб

[rinaton]

можно ли применить уравнение регрессии Y=a+b*X в данной задаче?

[Максим Дубинин]

да, это чистый метод наименьших квадратов

[Boris]

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

[rinaton]

мне нужно самому написать программу

[Boris]

не понятно, что мы ищем - кратчайшие расстояния до УЖЕ проложенной трубы газопровода (чем задана? отрезком или полилинией?) или расположение еще НЕ проложенной трубы, что бы подводящие были минимальны.
Как учитывается цена главной трубы газопровода? Она отрезок (линия) от ниоткуда в никуда или ее форма и наклон и есть переменные?

[rinaton]

расположение еще НЕ проложенной трубы по уже имеющимся данным объектов, газопровод представляет собой линию из ниоткуда в никуда
гланая для меня сложность - как составить алгоритм в программе?

[gamm]

писать такую программу на Мапвасике по своей воле может только мазохист ... а заставлять писать - садист.

Писать нужно на R, это действительно классический метод наименьших квадратов, параметризация - точка, через которую проходит труба (начальное приближение - среднее имеющихся точек), и угол наклона (начальное приближение - среднее углов наклона регрессии X на Y и регрессии Y на X). Параметры функционала МНК - смещение dX,dY точки и приращение угла dTheta. Для вычисления расстояний просто вращаем все точки по часовой вокруг (X+dX,Y+dY), куда переносим начало системы координат, на угол Theta+dThetа (формулу смотрим в Корне или в интернете), тогда новые координаты Y дают расстояние от трубы.

[Boris]

Не умаляя красоты R, и полностью соглашаясь с извращенностью ума в части использования mapbasic, позволю простейший совет, вернее два:
а) ищем в интеренете код для Visual Basic'а операций с матрицами и аккуратно выписываем строки формул для метода наименьших квадратов. В нем как известно ищут ПАРАМЕТРЫ уравнений, по известным значениям независимых переменных - решение сводится к решению системы линейных уравнений - вот тут и пригодится текст на VB.
б) не будет большим отступлением от заданных условий, но гораздо более человечным, написать часть по решению системы уравнений на обычном байсике или что вам ближе и затем собрать это в DLL-библиотеку, которую уже скормить мапбасику как обычную внешнюю DLL-функцию. Иначе берите текст из VB и переводите его в MapBasic - операторы схожие, но будет много-много мелких различий, которые вынут всю душу. Особенно отладка.

[gamm]

данная задача к системе линейных уравнений не сводится, ИМХО.

[rinaton]

Короче буду просить новое задание, всё же одного семестра изучения mapbasic недостаточно для решения этой задачи

[SergS]

да, это чистый метод наименьших квадратов

точнее, это классический пример линейной регрессии, решаемый методом нименьших квадратов.
именно с этой задачи (приведенной автором темы) начинается изучение регрессионного анализа.
(это к весьма странному замечанию

данная задача к системе линейных уравнений не сводится, ИМХО

)

и чем вам не нравится mapbasic? чем он хуже подходит для реализации алгоритма, состоящего из некоторого набора формул, чем любой другой язык общего назначения?

фраза

Писать нужно на R

напомнила очень смешное выражение, что-то типа:
"я пишу не на паскале, а на delphy"

[gamm]

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

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

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

[SergS]

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

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

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

уместны, уместны....
конечно не дойдет, я ж не подменяю понятие постановки задачи поиском ее решения. Есть задача - найти параметры линии, наилучшим образом моделирующие какой-то набор данных, это есть задача линейной регрессии, а уж как ее решать - другой вопрос.
а вот намеки Ваши здесь действительно неуместны, навскидку вижу парочку способов избавится от различий в "как считаются невязки в регрессии, и как считается расстояние в данной задаче."
одно извращенное (в смысле начальной формулировки), но на мой взгляд красивое решение - подобрать такое аффинное преобразование, естественно методом наименьших квадратов, в котором сумма расстояний (квадратов расстояний) от заданного набора точек (их образов в новом пространстве) до линии Y=0 будет минимальной. Надеюсь, для Вас, как преподавателя, будет несложно отобразить параметры такого преобразования в параметры искомой линии.

да, кстати, я давно, давно, давно уже не студент...

[gamm]

1) Есть задача - найти параметры линии, наилучшим образом моделирующие какой-то набор данных, это есть задача линейной регрессии
2) подобрать такое аффинное преобразование, естественно методом наименьших квадратов, в котором сумма расстояний (квадратов расстояний) от заданного набора точек (их образов в новом пространстве) до линии Y=0 будет минимальной.

1 - просто неверно, но вам об этом просто не рассказали (да и к данной задаче отношения не имеет).
2 - это примерно то, что я написал парой постов выше (рад, что до вас начинает доходить написанное), и к линейной регрессии не сводится. Если немного напряжетесь, то дойдет, что аффинное преобразование не годится (намек - оно меняет метрику).
3 - приближенное решение (про которое я писал) можно найти без МНК, линия задается собственным вектором ковариационной матрицы, соответствующим большему собственному числу (для матрицы 2х2 находится аналитически), и проходит через точку со средними значениями координат. Это преобразование ортогонально, и не меняет метрику