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

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg I. Khovayko

Date

2003-01-14T23:14:22Z

Area

RU.ALGORITHMS

From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote:

>>  Зачем $SUBJ повторять? Мы и так как бы в первую очередь про него говорим.
> 
> Нет. Это не $SUBJ, а совсем другая задача. Хотя внешне немного похожа, да.
> Основные отличия такие:

 Ok, торможу. Больше не буду читать по диагонали...

>> И для АНАЛИЗА это
>> представление гораздо лучше и удобнее, чем итерация. 
> 
> Не всегда, но очень часто. Но не всегда.
> Контрпример я уже приводил. Могу еше привести.

 Не годится контрпример - ведь это решение представимо в виде рекурсии.

>> А вот обратное неверно
>> - не всякую рекурсию в итерацию развернёшь. 
> 
> Хм. В машине Тьюринга нет ни рекурсий, 
> ни стека для рекурсий. Однако любая вычислимая 
> задача в ней решается. Доказано.

 Да. Но - очень неоднозначно. Кроме того, представление о машине Тьюринга
для того же самого анализа крайне неудобно, да и на фиг не нужно -
единственное, что даёт машина Тьюринга, возможность доказательства
конечности аргоритма.

> <<
> В обшем случае, для большинства задач, рекурентная 
> запись как условия задачи, так и алгоритма ее 
> решения более компактна и понятна, чем нерекурентная.
>>>
> 
> Но:
> - именно в обшем случае, а не всегда.
> - для большинства задач, но не для всех

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




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