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

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

Соеденить n точек полилинией заданной длины

Ответ
Поиск в этой теме
Непрочитано 02.03.2012, 11:58 #1
Соеденить n точек полилинией заданной длины
Mozgunov
 
Начинающий проектировщик
 
Санкт-Петербург
Регистрация: 07.02.2008
Сообщений: 443

Добрый день! Прошу поделиться идеями по решению следующей задачи (желательно на Autolisp). Или хотя бы алгоритм. Спасибо заранее!

Условия:
1-имеется n точек (3-50)
2-имеется заданная длина полилинии которая должна соединить все n точек

Задача:
Требуется соединить точки таким образом, чтобы длина построенной полилинии была максимально приближена к заданной длине при этом чтобы она обязательно проходила через все точки.
P.S. Полилиния не должна проходить через каждую точку больше одного раза.

Последний раз редактировалось Mozgunov, 02.03.2012 в 14:05.
Просмотров: 3583
 
Непрочитано 02.03.2012, 15:32
#2
Дима_

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


Ищи по фразе "задача комивояжора", все отличие с Вашей задачей - у Вас заданый путь (спидометр подгоняете?), а там кротчайший.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Автор темы   Непрочитано 02.03.2012, 15:41
#3
Mozgunov

Начинающий проектировщик
 
Регистрация: 07.02.2008
Санкт-Петербург
Сообщений: 443
<phrase 1=


Да Дима_ вы в точку. Подгоняем спидометр) Спасибо! Буду искать. Вот как раз с отличием я думаю будут большие проблемы)
Mozgunov вне форума  
 
Непрочитано 02.03.2012, 20:53
#4
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


В задаче про комивояжера ищется минимальная длина, а это извращение какое-то
[IMG]http://img233.**********.us/img233/5277/tsp2xd1.jpg[/IMG]
gomer вне форума  
 
Автор темы   Непрочитано 02.03.2012, 21:05
#5
Mozgunov

Начинающий проектировщик
 
Регистрация: 07.02.2008
Санкт-Петербург
Сообщений: 443
<phrase 1=


gomer, Может и извращение, но у него есть смысл. Когда-нибудь появится алгоритм решения этой задачи.
Mozgunov вне форума  
 
Непрочитано 02.03.2012, 22:36
#6
Кулик Алексей aka kpblc
Moderator

LISP, C# (ACAD 200[9,12,13,14])
 
Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,787


Отлично. Есть 4 точки с координатами 0,0,0; 1,1,0; 1,0,0; 0,1,0. Задача - построить путь, длина которого наиболее близка к 3.9. Второй вариант - к 3.5. Третий вариант - к 4.6.
И доказать, что этот вариант единственно возможный.
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Автор темы   Непрочитано 03.03.2012, 11:19
#7
Mozgunov

Начинающий проектировщик
 
Регистрация: 07.02.2008
Санкт-Петербург
Сообщений: 443
<phrase 1=


Кулик Алексей aka kpblc, Если в условия задачи добавить начальную и конечную точку, то эта проблема пропадает?
Mozgunov вне форума  
 
Непрочитано 03.03.2012, 12:45
#8
Кулик Алексей aka kpblc
Moderator

LISP, C# (ACAD 200[9,12,13,14])
 
Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,787


А на этот вопрос надо отвечать не мне
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Автор темы   Непрочитано 03.03.2012, 13:39
#9
Mozgunov

Начинающий проектировщик
 
Регистрация: 07.02.2008
Санкт-Петербург
Сообщений: 443
<phrase 1=


Пропадет. К условию задачи добавляется начальная и конечная точка. Алгоритм решения такой задачи тоже будет неизвестен? Я так понял что простым перебором, даже если будет до 20-ти точек её никогда не решить? Можете ответить можно ли решить такую задачу с поправкой о начальной и конечной точке?
Mozgunov вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Соеденить n точек полилинией заданной длины

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вставка точек по значениям из блакнота, и соединение их линиями (сплайном, полилинией) Redya Программирование 6 15.06.2010 18:47
Нахождение точек пересечения объектов с заданной погрешностью на VBA helpstud Программирование 3 07.05.2009 17:28
Команда _pline и список точек переменной длины Fogel Программирование 8 19.01.2007 14:08
Как строить дугу заданной длины ? ТРУП AutoCAD 31 21.01.2005 14:08
Как создать дугу заданной длины? Елена AutoCAD 7 08.02.2004 23:29