|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Jan 2003 22:32:27
To : Victor Antropov
Subject : Re: Кратчайший маршрут
--------------------------------------------------------------------------------
Victor Antropov wrote:
>
> Имеется N населенных пунктов соединенных дорогами,причем между какими-то
> пунктами дорог нет.Требуется обойти все пункты по кратчайшему пути.
Блин!
А я тут 2 часа расписывал нахождение кратчайшего пути в графе, а оказалось,
что нужно решение задачи коммовояжера!!! А это СОВСЕМ другая задача!
Совершенно не имеющая отношения к кратчайшему маршруту!
Хотя бы потому, что:
1. При поиске кратчайшего пути не надо обходить все узлы графа,
тогда как в задаче коммивояжера это обязательное условие.
2. У дорог в задаче коммивояжера есть длины, тогда как длины всех дуг
графа при поиске кратчайшего пути считаются одинаковыми.
А то если считать все дороги одинаковой длины - то все пути,
проходящие через все точки, будут иметь одинаковую длину, (равную количеству
точек без единицы) и кратчайший - любой из них.
Задача классическая, описана в любой книжке по теории сложности.
Мне же лениво учебники пересказывать. Тем более, что один раз я
уже отвечал. Больше неохота сил тратить, причем на классическую
многократно решенную задачку.
Кстати, вот здесь есть решение на PASCALe - правда, не тупой
рекурсией, а методом ветвей и границ:
http://lev13.pisem.net/commi.html
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Кратчайший маршрут