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

From

Oleg I. Khovayko ()

To

Vitaly Lugovsky

Date

2003-01-14T17:56:13Z

Area

RU.ALGORITHMS

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

Vitaly Lugovsky wrote:
> 
> Oleg Khovayko <olegh@hotpop.com> wrote:

> > Ну вот Вам с ходу пример алгоритма, который все же удобнее рассматривать
> > и анализировать именно итеративно:
> 
>  Зачем $SUBJ повторять? Мы и так как бы в первую очередь про него говорим.

Нет. Это не $SUBJ, а совсем другая задача. Хотя внешне немного похожа, да.
Основные отличия такие:

1. В $SUBJ требуется найти кратчайший путь через все точки, а 
в предложеном примере - количество возможных путей длиной в K шагов.
Про обход всех точек речи нет.
2. В $SUBJ присутствует длина/цена/вес одного пути, а 
в предложеном примере все "длины путей" одинаковы.
3. $SUBJ -- NP-полная задача, и на современной вычислительной технике
для N=1000 неразрешима за время, сопоставимое со сроком сушествования 
этой техники, тогда как предложеный пример имеет решение 
за N*N*K операций, то есть для N=1000, K=1000 - это всего-навсего
порядка миллиарда операций, что современный компутер раскалывает 
за минут, в худшем случае - часов.

> 
>  Hint: любая итерация представима в виде рекурсии. 

Да.

> И для АНАЛИЗА это
> представление гораздо лучше и удобнее, чем итерация. 

Не всегда, но очень часто. Но не всегда.
Контрпример я уже приводил. Могу еше привести.

> А вот обратное неверно
> - не всякую рекурсию в итерацию развернёшь. 

Хм. В машине Тьюринга нет ни рекурсий, 
ни стека для рекурсий. Однако любая вычислимая 
задача в ней решается. Доказано.
Вывод: нерекурсовное решение рекурсивной задачи
всегда возможно. А так как в любом нетривиальном алгоритме 
есть хотя бы один условный переход "назад" - это уже и 
есть итерация.

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

> Я хотел сказать это, и только
> это. Обидно, если меня неправильно поняли.

Я понял, что Вы хотели сказать. А хотели сказать следуюшее:

<<
В обшем случае, для большинства задач, рекурентная 
запись как условия задачи, так и алгоритма ее 
решения более компактна и понятна, чем нерекурентная.
>>

Но:
 - именно в обшем случае, а не всегда.
 - для большинства задач, но не для всех


-- 
#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)