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

From

Oleg Khovayko ()

To

Vitaly Lugovsky

Date

2003-01-15T04:55:46Z

Area

RU.ALGORITHMS

.n5080.z2.fidonet.ftn>
From: Oleg Khovayko <olegh@hotpop.com>

Vitaly Lugovsky 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, то есть N*N.
Все это выполняется К раз. Итого время выполнения O(N*N*K).
Дополнительной памяти - 2*N ячеек. ВСЕ.

Теперь: рекурентное описание с анализом - в студию!
Сравним понятность/краткость/возможность анализа.

>  Вот я и хотел бы посмотреть на такую задачу, где требуется в явном виде
> сложная итерация, и её нельзя было бы однозначно избавить от мутабельных 
> объектов,  переведя в рекурсию.

Смотрите выше. Попробуйте рекурентно это представить проще.

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

Рекуррентный алгоритм - в студию!
А потом я дам итерационный...

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)