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

[Vampire]

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

[Michael_Rybak]

Ограничение на количество точек?

[Vampire]

Какое ограничение ? Что имеется ввиду ? Ограничений на точек нету..

[Michael_Rybak]

Если точек порядка 10-20, решать нужно полным перебором, и получится точное решение.

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

Загвостка в том, что точки могут быть заданы на одном отрезке, а выводиться должны только концы отрезка..

А вот этого вопроса вообще не понимаю.

[Vampire]

Насчет полного перебора можно подробнее.. Как осуществить ?

[Michael_Rybak]

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

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

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

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

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

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

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

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

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

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

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

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

[Vampire]

Эм.. Сделал я следующее: ввел список из ~7 точек ( простеньких в последовательности: 1,1, 2,2, 3,3, 5,5, 6,4 ну там и т.д.) и смотрю по трем точкам (начальные: 1,1, 2,2, 3,3): если например средняя принадлежит прямой, на которой расположены остальные две, то тогда отметить ее.. Т.е. просто проверяю какие точки лежат на прямой с другими и помечаю их для НЕ вывода. А потом просто вывожу список не отмеченных точек. Знаю что не правильно в корне и все такое, но это все что я смог придуать... Будем надеятся на недалекость моего препода... Хотя хотел для себя решить таки эту задачу...
Спасибо за помощь.. Хотя если не сдам, придется таки решать как надо..

[Michael_Rybak]

ээээ

боюсь что препод, давший эту задачу, знает, что делает.

концы звеньев ломаной далеко не всегда должны ограничиваться заданными точками.

например, через 9 точек: 00, 01, 02, 10, 11, 12, 20, 21, 22 - можно провести ломаную из четырех звеньев (классическая задача), но для этого придется выходить за пределы квадрата.

если не сдашь, проси человеческую задачу. сделай честное лицо, и скажи преподу, чтоб имел совесть.

[Vampire]

Спасибо..