Сергей-4030: Все сообщения за 25 Апреля 2007 года

AidarM> Точно. Могу выложить док-во, оно элементарно, только формулу втыкать не выходит, а ссылку на сайт, с которого картинки загоняются, я забыл.

Это понятно, но к решению не приближает. Что имеем в имплементации: классический рекурсивный алгоритм поиска с откатом. Разницы в порядке вычислений для случая полного перебора (т.е. максимальной площади) и неполного (т.е. первого найденного решения) - нет (в худшем случае, скажем, когда решение только одно). В чем проблема - в том, что основная часть найденных ломаных - самопересекающиеся. Какое решение? Мне кажется, решение будет следующее:

Базис: берем произвольную точку, считаем ее первым звеном нашей цепи (и в этом случае - концом цепи).

Индуктивный переход:
пробуем соединить текущий конец цепи со всеми по порядку "свободными" вершинами. Если вершины исчерпаны - вычисляем площадь, если больше текущего максимума - запоминаем площадь и фигуру. Если нет - следующий шаг рекурсии.

Что может дать решающее увеличение скорости алгоритма? ИМХО, маркировка "доступных" точек. Т.е. делаем так: каждой точке исходно приписывается массив доступных точек, в начале работы алгоритма он состоит их всех остальных точек. Каждый раз, когда вписываем новое ребро, пересчитываем "список доступных" для всех точек на предмет того, что ребро лежит между данной точкой и кандидата в доступные. Если лежит - исключаем кандидата из списка. Преимущества: огромное сокращение числа вариантов. В частности, если после какого-то ребра оказалось, что одна вершина полностью изолирована - поиск по этой ветке можно прекращать. Может быть даже имеет смысл вести поиск на изолированную группу точек (что, конечно, само по себе перестановочная задача).

•  инфо
•  инструменты
• Ответить на сообщение

Сергей-4030>> 2. На основе всех наличествующих точек рисуем сетку из непересекающихся треугольников (разбиение не единственное, но "внешний контур" - единственный, заметьте).
-exec-> после этого уже ничего искать не надо. максимальную площадь даст выпуклый многоугольник, у которого часть первоначальных точек просто проигнорирована (находится внутри периметра).

Задача была не в том, чтобы найти максимальный многоугольник составленный из подмножества точек. Если бы это было так, то решение было бы относительно просто. Задача была - найти многоугольник, составленный из всех точек.

•  1
•  инфо
•  инструменты
• Ответить на сообщение

Сергей-4030> Если бы это было так, то решение было бы относительно просто.

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

•  инфо
•  инструменты
• Ответить на сообщение