 |
|
Модераторы: Poseidon, Snowy, bems, MetalFan |
 
|
|
Задачка на Графы, без пересечения ребер 
| LittleFuntik |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 37 Регистрация: 8.8.2007 Где: Украина, Чернигов Репутация: нет Всего: нет |
Здравствуйте. У меня возникла проблема небольшая, сейчас поясню...
На плоскости есть точки (узлы). Координаты узлов известны. Есть главный узел(источник питания). С этим источником питания надо соединить все узлы так, что бы они не пересекались и что-бы путь был минимальным. Если правильно понял, то нужно найти минимальное остовное дерево, но что бы ребра (или линии) не пересекались между собой. Я в математике так себе, может вы чего посоветуете, а то голова не варит уже... Вот картинка, которую я представляю (3 из многих вариантов соединения):  Пожалуйста, помогите!!! |
|||
|
||||
Дата 23.11.2010, 22:54 (
Загрузка ...
| LittleFuntik |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 37 Регистрация: 8.8.2007 Где: Украина, Чернигов Репутация: нет Всего: нет |
Вроде интересная задачка, а никому не интересно)
|
|||
|
||||
| cat512 |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 438 Регистрация: 20.3.2007 Репутация: 7 Всего: 15 |
А что не получается? Рёбра помечаешь весами, и структура графа передаёшь в алгоритм построения мин. остовных деревьев (на выбор Прима, Крускала, Борувки). На выходе получаешь требуемый результат. При желании, даже можно найти и реализацию этих алгоритмов на Delphi
Это сообщение отредактировал(а) cat512 - 24.11.2010, 18:05 |
|||
|
||||
| LittleFuntik |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 37 Регистрация: 8.8.2007 Где: Украина, Чернигов Репутация: нет Всего: нет |
Ну понимаешь... Ребра пересекаться не должны, вот загвоздка в чем
|
|||
|
||||
| cat512 |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 438 Регистрация: 20.3.2007 Репутация: 7 Всего: 15 |
объясни плиз, что значит не должны пересекаться? |
|||
|
||||
| LittleFuntik |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 37 Регистрация: 8.8.2007 Где: Украина, Чернигов Репутация: нет Всего: нет |
Можно ведь соединить точки так, что бы линии пересекались... Но этот вариант не подойдет)
|
|||
|
||||
| cat512 |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 438 Регистрация: 20.3.2007 Репутация: 7 Всего: 15 |
Смотри теорию плоских графов
|
|||
|
||||
|
|
| Правила форума "Delphi: Общие вопросы" | |
|
|
Запрещается! 1. Публиковать ссылки на вскрытые компоненты 2. Обсуждать взлом компонентов и делиться вскрытыми компонентами
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Delphi: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0616 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |