|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko 2:5020/400 12 Jan 2003 23:29:19
To : Vitaly Lugovsky
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Виталий! Вы человек, конечно, грамотный, но уж слишком запальчиво
и безапелляционно отстаиваете сомнительные точки зрения навроде:
> Это не болтовня, это факт. Любой алгоритм в рекуррентной форме
> представляется гораздо лучше, и анализировать (в том числе и
> автоматически)
> его удобнее.
Hу вот Вам с ходу пример алгоритма, который все же удобнее рассматривать
и анализировать именно итеративно:
Вводные данные:
Есть конечное число пунктов (городов) N. Они соединены
сетью однонаправленых дорог. То есть по дороге можно двигаться
только в одну сторону, и если есть прямой путь A->B, то это не
означает, что есть также прямой путь В->А. Между пунктами может быть
несколько дорог, а также могут быть "кольцевые" дороги типа A->A.
Структура дорог задается матрицей NxN, в которой M[i,j] есть
число прямых путей из точки i в точку j.
Задача:
Для заданых пунктов I, J и числа шагов К найти количество
возможных путей из точки I в точку J за К шагов.
Hу как? Прямо просится рекурсивное решение с обходом графа и тп.
Вопрос: Сколько времени эта рекурсивная байда будет работать для N=1000?
А есть простое итеративное решение этой задачи за N*N*K операций.
Как, можно с ходу написать рекурентное соотношение, приводящее
к алгоритму такой вычислительной сложности?
А на topcoder-е народ такую задачу примерно за 40 минут кодирует.
40 минут - это все время -- с момента получения условия до
submit-a работающего безглючного кода.
> Или наоборот. Они же почти тождественны, что то, что другое - одно говно.
А что есть еда?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: коммивояжёр 