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

From

Vitaly Lugovsky (2:5080/1003)

To

Oleg Khovayko

Date

2003-01-16T18:01:25Z

Area

RU.ALGORITHMS

.n5080.z2.fidonet.ftn> <b02f2e$lpp$1@ddt.demos.su>
From: Vitaly Lugovsky <vsl@ontil.ihep.su>

Oleg Khovayko <olegh@hotpop.com> wrote:

> Так и быть, привожу решение:
> 
> 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];
> }

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

let numways n i j k m =
  let v0 = Array.make n 0 in v0.(i) <- 1;
  let v = dowhile (fun x -> vm_mul x m) k v0 in
  v.(j)

> А вот еще один пример:
> Есть дерево. Задача: обойти дерево по слоям.
> Я утверждаю, что существует итеративное решение этой задачи,
> пропорциональное N, то есть каждый узел дерева посещается один раз.
> 
> Рекуррентный алгоритм - в студию!
> А потом я дам итерационный...

 Вот, типа, самый тупой и примитивный вариант:

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)
      )
   | [] -> []
  in tfindl f (nxtlyr nl)

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

 Естественно, каждый узел дерева тут посещается лишь один раз.
--- ifmail v.2.15dev5
 * Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)