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

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg I. Khovayko

Date

2003-01-17T20:24:04Z

Area

RU.ALGORITHMS

.n5080.z2.fidonet.ftn> <b02f2e$lpp$1@ddt.demos.su> <3377601035@f1003.n5080.z2.fidonet.ftn> <3E281795.6DBC823D@ncbi.nlm.nih.gov>
From: Vitaly Lugovsky <vsl@ontil.ihep.su>

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

>> считать за труд. Сам же алгоритм простенький, намного короче его и не
>> записать:
> 
> Итак, Вы признали, что применение рекурсии не дает пользы
> дла решения первого примера. И даже написали свое решение,
> которое точь-в-точь воспроизводит приведенный мною алгоритм на ML-e.

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

> Хочу отметить еще такой момент: Сначала я дал описание
> задачи (что бы подумать), а потом с задержкой привел решение.
> Судя по Вашей реакции, вначале Вы не поверили, что матричный
> алгоритм и есть решение задачи, и требовали от меня доказательств
> адекватности приведенного алгоритма поставлений задаче.

 Нет. Доказательство мне нужно, чтоб показать, насколько оно неэлементарно
для итерации, тогда как аналогичная рекурсия приводит к достаточно простым
выводам.

> Отсюда вывод: Ваши рекурсивные изыскания в области
> разработки алгоритма явно лежали в стороне от правильного
> решения. Следовательно, знание рекурсии во всех ее проявлениях
> не сильно помогло Вам самому разработать правильный алгоритм
> для решения этой задачи.

 Правильный алгоритм был известен изначально. Речь шла о формально анализе
этого алгоритма, и о той форме, в которой он должен быть записан для
облегчения этого анализа.

> И где-то сутки Вам потребовались,
> чтобы убедиться в адекватности приведенного мною матричного 
> алгоритма поставленой задаче.

 Нет. Я вообще дальше формулировки не продвинулся - не смог спецификацию
написать, дабы было, что доказывать.

> Напоминаю: на 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];
> }
> 
> Ваше итерационное решение:

 Оно НЕ итерационное.

 Потому как 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)
> 
> 
> --------
> 
> Теперь пусть обшество сравнит приведенные примеры,
> и выскажет свое мнение в пользу читабельности, понятности,
> компактности, эффективности и возможности анализа того или 
> иного алгоритма и приведенной в примерах его реализации.

 На тему компактности - не честно. Функции всё же разные.
 Потому как
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)