| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Соединить N точек минимальным колличеством прямых

Соединить N точек минимальным колличеством прямых

Ответ
Поиск в этой теме
Непрочитано 12.03.2012, 09:14 #1
Соединить N точек минимальным колличеством прямых
gizmo_zx
 
Проектировщик ЭО,ЭМ, ЭОС
 
Нижний Новгород
Регистрация: 18.07.2007
Сообщений: 256

Бодрого дня.
Помогите с задачкой.
Есть N точек с координатами Xi, Yi.
Есть конечная точка X0,Y0.
Нужно соединить эти точки прямыми. Прямых должно быть минимальное количество.
Прямые либо горизонтальные, либо вертикальные т.е. наклон не наклонные прямые.
Последняя прямая должна доходить до точки X0,Y0.
Нужна идея математической реализации.

Миниатюры
Нажмите на изображение для увеличения
Название: план.jpg
Просмотров: 66
Размер:	38.2 Кб
ID:	76243  

Просмотров: 3266
 
Непрочитано 12.03.2012, 10:22
#2
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


N точек это сколько? (в зависимости от порядка, либо перебирать все варианты, либо использывать "жадный" алгоритм).
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Автор темы   Непрочитано 12.03.2012, 10:35
#3
gizmo_zx

Проектировщик ЭО,ЭМ, ЭОС
 
Регистрация: 18.07.2007
Нижний Новгород
Сообщений: 256
<phrase 1= Отправить сообщение для gizmo_zx с помощью Skype™


N это о 3 до 50.
Нужен пример математики хотя бы в общих чертах
gizmo_zx вне форума  
 
Непрочитано 12.03.2012, 10:51
1 | #4
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Если в общих четрах - тогда неплохо-бы было понять что все таки нужно, у Вас написанно минимальным количество прямых, а на рисунке их 4 (хотя может вполне быть три) - уточняйте условия.
Миниатюры
Нажмите на изображение для увеличения
Название: Снимок.GIF
Просмотров: 65
Размер:	15.4 Кб
ID:	76250  
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Автор темы   Непрочитано 12.03.2012, 10:57
#5
gizmo_zx

Проектировщик ЭО,ЭМ, ЭОС
 
Регистрация: 18.07.2007
Нижний Новгород
Сообщений: 256
<phrase 1= Отправить сообщение для gizmo_zx с помощью Skype™


Все верно... Сам еще не проснулся...
Ваш вариан правильние.
gizmo_zx вне форума  
 
Непрочитано 12.03.2012, 11:26
#6
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Тогда сортируешь все точки 2 раза (по X и по Y) - смотришь где меньше рядов (столбцов) с одинаковыми (с учетом допуска) координатами получилось (через одинарные тоже вертикали-горизонтали проводишь, но они без одной считаються - через нее другую ось пропустишь), ну а потом через все столбцы (ряды) 1 линию пропускаешь (через какую-нибудь одинарную точку - если такая есть - если нет, то без разницы где).
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Автор темы   Непрочитано 12.03.2012, 11:33
#7
gizmo_zx

Проектировщик ЭО,ЭМ, ЭОС
 
Регистрация: 18.07.2007
Нижний Новгород
Сообщений: 256
<phrase 1= Отправить сообщение для gizmo_zx с помощью Skype™


А если более сложный вариант?
Миниатюры
Нажмите на изображение для увеличения
Название: план1.jpg
Просмотров: 56
Размер:	27.6 Кб
ID:	76257  
gizmo_zx вне форума  
 
Непрочитано 12.03.2012, 11:38
#8
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Если по вышеизложенному алгоритму - то красная пойдет вниз - то есть будет тоже 4 линии.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Соединить N точек минимальным колличеством прямых

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск