|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 17 Jan 2003 21:24:04
To : Oleg I. Khovayko
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote:
>> считать за труд. Сам же алгоритм простенький, намного короче его и не
>> записать:
>
> Итак, Вы признали, что применение рекурсии не дает пользы
> дла решения первого примера. И даже написали свое решение,
> которое точь-в-точь воспроизводит приведенный мною алгоритм на ML-e.
Конечно же. Hо он - рекурсивный, без итерации. И если всё же получится
сформулировать спецификацию задачи - то для доказательства алгоритма
придётся мою реализацию взять, а не итеративную - иначе доказательство
превратится в настоящий кошмар.
> Хочу отметить еще такой момент: Сначала я дал описание
> задачи (что бы подумать), а потом с задержкой привел решение.
> Судя по Вашей реакции, вначале Вы не поверили, что матричный
> алгоритм и есть решение задачи, и требовали от меня доказательств
> адекватности приведенного алгоритма поставлений задаче.
Hет. Доказательство мне нужно, чтоб показать, насколько оно неэлементарно
для итерации, тогда как аналогичная рекурсия приводит к достаточно простым
выводам.
> Отсюда вывод: Ваши рекурсивные изыскания в области
> разработки алгоритма явно лежали в стороне от правильного
> решения. Следовательно, знание рекурсии во всех ее проявлениях
> не сильно помогло Вам самому разработать правильный алгоритм
> для решения этой задачи.
Правильный алгоритм был известен изначально. Речь шла о формально анализе
этого алгоритма, и о той форме, в которой он должен быть записан для
облегчения этого анализа.
> И где-то сутки Вам потребовались,
> чтобы убедиться в адекватности приведенного мною матричного
> алгоритма поставленой задаче.
Hет. Я вообще дальше формулировки не продвинулся - не смог спецификацию
написать, дабы было, что доказывать.
> Hапоминаю: на topcoder-e люди, не зацикленые исключительно
> на рекурсии, такой алгоритм разрабатывают и кодируют примерно
> за 40 минут.
Меня не интересует, сколько там времени на разработку и кодирование уходит.
Мне важен результат - СТРОГОЕ доказательство того факта, что данная
формулировка данного алгоритма в точности соответствует данной постановке
задачи и является её решением при заданных условиях.
> То есть человек получил описание задачи
> (не способа ее решения, а именно описание задачи) - и через
> 40 минут засабмитил безглючный код, решающий эту задачу.
Что значит "безглючный"? "Работает, и хрен с ним"? Или всё же безглючность
формально обоснована?
> 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Е итерационное.
Потому как dowhile есть функция:
let rec dowhile f k x =
if k > 0 then dowhile f (k-1) (f x)
else x
И из этой формулировки уже моментально выводятся констрейны для k,
ограничения на вид функции f и на параметр x. Как это в итерации сделать,
устраивая разборки с промежуточными переменными - я представляю, конечно же,
но ни за что не возьмусь за подобное доказательство.
> Мое итерационное решение:
>
> queue<Node*> q;
>
> q.put(&root);
>
> while(!q.empty()) {
> Node *cur = q.get();
> do_something(cur); // Processing current node
> q.put(cur->left); q.put(cur->right);
> }
>
>
> Ваше рекурсивное решение:
>
> let rec tfindl f nl =
> let rec nxtlyr = function
> hd :: tl ->
> (match hd with
> Tnode(v,l,r) -> if f v than raise (Found(v)) else
> l::r::(nxtlyr tl) | Tnone -> nxtlyr tl
> )
> | [] -> []
> in tfindl f (nxtlyr nl)
>
>
> --------
>
> Теперь пусть обшество сравнит приведенные примеры,
> и выскажет свое мнение в пользу читабельности, понятности,
> компактности, эффективности и возможности анализа того или
> иного алгоритма и приведенной в примерах его реализации.
Hа тему компактности - не честно. Функции всё же разные.
Потому как
1) проверка наличия ветки дерева у меня в do_something не запрятана, а
явно прописана
2) do_something - нечто грязное, с сайд-эффектами, а у меня f - функция,
возвращающая true, если искомый элемент найден, после чего исполнение
завершается.
Для сравнения компактности прошу привести итеративный вариант к тому же
поведению.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
