Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Минимальное число окружностей по массиву точек |
Автор: BoomeR 13.5.2009, 19:15 | ||||
Привет! Бьюсь, в настоящий момент, над несложной, на первый взгляд, задачкой. Суть :
До чего я дошёл :
Смущает именно "с большой долей уверенности можно считать". Возможно кто-то решал подобную задачу, или просто есть светлые мысли - буду рад услышать совет ![]() |
Автор: maxdiver 13.5.2009, 20:23 |
Ну понятно, это т.н. "жадный" алгоритм, он не всегда даст оптимальный ответ, хотя обычно будет давать близкий к оптимальному ответ. В терминах теории графов это - задача о минимальном доминирующем множестве в двудольном графе (хотя не совсем классическая, у нас только из одной доли мы выбираем вершины), она NP-полная (вроде бы ![]() |
Автор: LOD77 14.5.2009, 15:49 |
Ну я бы не совсем согласился... Задача немного напоминает NP-полные (например задачу о вершинном покрытии графа), но по моему таковой не является. И жадный алгоритм здесь как раз выруливает. Основная разница с классикой в чем? В том что найдя вершину, покрывающую максимальное число ребер мы отбраковываем решения, основанные на вершинах с меньшим покрытием. Лучше в виде матрицы: 1 2 3 4 5 6 1 + + 2 + + 3 + + 4 + + + 5 + 6 + Так вот здесь правильное (минимальное) решение определяется 3-мя вершинами 1,2 и 3 - они полностью закрывают всю строку. Но жадный алгоритм включает в первую очередь 4-ю вершину (у нее покрытие максимальное), а потом добивает строку оставшимися вершинами. Тут возможны решения: 4,5,2,3 или 4,5,2,6 или 4,1,2,3 или 4,1,2,6. В любом случае жадный алгоритм не находит оптимального решения. А в нашем случае (с окружностями) независимо от того, насколько много точек мы включили в текущую окружность, остальные точки не "пострадают". Так что именно жадный алгоритм. Вопрос только начального перебора всех окружностей. Получается N*(N-1)*(N-2) операций, да еще и проверка оставшихся N-3-х точек на принадлежность к окружности. Итого сложность N*(N-1)*(N-2)*(N-3), то есть N в четвертой степени. P.S. Не совсем понятно зачем автору понадобилось сортировать массив. Я бы просто нашел те 3 точки, через которые проходит окружностьвключающая в себя максимальное число точек и затем их вычеркнул из массива точек. Потом повторил бы операцию. |
Автор: maxdiver 14.5.2009, 20:32 | ||
LOD77 Ну и где же доказательство, что "остальные окружности не пострадают"? Вот я не поленился и написал программу, которая генерит рандомный тест и запускает эти два метода. В результате нашёлся хороший тест:
Это квадратик размера 1x1, и оставшиеся три точки на одной прямой. Жадность сначала покроет 4 точки квадратика, а потом с тремя оставшимися точками ей ничего не получится сделать, кроме как ещё две окружности взять. А умное решение возьмёт две совсем другие окружности: (1.5; 1.5) и (1.5; 3.5), первая покроет четыре точки, вторая - три. |
Автор: BoomeR 15.5.2009, 11:09 |
Просто первое решение пришедшее в голову ![]() maxdiver, LOD77, что жадный алгоритм не всегда корректен - это понятно (тут можно сделать поблажку, что на поле 800х800 вероятность попадания 4ой точки на окружность крайне мала и практические все решения оптимальны), но я никак не могу понять : как же реализовать "умный" алгоритм? Искать в NP-полных задачах? Или копать в другую сторону? Дайте наводку ![]() |
Автор: maxdiver 15.5.2009, 18:53 |
BoomeR Если нужен точный алгоритм, то, если задача действительно NP-полна (а этого пока нельзя утверждать точно), то придётся тяжко. Ведь если есть N точек, то возможных расположений окружности будет уже N^3. После этого сюда приходится натравливать переборное решение, которое уже для N=8 работает очень долго. Я для теста написал эвристику - выбирать сто тысяч случайных окружностей и смотреть, что получится; конечно, для практического применения это не прокатит (очень часто даже жадность найдёт более лучшее решение). |
Автор: BoomeR 15.5.2009, 20:16 |
maxdiver, ок, оставлю жадный. Хотя и его производительность оставляет желать лучшего - для 60 точек : вычислений на 11 с мелочью секунд и дальше очень стремительно нарастают. Вопрос считаю закрытым, ура ![]() |
Автор: LOD77 19.5.2009, 15:03 | ||
И тут не совсем согласен. В приведенном примере имеется частный случай: три точки на одной прямой. Теоретически через любые 3 точки можно провести окружность - просто ее центр будет в бесконечности. Поэтому в приведенном примере жадный алгоритм выдаст 2 окружности: одну проходящую ч/з 4 точки (квадрат), другую через 3 оставшихся. Покажите мне реальный пример, когда жадный алгоритм дает неверный результат (только без точек на одной прямой). Я такой пример придумать не смог. |