Всем привет! Если есть желающие "почесать затылок", вот вам задачка.
Заданы координаты N точек на плоскости. Нужно соединить все эти точки ломаной, так чтобы ее длина была минимальной. Ответом будет список координат заданых точек, в порядке их соединения. Первой может быть любая точка.
ЗЫ Дерзайте!!!Заодно и мне поможите(Вопрос №35472).
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
08-09-2005 10:13
Есть 2 задачи коммивояжера (Travelling Salesman Problem - TSP) - неевклидова и евклидова.
Условием является возврат в точку, из которой стартовал. Это автор не уточнил. Но, наверное, он говорит именно о TSP.
Первая задача связана с матрицей расстояний, когда путь из А в Б не всегда равен пути из Б в А. Задача весьма сложная, начиная уже с n=12. Ею занимались и занимаются лучшие математики мира из-за чрезвычайной важности проблемы.
Для этой задачи наилучший метод пока - метод ветвей и границ (brand-n-bench).
Вторая, более простая определяется исключительно геометрическим положением точек,
где путь из А в Б всегда равен пути из Б в А и равен расстоянию по прямой между точками.
Именно эту задачу, видимо, имеет ввиду автор вопроса.
Лучшие методы - генетические алгоритмы. Для них 50-100 точек - пустяк.
В интернете таких алгоритмов пруд пруди. Только не ленись рыться.
08-09-2005 09:49 | Комментарий к предыдущим ответам
Я хотел сказать очень простую вещь - в классической постановке задачи комивояжера речь идет о некоторой цене за переезд из города в город. Кроме неотрицательности, никаких ограничений на нее нет.
В постановке с реальными расстояниями на плоскости появляются дополнительные ограничения: правило треугольника и т.д., что дает шанс построить эффективный алгоритм.
Там "расстояния" между точками произвольны, задача чисто комбинаторная
гы гы гы если из задачи убрать весовые коэффиценты для каждой дороги (в данном случае расстояние) то задача теряет всякий смысл ввиду того что оптимален любой путь, захватывающий каждую точку графа.
Не совсем задача комивояжера. Там "расстояния" между точками произвольны, задача чисто комбинаторная.
А в данной задаче мы знаем, что это вполне обыкновенные расстояния на плоскости т.е. выполняется правило треугольника и т.д. Только на этом и можно играть, что задача комбинаторно-геометрическая. Впрочем в реферате (по первой ссылке) рассмотрен и такой вариант.
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
