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

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg Khovayko

Date

2003-01-14T17:51:52Z

Area

RU.ALGORITHMS

From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Oleg Khovayko <olegh@hotpop.com> wrote:

> >  Это не болтовня, это факт. Любой алгоритм в рекуррентной форме
> > представляется гораздо лучше, и анализировать (в том числе и
> > автоматически)
> > его удобнее.
> 
> Ну вот Вам с ходу пример алгоритма, который все же удобнее рассматривать
> и анализировать именно итеративно:

 Зачем $SUBJ повторять? Мы и так как бы в первую очередь про него говорим.

> Ну как? Прямо просится рекурсивное решение с обходом графа и тп.
> Вопрос: Сколько времени эта рекурсивная байда будет работать для N=1000?
> 
> А есть простое итеративное решение этой задачи за N*N*K операций.

 Hint: любая итерация представима в виде рекурсии. И для АНАЛИЗА это
представление гораздо лучше и удобнее, чем итерация. А вот обратное неверно
- не всякую рекурсию в итерацию развернёшь. Я хотел сказать это, и только
это. Обидно, если меня неправильно поняли.

--- ifmail v.2.15dev5
 * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)