тема Графы Опции

[Vampire]

Собственно задача: На плоскости заданы n точек своими координатами. Постройте ломаную, имеющую наименьшее число отрезков, проходящую через эти точки, причем через каждую точку ломаная должна проходить лишь один раз.
Загвостка в том, что точки могут быть заданы на одном отрезке, а выводиться должны только концы отрезка..
Не мог бы кто на словах пояснить как здесь нужно действовать..?

[Michael_Rybak]

Ой. Короче я тут подумал... Она, конечно, решаема, но строгое аналитическое решение настолько громоздко, что я не уверен, стоит ли даже пытаться его здесь описывать.

Общая схема такая.

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

Выделим два типа звеньев ломаной - те, которые проходят ровно через одну точку (звенья типа А), и те, которые проходят через 2 и больше (звенья типа В).

Перебираем порядок, в котором точки будут обходиться, вместе с разделением на звенья типа А и В.

Возникает подзадача - для данных двух звеньев типа В проверить, можно ли соединить промежуточные звенья типа А без лишних (не содержащих ни одной точки) звеньев. При этом не нарушая требования - через каждую точку проходит только одно звено.

Вот эту подзадачу можно пытаться решать всякими вероятностными/эвристическими методами, а можно аналитически.

Аналитически - реально сложно. Не смертельно, но на пальцах долго объяснять.

Вероятностно - нужно экспериментировать с реальными данными, ничего не могу сказать; думаю, вполне реально получить очень надежную эвристику, но посидеть придется не один час.

Резюмируя, от всей души советую любой ценой сменить задание, если только это возможно. При этом допускаю некоторый шанс, что я не заметил чего-то очевидного, и она решается относительно просто. Бывает и такое.

Если же поменять не удастся - закатай рукава и готовься много потеть

Жду вопросов.