В продолжение темы об олимпиаде, проведенной Воронежским государственным университетом. Хотелось бы узнать идеи по перовой задаче из предложенных.
Формально: найти эллипс с осями параллельными осям координат минимальной площади, который покрывает все заданные точки. Ограничения: 20 точек, координаты точек по модулю не превосходят 100 и целочисленны. Параметры эллипса (координаты центра и размеры осей) могут быть любыми.
В процессе обдумывания задачи была отброшена идея постепенного построения эллипса по 4ем опорным точкам. Контр-пример: (0 41) (10 40) (-10 -40) (0 -41). Через данные точки можно единственным образом построить эллипс, но он не будет искомым. На момент сдачи решений осталось две идеи: копать в сторону преобразований системы координат, или работать в текущей, отталкиваясь от того, что в границу искомого эллипса обязательно войдут 2 точки. Количество точек позволяет перебрать все пары, не придумал как найти минимальный эллипс, проходящий через 2, и покрывающий остальные.
Мне кажется, нужно идею про охватывающие эллипсы всего-лишь чуть-чуть проапгрейдить. Рассмотрим три типа эллипсов, с осями, параллельными осям координат.
Эллипсы, проходящие через две заданные точки и имеющие минимальную площадь
Эллипсы, проходящие через три заданные точки и имеющие минимальную площадь
Эллипсы, проходящие через четыре заданные точки (и имеющие среди таких минимальную площадь в силу единственности такого эллипса)
Назовём такие эллипсы охватывающими. Я утверждаю, что ответ лежит среди множества всех охватывающих эллипсов. Перебираем все возможные охватывающие эллипсы, проверяем, что он покрыл все точки. Это ясно из каких-то интуитивных математических соображений, что искомый эллипс вот так вот натянут либо на две, либо на три, либо на четыре точки из множества. В частности, в примере ответом является охватывающий эллипс, натянутый на точки (-10 -40) и (10 40).
Как строить охватывающий эллипс для четвёрки, тройки или двойки должно быть более-менее понятно. Надо посидеть с листиком и ручкой и честно вывести формулы. С этим вы, наверное, справитесь (а вот мне, кажется, не хватает теор. базы :-( )
Натянут на 2/3/4, но с чего вы решили, что нам нужен минимальный из натянутых на две (например).
Хотя возникает такое ощущение, что если мы попытаемся завалить эту идею, ну например добавив к двум точкам примера 3юю, то получим минимальный эллипс натянутый на 3. Доказательство конечно требовать нагло, но если есть какие-то соображения, которые можно изложить, не тратя много времени, то был бы благодарен. Похвастаться хорошей интуицией в математике и программировании не могу. Скорее наоборот, сильно не люблю жадные идеи и алгоритмы ((.
Жаль нельзя проверить идею полным перебором.
Кстати построение эллипса по 4ем точкам сведется к решению системы 4ех нелинейных уравнений. Не могу сказать, что это сильно радует.
Прочитал ваш комментарий и так и не понял, согласились вы с моим решением или нет))
Я могу аргументировать следующим образом.
Понятно, что искомый эллипс натянут либо на четыре, либо на три, либо на две точки. Если искомый эллипс натянут на четыре — то мы его найдём. Если на три — зафиксируем две точки A, B и С, на которые он, собственно, натянут.
Основная проблема заключается в том, чтобы понять, что никакой эллипс из натянутых на A, B, C, кроме минимального не может быть кандидатом на попадание в качестве ответа. Рассмотрим множество всех эллипсов, проходящих через данные три точки. Это множество можно параметризовать каким-нибудь одним действительным параметром t. Например, зафиксировав, что отношение длин полуосей равно t, и зная три точки A, B и C, мы можем однозначно восстановить эллипс.
Теперь начинается интуитивный факт. Если обозначить за S(t) площадь эллипса с параметром, равным t, то S(t) имеет один глобальный минимум по всем значениям t. Что это значит? Если у нас есть эллипс, который якобы является минимальным, и который натянут ровно на три точки, давайте обозначим значение его параметра — t0. Давайте "пошевелим" t0 в небольших пределах, так, чтобы не наткнуться эллипсом на какую-нибудь четвёртую точку. Раз мы не нашли значения лучше, то в этой окрестности точка t0 будет соответствовать минимуму функции S. А раз так, то мы находимся в каком-то локальном минимуме функции S. А локальный минимум у S из интуитивного соображения есть только один и он совпадает с глобальным. А глобальный мы в программе проверяем, значит ура, победа.
То же самое, с эллипсами, натянутыми на две точки. Там просто понадобится больше параметров для параметризации — два или три, точно не уверен.
Основная идея на пальцах — если у нас что-то известно про эллипс, например, что он проходит через такие-то точки, то если забить на условие, что он должен содержать все остальные точки, при таких условиях существует единственный локальный минимум площади по всем этим эллипсам и он совпадает с глобальным.
Если хотите аналогию — общеизвестно, как решать задачу о минимальной охватывающей окружности за O(n4). Точно так же перебираем все тройки и двойки точек. Тут вам очевидно, что из всех окружностей, натянутых на две точки, нужно взять ту, которая имеет минимальную площадь, то построенную на отрезке между этими двумя точками как на диаметре? Это объясняется тем, что если это не так, то будем двигать окружность в направлении бла-бла-бла... Здесь рассуждения из той же оперы, "шевеление" параметра t занимается тем же самым.
Да, пожалуй достаточно строгое доказательство. Спасибо вам за развернутый ответ. Почти согласен, но пожалуй окончательно буду осознавать завтра, после рабочего дня хреново соображаю ))
кстати, те, кто минусует первый пост Zlobober`a, может поясните причину? я вроде бы ошибки не вижу.
В такой ситуации можно очень легко поступить.
Я готов поставить тортик, что такое решение пройдёт на ОК. Если кто-то готов со мной спорить, то он пишет комментарий и тогда я через некоторое время пишу это решение. Если желающих не найдётся, то я — Д'Артаньян, а все минусующие — известно кто :-)
Только увидел пост.
Вчера обсуждали двумя чапельниками эту задачу. Утверждение выше ясно и верно. 4 точки очевидно как обработать. Для двух точек полуоси эллипса относятся как соответствующие координаты вектора от первой точки ко второй. Это тоже понятно. Не очень ясно, как решить задачу для трех точек (кроме как злобного численного шаманства).
Кстати, в сообщении выше явные неточности.
По 3 точкам — почему эта функция имеет единственный минимум? Более того, интуитивно это как раз НЕ верно: относительно параметра "отношение x и y полуосей эллипса" эта функция имеет вид произведения трех (a^2/k + b^2 * k).
По 4 точкам — такой эллипс не единственный. Их может быть от 0 (невыпуклое множество) до бесконечного множества (квадрат).
Ну так a и b тоже от параметра k зависят, не так ли?
По четырем точкам — речь идет о четырех точках общего положения, естественно, выпуклая оболочка которых — четырехугольник.
Вот и прекрасно, что такое решение правильное.
Выпуклая оболочка квадрата — четырехугольник. Легко провести через него сколько угодно эллипсов. Все дело в том, что если три точки образуют прямоугольный треугольник в осях, то все эллипсы в осях через эти три точки проходят через четвертую точку (которая достраивает треугольник до прямоугольника).
Параметры a^2 и b^2 — это квадраты координат соединяющих векторов, они связаны соотношениями, но (интуитивно) все равно можно сделать, чтобы целевая функция имела несколько минимумов.
Общего положения, уважаемый, общего положения! Я прекрасно понимаю, когда можно построить одну конику по четырем точкам с осями, параллельными осям координат, а когда — бесконечно много.
А на пример, когда несколько минимумов, я бы посмотрел. Мне моя лично интуиция подсказывает, что такого не бывает. Более того, я не умею докзывать корректность работы алгоритма, не опираясь на этот факт. А вы умеете?
Корректность подхода (интуитивно) следует из принципа условной минимизации — либо безусловный минимум, либо дополнительное ограничение.
Строго можно доказывать, если аккуратно разобрать изменение решения задачи "покрыть окружностью" относительно растяжения/сжатия по одной из координат.
Да, разумеется, проверять надо все локальные минимумы для случая с тремя точками, если их несколько, а не только лучший из них.
Кстати, просветите — а почему не бывает случая, когда можно провести ровно N > 1 эллипса в осях?
======================================== Посмотрими на общее уравнение коники: Ax2 + By2 + Cxy + Dx + Ey + F = 0. Утверждается, что оси коники параллельны осям координат тогда и только тогда, когда C = 0. K точек дают K линейных соотношения на коэффициенты. Система — однородная, поэтому решением является какая-то гиперплоскость через ноль. Количество решений зависит от размерности этой гиперплоскости. Если это точка, то решений нет. Если прямая, то оно одно (с точностью до пропорциональности). Если это плоскость или круче (а в вашем примере с квадратом это плоскость), решений бесконечно много.
Да, я похоже получу на этой задаче "тормоз года" :(
Про случай трех точек: пример с неединственным ответом, похоже, и правда не существует. Производная от ln(a^2*x+b^2/x) ведет себя так предательски, что совершенно не понятно, как складывать функции такого вида, чтобы у суммы было несколько минимумов.
Я вместо такого комментария просто немного исправил сложившуюся ситуацию и нажал вверх, т.е. я бы наверное не нажал, если бы комментарий не был в минусе.
Я, конечно, дико извиняюсь, но мне не понятно, почему для точек из примера эллипс-ответ не проходит через все 4 точки. Хотите сказать, что эллипс-ответ, строящийся на точках (10,40) и (-10,-40) содержит две другие точки внутри себя и при этом не может быть "сужен"?
да, именно. эллипс по четырем точкам близок к кругу. А ответом является минимальный эллипс по двум диагональным. Он сужен
Очевидно имеем следующую задачу условной оптимизации:
множество
задаётся ограничениями:
Здесь x, y -- координаты центра эллипса, a, b -- полуоси. Можно попытаться решить такую задачу численно.