Re: Кратчайший маршрут

From

Oleg I. Khovayko ()

To

Victor Antropov

Date

2003-01-07T21:32:27Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

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)