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

From

Oleg Khovayko ()

To

Vitaly Lugovsky

Date

2003-01-12T22:29:19Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>


Виталий! Вы человек, конечно, грамотный, но уж слишком запальчиво
и безапелляционно отстаиваете сомнительные точки зрения навроде:

 >  Это не болтовня, это факт. Любой алгоритм в рекуррентной форме
 > представляется гораздо лучше, и анализировать (в том числе и
 > автоматически)
 > его удобнее.


Ну вот Вам с ходу пример алгоритма, который все же удобнее рассматривать
и анализировать именно итеративно:

Вводные данные:
    Есть конечное число пунктов (городов) N. Они соединены
сетью однонаправленых дорог. То есть по дороге можно двигаться
только в одну сторону, и если есть прямой путь A->B, то это не
означает, что есть также прямой путь В->А. Между пунктами может быть
несколько дорог, а также могут быть "кольцевые" дороги типа A->A.
Структура дорог задается матрицей NxN, в которой M[i,j] есть
число прямых путей из точки i в точку j.
Задача:
   Для заданых пунктов I, J и числа шагов К найти количество
возможных путей из точки I в точку J за К шагов.

Ну как? Прямо просится рекурсивное решение с обходом графа и тп.
Вопрос: Сколько времени эта рекурсивная байда будет работать для N=1000?

А есть простое итеративное решение этой задачи за N*N*K операций.

Как, можно с ходу написать рекурентное соотношение, приводящее
к алгоритму такой вычислительной сложности?

А на topcoder-е народ такую задачу примерно за 40 минут кодирует.
40 минут - это все время -- с момента получения условия до
submit-a работающего безглючного кода.


> Или наоборот. Они же почти тождественны, что то, что другое - одно говно.

А что есть еда?

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