Привет!

Бьюсь, в настоящий момент, над несложной, на первый взгляд, задачкой. Суть :


До чего я дошёл :


Смущает именно "с большой долей уверенности можно считать". Возможно кто-то решал подобную задачу, или просто есть светлые мысли - буду рад услышать совет   

Ну понятно, это т.н. "жадный" алгоритм, он не всегда даст оптимальный ответ, хотя обычно будет давать близкий к оптимальному ответ.

В терминах теории графов это - задача о минимальном доминирующем множестве в двудольном графе (хотя не совсем классическая, у нас только из одной доли мы выбираем вершины), она NP-полная (вроде бы  ну я не 100% уверен, но наша задача не сильно отличается от классической). Хотя здесь не самый общий случай этой задачи (граф всё-таки особого вида), надеяться на быстрое и точное решение не стоит. Тогда решать перебором или динамикой по маскам.

Ну я бы не совсем согласился...
Задача немного напоминает 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 точки, через которые проходит окружностьвключающая в себя максимальное число точек и затем их вычеркнул из массива точек. Потом повторил бы операцию.

LOD77
Ну и где же доказательство, что "остальные окружности не пострадают"?

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

Это квадратик размера 1x1, и оставшиеся три точки на одной прямой. Жадность сначала покроет 4 точки квадратика, а потом с тремя оставшимися точками ей ничего не получится сделать, кроме как ещё две окружности взять.

А умное решение возьмёт две совсем другие окружности: (1.5; 1.5) и (1.5; 3.5), первая покроет четыре точки, вторая - три.

Это сообщение отредактировал(а) maxdiver - 14.5.2009, 20:38

Просто первое решение пришедшее в голову 



maxdiver, LOD77, 

что жадный алгоритм не всегда корректен - это понятно (тут можно сделать поблажку, что на поле 800х800 вероятность попадания 4ой точки на окружность крайне мала и практические все решения оптимальны), но я никак не могу понять : как же реализовать "умный" алгоритм? Искать в NP-полных задачах? Или копать в другую сторону? Дайте наводку 

BoomeR
Если нужен точный алгоритм, то, если задача действительно NP-полна (а этого пока нельзя утверждать точно), то придётся тяжко. Ведь если есть N точек, то возможных расположений окружности будет уже N^3. После этого сюда приходится натравливать переборное решение, которое уже для N=8 работает очень долго.

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

maxdiver, 
ок, оставлю жадный. Хотя и его производительность оставляет желать лучшего - для 60 точек : вычислений на 11 с мелочью секунд и дальше очень стремительно нарастают.

Вопрос считаю закрытым, ура 

  И тут не совсем согласен. В приведенном примере имеется частный случай: три точки на одной прямой. Теоретически через любые 3 точки можно провести окружность - просто ее центр будет в бесконечности. Поэтому в приведенном примере жадный алгоритм выдаст 2 окружности: одну проходящую ч/з 4 точки (квадрат), другую через 3 оставшихся.
Покажите мне реальный пример, когда жадный алгоритм дает неверный результат (только без точек на одной прямой).
Я такой пример придумать не смог.