| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Оптимальное расположение линии |
| Автор: Kangaroo 14.10.2008, 17:56 |
| Всем привет! На плоскости находятся точки. Необходимо найти оптимальное расположение горизонтальной линии (на рисунке - красная) так, чтобы суммарная длина перпендикуляров (на рисунке - синии линии) была наименьшей.  Рекомендуют использовать алгоритм поиска двух наиболее близких точек на плоскости (Описан http://en.wikipedia.org/wiki/Closest_pair_of_points_problem, но я пока не придумал куда его прикрутить. Любые идеи, ссылки приветствуются. Спасибо. |
| Автор: Akina 14.10.2008, 18:09 | ||
"Метод наименьших отклонений". |
| Автор: ksnk 14.10.2008, 18:20 |
| Гы... Зачет? Рассмотрим 2 точки. если прямая расположена между ними, то сумма перпендикуляров наименьшая и не изменяется. Можно на досуге подоказывать... Итого решение - делим все точки на 2 равные половины. одна половина лежит выше другой. проводим прямую между половинами. Если количество точек нечетно - выделяем точку прямо "типо по центру" и проводим прямую по ней... |
| Автор: Kangaroo 14.10.2008, 20:24 | ||||||
Гугл нашел только твой пост, может есть другое название?
Ну, если бы все так просто  Это я сам уже придумал. Мне смутила подсказка про "алгоритм поиска двух наиболее близких точек на плоскости".Я, наверное, немного не так написал в первом посте. Мне интересно как можно использовать алгоритм про две точки в этой задаче. В этом основная проблема.
Лабу помогаю сделать. |
| Автор: ksnk 14.10.2008, 20:32 | ||
Пудрют мозги? Либо так, либо условие неполное Вроде по этому условию решение такое и есть... |
| Автор: Kangaroo 14.10.2008, 20:34 | ||||
Ок, попытаюсь ща найти что-нибудь в условии. Спасибо. Добавлено через 45 секунд
Все может быть )) |
| Автор: fryConstantine 15.10.2008, 02:56 | ||
метод наименьшх квадратов |
| Автор: Akina 15.10.2008, 07:48 | ||||
Бред.
Возьми метод наименьших квадратов - конкретно АНАЛИТИЧЕСКОЕ получение выражения для подсчета k и b через соотв. суммирование. Потом проделай ТО ЖЕ САМОЕ, но минимизируя не сумму квадратов, а сумму абсов отклонений от регрессионного уравнения y=k. И получишь аналитическое выражение для расчета этого самого k. Если же тебе достаточно численного решения, без аналитики - Экселевский "поиск решения" щелкает такие задачки как орехи. |
| Автор: ksnk 15.10.2008, 09:11 | ||
? если мы отобразим все множество наших точек на прямую Y и будем решать ту-же задачу для прямой это будет бредом? Пусть для начала, количество точек четно. Разделим точки на 2 равных по количеству множества (Y и Z), все элементы первого лежат не "ниже" всех элементов второго. Возьмем точку, лежащую "не ниже" второго и "не выше" первого. Начнем утверждать , что такая точка (X) и есть решение нашей задачи... Итого - Нужно минимизировать выражение СУММА(abs(Y[]-X))+ СУММА(abs(Z[]-X)) Для этого выберем по одной точке из первого и второго множества, возьмем первую по счету пару и убедимся, что это так... Показывается перебором возможного расположения x y и z. Возьмем вторую, третью и т.д пары Получим, что конструкция abs(Y[n]-X)+abs(Z[n]-X) уже минимизирована. Сложив все такие уже минимизированные конструкции получим, что искомое выражение таки уже минимизировано... В каком месте наблюдается бред? |
| Автор: Akina 15.10.2008, 10:32 | ||
У меня. Просто в другом форуме буквально день назад была та же задача - но с минимизацией суммы квадратов отклонений. Вот и ляпнул не подумав. Приношу извинения. |
| Автор: Kangaroo 15.10.2008, 10:36 | ||
А я уже минут 10 чесал репу над твоим постом  Сделал по алгоритму, который описал ksnk. Тему пока не закрываю, если расскажут как надо было правильно - отпишусь.ksnk, Akina, спасибо. |
