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

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg Khovayko

Date

2003-01-15T18:36:10Z

Area

RU.ALGORITHMS

.n5080.z2.fidonet.ftn> <b02f2e$lpp$1@ddt.demos.su>
From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Oleg Khovayko <olegh@hotpop.com> wrote:

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

 Именно так.

> Теперь же Вы говорите о представимости -
> то есть принципиальной возможности представить - невзирая на
> "трудозатраты".

 Прошу прощения за то, что был неправильно понят. Конечно же, имелось в виду
УДОБНО ПРЕДСТАВИМО. Более удобно, чем сама итерация.

> Про представимость - я и никогда не спорил.
> Да, конечно, все представимо. Вопрос - какими силами?

 Всегда меньшими, чем те, что требуются для анализа не-функционального
алгоритма.

> Попробуйте проанализировать этот Ваш рекурентный алгоритм,
> и доказать его вычислительную сложность.

 Что понимается под "доказать вычислительную сложность"?
 Вы бы лучше попробовали ДОКАЗАТЬ сам этот алгоритм. Да ещё и в императивной
форме. Вот тогда сразу рекурсии захочется - гарантирую.

> Я уверяю, что будет существенно больше, чем O(N*N*K).

 Да ну? Он же тождественный итерации. Что за чушь?

> А итерационный алгоритм дает именно такое
> решение, и анализ его тривиален.

 Тривиален? Жыду доказательства этого алгоритма. Будет оч-чень интересно!

> И кодируется он в десять
> строчек - в прямом смысле слова.
> 
> Так и быть, привожу решение:
> 
> int NumWays(int I, int J, int K, vector< vector<int> > matrix) {
>   vector<int> V(N);
>   V[I] = 1;
>   while(K--)
>     V *= matrix; // тут векторное произведение вектора на матрицу
>   return V[J];
> }

 Ок. Чуть позже (сегодня-завтра, как время найду) приведу неимперативное 
решение той же вычислительной сложности с полным доказательством. Сравним, 
какое из доказательсв проще.

> Теперь: рекурентное описание с анализом - в студию!

 Я про столь тривиальные задачи, как анализ сложности и не говорил. 
Будем доказывать, что этот алгоритм и есть РЕШЕНИЕ задачи.

> А вот еще один пример:
> Есть дерево. Задача: обойти дерево по слоям.
> Я утверждаю, что существует итеративное решение этой задачи,
> пропорциональное N, то есть каждый узел дерева посещается один раз.
> 
> Рекуррентный алгоритм - в студию!
> А потом я дам итерационный...

 Ok. Следующей мессагой и его выдам.

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