|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko 2:5020/400 15 Jan 2003 05:55:46
To : Vitaly Lugovsky
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Vitaly Lugovsky wrote:
>
> Hе годится контрпример - ведь это решение представимо в виде рекурсии.
Пожалуйста, давайте не будем заниматься демагогией и втихаря подменять
тему дискуссии. Ведь дискуссия началась в Вашего утверждения:
<<
Это не болтовня, это факт. Любой алгоритм в рекуррентной форме
представляется гораздо лучше, и анализировать (в том числе и автоматически)
его удобнее.
>>
Иными словами, Вы утверждали, что не существует алгоритмов,
которые удобнее было бы представлять и анализировать в
нерекурентной форме. Теперь же Вы говорите о представимости -
то есть принципиальной возможности представить - невзирая на
"трудозатраты". Про представимость - я и никогда не спорил.
Да, конечно, все представимо. Вопрос - какими силами?
Продолжим на счет моего контрпримера. Да, рекурентно
можно написать алгоритм, но толку то!
Попробуйте проанализировать этот Ваш рекурентный алгоритм,
и доказать его вычислительную сложность.
Я уверяю, что будет существенно больше, чем 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
