Построение максимального пути по заданным точкам - C# (си шарп)

andreEN · 30.11.2015, 19:14

Построение пути по точкам я написал и возникли проблемы при поиске максимального пути от точки к точке(с проходом через каждую точка 1н раз). Может быть у кого-то есть подобный алгоритм ? или что посоветуете ?
Заранее спасибо

Скарам · 01.12.2015, 18:07

Что значит от точки к точке? Это граф? Или просто надо рассчитать расстояние между двумя точками? Что у тебя будет на входе в функцию?

andreEN · 01.12.2015, 22:18

Цитата:

Сообщение от Скарам

Что значит от точки к точке? Это граф? Или просто надо рассчитать расстояние между двумя точками? Что у тебя будет на входе в функцию?

По сути нужно рассчитать расстояние между точками и выбрать максимальное.
Прикрепляю проект.

Аватар · 01.12.2015, 23:14

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

FPaul · 02.12.2015, 22:15

Если вы о
1. даны n точек на плоскости с координатами (x,y)
2. построить многоугольник с максимальным периметром

То эта задача решается полным перебором.
Или неточно, но быстрее таким алгоритмом (находил в сети, и сейчас привожу по памяти)
1. из n точек находится максимальная выпуклая поверхность (известный алгоритм)
2. перебор по всем отрезкам поверхности на тему:
- для очередного отрезка перебираются неиспользованные точки
- нужная точка обладает свойствами, что 1) если отрезок стереть и добавить два новых на основе этих 3-х точек, то все незадействованные точки окажутся внутри новой поверхности, 2) увеличение периметра максимально для исходного отрезка
3. Выполнять п2, пока не закончатся незадействованные точки.

Кажется так.

Poma][a · 02.12.2015, 22:23

Идиотская идея за 4 секунды -
А что если граф строить?
Взять Форда, например (может и Дейкстра сойдет) - но брать максимум.. Зйадет?

FPaul · 02.12.2015, 22:34

Уже не могу вспомнить причину, но когда на форуме был неправильно сформулированный вопрос о диаметре графа (спрашивали о максимальном расстоянии в графе), то я приходил к выводу о неприменимости Форда и Дейкстры. А позже узнал значение термина "диаметр графа".

Поиск в сети ответа на вопрос о многоугольнике с максимальным периметром, давал полный перебор или приближённые алгоритмы.

30.11.2015, 19:14	#1
andreEN Новичок Джуниор Регистрация: 30.11.2015 Сообщений: 2	Построение максимального пути по заданным точкам Построение пути по точкам я написал и возникли проблемы при поиске максимального пути от точки к точке(с проходом через каждую точка 1н раз). Может быть у кого-то есть подобный алгоритм ? или что посоветуете ? Заранее спасибо

01.12.2015, 18:07	#2
Скарам Дружите с Linq ;) Форумчанин Регистрация: 15.10.2008 Сообщений: 822	Что значит от точки к точке? Это граф? Или просто надо рассчитать расстояние между двумя точками? Что у тебя будет на входе в функцию? Не давай организму поблажки, каждый день тренируй его в шашки..

01.12.2015, 23:14	#4
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	Вообще то задача коммивояжера, только почему то самый не оптимальный путь ищется. Обычно наоборот. Почему? Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию Последний раз редактировалось Аватар; 01.12.2015 в 23:17.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Построение графика по заданным точкам 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

02.12.2015, 22:15	#5
FPaul Форумчанин Регистрация: 25.01.2015 Сообщений: 472	Если вы о 1. даны n точек на плоскости с координатами (x,y) 2. построить многоугольник с максимальным периметром То эта задача решается полным перебором. Или неточно, но быстрее таким алгоритмом (находил в сети, и сейчас привожу по памяти) 1. из n точек находится максимальная выпуклая поверхность (известный алгоритм) 2. перебор по всем отрезкам поверхности на тему: - для очередного отрезка перебираются неиспользованные точки - нужная точка обладает свойствами, что 1) если отрезок стереть и добавить два новых на основе этих 3-х точек, то все незадействованные точки окажутся внутри новой поверхности, 2) увеличение периметра максимально для исходного отрезка 3. Выполнять п2, пока не закончатся незадействованные точки. Кажется так.

02.12.2015, 22:23	#6
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	Идиотская идея за 4 секунды - А что если граф строить? Взять Форда, например (может и Дейкстра сойдет) - но брать максимум.. Зйадет?

02.12.2015, 22:34	#7
FPaul Форумчанин Регистрация: 25.01.2015 Сообщений: 472	Уже не могу вспомнить причину, но когда на форуме был неправильно сформулированный вопрос о диаметре графа (спрашивали о максимальном расстоянии в графе), то я приходил к выводу о неприменимости Форда и Дейкстры. А позже узнал значение термина "диаметр графа". Поиск в сети ответа на вопрос о многоугольнике с максимальным периметром, давал полный перебор или приближённые алгоритмы.