Re: коммивояжёр

From

Oleg I. Khovayko ()

To

Ilya Rogov

Date

2003-01-10T19:23:54Z

Area

RU.ALGORITHMS

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

Ilya Rogov wrote:
>    Кто-нибудь слышал о НЕРЕКУРСИВНОМ решении задачи сабжа ? Я подчёркиваю -
> НЕРЕКУРСИВНОМ. Ведь всякую рекурсивный алгоритм можно преобразовать в
> аналогичный итерационный. Или я не прав ?

Конечно, прав.
Простейший нерекурсивный алгоритм для комми-случая - 
генерить все возможные перестановки пунктов, и 
по новой каждый раз считать длину.

А более грамотный нерекурсовный алгоритм, который отсекает
бесперспективные пути методом ветвей и границ, находится тут:

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)