|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 15 Jan 2003 19:36:10
To : Oleg Khovayko
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Oleg Khovayko <olegh@hotpop.com> wrote:
>> Hе годится контрпример - ведь это решение представимо в виде рекурсии.
>
> Пожалуйста, давайте не будем заниматься демагогией и втихаря подменять
> тему дискуссии. Ведь дискуссия началась в Вашего утверждения:
> <<
> Это не болтовня, это факт. Любой алгоритм в рекуррентной форме
> представляется гораздо лучше, и анализировать (в том числе и автоматически)
> его удобнее.
> >>
> Иными словами, Вы утверждали, что не существует алгоритмов,
> которые удобнее было бы представлять и анализировать в
> нерекурентной форме.
Именно так.
> Теперь же Вы говорите о представимости -
> то есть принципиальной возможности представить - невзирая на
> "трудозатраты".
Прошу прощения за то, что был неправильно понят. Конечно же, имелось в виду
УДОБ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];
> }
Ок. Чуть позже (сегодня-завтра, как время найду) приведу неимперативное
решение той же вычислительной сложности с полным доказательством. Сравним,
какое из доказательсв проще.
> Теперь: рекурентное описание с анализом - в студию!
Я про столь тривиальные задачи, как анализ сложности и не говорил.
Будем доказывать, что этот алгоритм и есть РЕШЕHИЕ задачи.
> А вот еще один пример:
> Есть дерево. Задача: обойти дерево по слоям.
> Я утверждаю, что существует итеративное решение этой задачи,
> пропорциональное N, то есть каждый узел дерева посещается один раз.
>
> Рекуррентный алгоритм - в студию!
> А потом я дам итерационный...
Ok. Следующей мессагой и его выдам.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
