|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
30.11.2015, 19:14 | #1 |
Новичок
Джуниор
Регистрация: 30.11.2015
Сообщений: 2
|
Построение максимального пути по заданным точкам
Построение пути по точкам я написал и возникли проблемы при поиске максимального пути от точки к точке(с проходом через каждую точка 1н раз). Может быть у кого-то есть подобный алгоритм ? или что посоветуете ?
Заранее спасибо |
01.12.2015, 18:07 | #2 |
Дружите с Linq ;)
Форумчанин
Регистрация: 15.10.2008
Сообщений: 822
|
Что значит от точки к точке? Это граф? Или просто надо рассчитать расстояние между двумя точками? Что у тебя будет на входе в функцию?
Не давай организму поблажки, каждый день тренируй его в шашки..
|
01.12.2015, 22:18 | #3 | |
Новичок
Джуниор
Регистрация: 30.11.2015
Сообщений: 2
|
Цитата:
Прикрепляю проект. |
|
01.12.2015, 23:14 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Вообще то задача коммивояжера, только почему то самый не оптимальный путь ищется. Обычно наоборот. Почему?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 01.12.2015 в 23:17. |
02.12.2015, 22:15 | #5 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Если вы о
1. даны n точек на плоскости с координатами (x,y) 2. построить многоугольник с максимальным периметром То эта задача решается полным перебором. Или неточно, но быстрее таким алгоритмом (находил в сети, и сейчас привожу по памяти) 1. из n точек находится максимальная выпуклая поверхность (известный алгоритм) 2. перебор по всем отрезкам поверхности на тему: - для очередного отрезка перебираются неиспользованные точки - нужная точка обладает свойствами, что 1) если отрезок стереть и добавить два новых на основе этих 3-х точек, то все незадействованные точки окажутся внутри новой поверхности, 2) увеличение периметра максимально для исходного отрезка 3. Выполнять п2, пока не закончатся незадействованные точки. Кажется так. |
02.12.2015, 22:23 | #6 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Идиотская идея за 4 секунды -
А что если граф строить? Взять Форда, например (может и Дейкстра сойдет) - но брать максимум.. Зйадет? |
02.12.2015, 22:34 | #7 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Уже не могу вспомнить причину, но когда на форуме был неправильно сформулированный вопрос о диаметре графа (спрашивали о максимальном расстоянии в графе), то я приходил к выводу о неприменимости Форда и Дейкстры. А позже узнал значение термина "диаметр графа".
Поиск в сети ответа на вопрос о многоугольнике с максимальным периметром, давал полный перебор или приближённые алгоритмы. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Построение графика по заданным точкам Delphi | anthonyk | Помощь студентам | 7 | 26.12.2012 13:03 |
График по заданным точкам | Dim2 | Общие вопросы по Java, Java SE, Kotlin | 6 | 20.05.2010 12:29 |
Си++ Эллипс по заданным точкам | serg777321 | Помощь студентам | 1 | 25.05.2009 11:58 |
В паскале написать программу которая по заданным точкам рисовала многоугольник. | Anton1997 | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 30.11.2008 19:26 |
ассемблер. Написать функцию, вычисляющую по заданным точкам а,b,c площадь треугольника abс. | qimbo | Помощь студентам | 5 | 05.01.2008 13:54 |