Добрый вечер, товарищи! Не могли бы вы подсказать идею решения следующей задачи?
Дано n точек на плоскости. Нужно построить окружность таким образом, чтобы она охватывала все эти точки, лежащие на плоскости, и чтобы радиус её был минимальным.
И здесь требуется алгоритм, который будет решать эту задачу за линейное время.
Подскажите, пожалуйста, с чего здесь нужно начать. Заранее спасибо!
Построение окружности с минимальным радиусом
Построение окружности с минимальным радиусом
Последний раз редактировалось Shtirlitz 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Очевидно, что на искомой окружности будут лежать какие-то три точки ( или две, если они будут лежать на диаметре окружности). Поэтому можно перебрать все комбинации из трёх точек, для каждой находить центр окружности описанной вокруг треугольника из этих трёх точек, и проверять, лежат ли остальные точки в этой окружности. Ну и, в принципе, это всё можно оптимизировать немного.
Вот такая у меня идея алгоритма, правда не могу сказать будет ли он решать задачу за линейное время, но мб это вам чем-то поможет=)
Вот такая у меня идея алгоритма, правда не могу сказать будет ли он решать задачу за линейное время, но мб это вам чем-то поможет=)
Последний раз редактировалось MrDindows 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Если для 1 точки взять расстояние до нее это будет 0 и записать в матрицу, для второй аналогично и.т.д. Следовательно на диаганали матрицы будут стоять нули. В остальном матрица симметрическая, поэтому все расстояния определять не надо. Поэтому исходные данные можно представить в виде треугольном матрицы с n(n-1)/2 элементами. Поэтому задача заключается в поиске максимального из (n-1)/2 элементов. Например дихотомический алгоритм поиска даст -это уже алгоритм линейной трудоемкости.
Последний раз редактировалось vicvolf 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
vicvolf писал(а):Source of the post
Надо найти 2 точки, лежащие на максимальном расстоянии и соединить их-это будет диаметр искомой окружности.
Треугольник со сторонами 4,3,3
Последний раз редактировалось mihailm 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
mihailm писал(а):Source of the postvicvolf писал(а):Source of the post
Надо найти 2 точки, лежащие на максимальном расстоянии и соединить их-это будет диаметр искомой окружности.
Треугольник со сторонами 4,3,3
Да максимальное расстояние не проходит.
Последний раз редактировалось vicvolf 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Это известная задача о нахождении наименьшей охватывающей окружности. тут вроде описан линейный алгоритм. На русском есть описание алгоритма тут, но он не линейный
Последний раз редактировалось OpenGL 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Спасибо всем большое за помощь! Попробую разобраться.
а какая трудоёмкость будет у этого алгоритма тогда?
На русском есть описание алгоритма тут, но он не линейный
а какая трудоёмкость будет у этого алгоритма тогда?
Последний раз редактировалось Shtirlitz 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Больше, чем у линейного!
Последний раз редактировалось vicvolf 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Shtirlitz писал(а):Source of the post
Добрый вечер, товарищи! Не могли бы вы подсказать идею решения следующей задачи?
Дано n точек на плоскости. Нужно построить окружность таким образом, чтобы она охватывала все эти точки, лежащие на плоскости, и чтобы радиус её был минимальным.
И здесь требуется алгоритм, который будет решать эту задачу за линейное время.
Подскажите, пожалуйста, с чего здесь нужно начать. Заранее спасибо!
Сам алгоритм я к сожалению точно не помню, но могу сказать про него, что:
1. он рандомизированный
2. его оценка доказывается по индукции
3. суть его в том, что в каждый момент есть какие-то выбранные (что-то не более 3х) точки и некоторая окружность, алгоритм пытается достроить конструкцию и в некотором случае начинает всё почти заново
Сейчас попробую загуглить его, но вообще считается, что он вполне придумываем
А вот и весь алгоритм:
Алгоритм рекурсивный, за аргументы он берет два множества точек S и Q. Он считает минимальную окружность для S и Q, считая, что каждая точка Q лежит на границе возможной минимальной окружности. Так, сама задача решается вызовом алгоритма с S=исходным точкам, а Q — пустому множеству. Т.к. алгоритм вызывает себя рекурсивно, он будет увеличивать Q пока он не будет содержать все граничные точки окружноти.
Алгоритм обрабатывает точки S в случайном порядке, поддерживая множество P обработанных точек и минимальную окружность, охватывающую P и Q. На каждом шаге алгоритм проверяет, входит ли очередная точка r в окружность, если нет, то алгоритм заменяет текущую окружность на результат алгоритма со множествами P и Q+r. Независимо от того, изменилась окружность или нет, r включается во множество P. Обработка каждой точки, таким образом, состоит из проверки за константное время, лежит ли точка в окружности, и возможно ещё один рекурсивный вызов алгоритма. Можно показать, что i-тая точка имеет вероятность рекурсивного вызова O(1/i), и таким образом время линейно
(Правда мне нерекурсивный вариант рассказывали)
Последний раз редактировалось Equinoxe 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Построение окружности с минимальным радиусом
Если для 1 точки взять расстояние до нее это будет 0 и записать в матрицу, для второй аналогично и.т.д. Следовательно на диаганали матрицы будут стоять нули. В остальном матрица симметрическая, поэтому все расстояния определять не надо. Поэтому исходные данные можно представить в виде треугольном матрицы с n(n-1)/2 элементами. Поэтому задача заключается в поиске максимального из (n-1)/2 элементов. Например дихотомический алгоритм поиска даст -это уже алгоритм линейной трудоемкости.
А не могли бы вы немного пояснить на этом примере, как мы здесь считаем трудоёмкость? Почему логарифм берём?...
Последний раз редактировалось Shtirlitz 28 ноя 2019, 18:38, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Школьная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 9 гостей