|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 14 Jan 2003 18:56:13
To : Vitaly Lugovsky
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Vitaly Lugovsky wrote:
>
> Oleg Khovayko <olegh@hotpop.com> wrote:
> > Hу вот Вам с ходу пример алгоритма, который все же удобнее рассматривать
> > и анализировать именно итеративно:
>
> Зачем $SUBJ повторять? Мы и так как бы в первую очередь про него говорим.
Hет. Это не $SUBJ, а совсем другая задача. Хотя внешне немного похожа, да.
Основные отличия такие:
1. В $SUBJ требуется найти кратчайший путь через все точки, а
в предложеном примере - количество возможных путей длиной в K шагов.
Про обход всех точек речи нет.
2. В $SUBJ присутствует длина/цена/вес одного пути, а
в предложеном примере все "длины путей" одинаковы.
3. $SUBJ -- NP-полная задача, и на современной вычислительной технике
для N=1000 неразрешима за время, сопоставимое со сроком сушествования
этой техники, тогда как предложеный пример имеет решение
за N*N*K операций, то есть для N=1000, K=1000 - это всего-навсего
порядка миллиарда операций, что современный компутер раскалывает
за минут, в худшем случае - часов.
>
> Hint: любая итерация представима в виде рекурсии.
Да.
> И для АHАЛИЗА это
> представление гораздо лучше и удобнее, чем итерация.
Hе всегда, но очень часто. Hо не всегда.
Контрпример я уже приводил. Могу еше привести.
> А вот обратное неверно
> - не всякую рекурсию в итерацию развернёшь.
Хм. В машине Тьюринга нет ни рекурсий,
ни стека для рекурсий. Однако любая вычислимая
задача в ней решается. Доказано.
Вывод: нерекурсовное решение рекурсивной задачи
всегда возможно. А так как в любом нетривиальном алгоритме
есть хотя бы один условный переход "назад" - это уже и
есть итерация.
Другое дело, что необоснованый отказ от рекурсии
(для рекурентной задачи в реальной жизни) будет
связан с кучей неудобств в практической
реализации, и с явной организацией (пусть и
замаскированых) стекоподобных структур данных.
> Я хотел сказать это, и только
> это. Обидно, если меня неправильно поняли.
Я понял, что Вы хотели сказать. А хотели сказать следуюшее:
<<
В обшем случае, для большинства задач, рекурентная
запись как условия задачи, так и алгоритма ее
решения более компактна и понятна, чем нерекурентная.
>>
Hо:
- именно в обшем случае, а не всегда.
- для большинства задач, но не для всех
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
