IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> тема Графы
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ограничение на количество точек?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Какое ограничение ? Что имеется ввиду ? Ограничений на точек нету..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Насчет полного перебора можно подробнее.. Как осуществить ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

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

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

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

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

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

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

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

Жду вопросов.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


ээээ

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

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

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

если не сдашь, проси человеческую задачу. сделай честное лицо, и скажи преподу, чтоб имел совесть.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Спасибо..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.11.2020 9:01
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name