0votos

Carrera de "¡Baja la escalera!" en JavaScript

por josejuan hace 5 años

La estrategia básica consiste en obtener el camino óptimo de un nodo, conociendo el camino óptimo de sus dos descendientes. Ésto se puede hacer eficientemente de dos formas, memoizando una búsqueda recursiva en el árbol o haciendo "tail recursion" que, imperativamente, puede reducirse a mantener un único registro de caminos óptimos. Ésto supone usar 4mS para el árbol de 100 filas y 340mS para el árbol de 1.000 filas en un ordenador modesto.

Una variante que convierte al popular juguete en una carrera de la que debes calcular las mejores rutas de los corredores.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// esta implementación asume w=1 
 
function minPath(T) { 
    var i, a, b, c, t, j = T.length; 
    var R = T[--j].map(function(k) { return {p: {e: k, n: null}, c: k} });    // lista enlazada y menor coste 
    while(j--) { 
        t = T[j]; 
        for(i = 0; i <= j; i++) { 
            c = t[i];                                             // para cada nodo `c` 
            a = R[i]; b = R[i + 1]; if(a.c > b.c) a = b;                    // elegir entre izq y der 
            R[i] = {p: {e: c, n: a.p}, c: ~~c + ~~a.c};                    // y formar el nuevo óptimo 
    return R[0]; 
 
 
// *** forma de uso *** 
var DATA= <poner aquí el árbol que sea>; 
var time = new Date();  
var p = minPath(DATA); 
console.log((new Date() - time) + 'ms'); 
var c = [], q = p.p; while(q != null) {c.push(q.e); q = q.n;} 
console.log("PATH (" + p.c + "): " + c); 
 
 
 
/*** por ejemplo **** 
 
Usando el javascript de Firefox 24.0 en un Athlon 64 X2 a 2Ghz 
 
** el árbol de 100 ** 
4ms 
PATH (227): 8,6,2,2,3,2,5,9,1,0,6,1,0,8,0,2,1,0,0,1,0,1,5,0,6,3,0,1,0,6,4,5,6,4,1,0,6,2,0,2,5,3,0,0,2,0,3,1,3,0,6,0,1,2,1,1,5,4,3,2,0,1,3,7,0,3,5,1,2,3,0,0,2,3,3,0,1,0,0,4,3,0,1,7,0,2,3,0,0,2,2,0,0,9,0,4,1,0,3,1 
 
** el árbol de 1000 ** 
340ms 
PATH (2045): 4,8,5,2,0,1,6,8,1,2,4,0,2,1,0,6,6,1,0,0,4,0,2,1,1,2,5,6,1,1,0,0,3,2,2,4,2,0,1,0,5,1,1,5,1,1,3,1,2,5,1,3,4,0,0,1,6,9,1,1,4,1,2,1,1,4,1,0,0,0,0,0,2,2,1,3,8,0,1,3,1,0,2,3,4,0,0,1,4,6,6,7,7,2,0,2,2,0,2,3,3,3,0,0,0,4,3,0,1,0,0,4,0,2,5,0,0,1,0,7,0,2,1,2,1,2,6,0,2,6,0,4,6,3,0,0,1,2,0,3,4,2,2,0,6,1,0,1,4,4,3,3,3,1,0,2,2,7,0,2,3,3,6,2,3,1,0,4,2,1,2,2,2,3,1,1,4,3,1,4,2,1,1,3,0,2,3,0,2,2,0,4,1,8,0,1,1,3,0,0,2,7,0,1,0,1,2,6,2,1,2,1,0,7,1,1,3,0,0,1,2,3,4,0,0,4,2,2,2,3,2,0,2,3,2,1,2,1,0,2,2,1,2,0,8,0,2,1,7,1,3,5,1,1,6,5,1,5,3,0,3,1,4,0,2,0,3,3,3,4,0,4,2,2,4,1,2,2,1,1,0,4,0,1,9,0,1,3,0,1,2,0,1,0,4,5,2,0,1,3,0,4,1,4,0,0,0,6,2,0,4,3,0,0,0,1,6,1,4,0,8,0,2,2,0,7,3,1,0,1,1,4,1,1,0,6,3,2,3,2,7,0,0,4,0,7,0,1,0,1,0,1,0,9,0,2,1,5,3,5,1,0,2,3,1,1,2,5,1,1,3,0,4,0,4,2,3,2,1,0,2,0,3,0,4,1,1,1,3,1,0,5,0,4,2,2,2,0,2,1,7,2,4,0,2,0,0,0,3,0,2,3,5,0,5,1,1,1,4,2,4,1,1,7,3,1,2,2,0,2,2,2,0,0,0,1,5,1,6,0,2,0,6,2,0,1,4,3,0,0,1,0,1,1,0,0,0,5,4,4,5,8,5,2,3,1,0,0,5,2,1,2,2,4,0,2,1,5,0,2,7,1,0,2,4,1,0,1,1,0,3,3,2,3,0,5,0,4,6,1,5,4,0,1,0,3,0,0,2,2,5,0,0,0,4,1,2,3,7,1,6,0,2,4,2,1,3,4,0,5,2,2,0,5,4,4,1,5,5,1,0,4,1,2,3,2,1,5,4,0,0,0,6,2,2,0,2,1,6,3,0,7,0,0,0,0,4,1,0,3,1,3,1,5,2,7,0,1,3,0,4,0,0,3,2,3,3,4,1,1,3,3,1,2,2,0,1,1,0,0,9,0,1,0,5,6,1,3,0,4,0,1,2,0,1,1,0,2,1,2,2,1,2,0,4,2,3,1,4,4,1,3,0,0,2,5,0,0,0,3,1,5,1,3,0,9,3,1,2,0,0,3,0,1,2,2,4,4,0,1,4,2,3,1,1,6,1,1,2,4,0,6,1,2,0,0,0,1,1,3,2,2,1,1,0,3,6,4,1,0,1,1,3,0,1,0,7,0,5,0,5,1,3,1,2,1,7,4,3,2,1,0,0,5,0,2,0,4,2,0,1,2,0,4,0,0,0,2,0,2,1,3,8,0,3,2,4,2,0,4,0,0,1,1,2,0,1,0,1,8,1,1,0,2,3,2,2,1,4,5,1,1,1,3,5,2,2,1,1,6,8,3,0,4,3,2,3,0,0,5,0,0,0,5,4,0,2,8,3,4,2,0,1,1,9,0,0,5,0,4,2,0,1,0,0,2,1,6,2,3,4,7,1,1,1,1,8,0,2,2,0,0,4,0,7,1,0,0,2,0,1,4,1,6,0,3,0,3,1,6,1,0,0,0,1,4,2,0,6,1,3,2,1,6,1,0,2,2,1,2,3,3,2,1,4,2,5,4,3,1,0,4,1,0,2,1,5,1,0,0,0,1,0,1,0,2,4,3,3,1,1,4,1,1,0,4,0,3,0,0,2,1,1,2,2,4,3,5,0,1,9,0,0,6,3,0,0,0,2,0,2,5,0,4,0,1,0,2,0,0,3,6,0,2,0,5,3,4,4,1,1,2,0,3,2,5,5,1,1,1,2,3,2,2,1,0,6,2,1,1,5,1,2,1,1,3,2,0,1,0,3,4,0,1,2,1,0,1,0,0,6,1,4,0,2,1,0,0,0,2,1,0,4,1,2,4,2,0,1,0 
 
*/ 
3 comentarios
0votos

Escrito por Pedro-vk hace 5 años

¿Y qué pasaría si buscar "lo más óptimo" le deja sin ver otras opciones?

Es decir imagina que en un lateral de la pirámide (al que solo se accede si vas tirando hacia la derecha) tiene números muy altos (todo 9) en 20 filas, y posteriormente todo 0. ¿Pasaría por ahí?
0votos

Escrito por josejuan hace 5 años

Sí, revisa (virtualmente) todas las posibilidades, supongo que te refieres a árboles como:

var DATA=
[        [5]
,       [5,9]
,      [5,9,9]
,     [5,9,9,9]
,    [5,9,9,9,0]
,   [5,9,9,9,9,0]
,  [5,9,9,9,9,9,0]
, [5,9,9,9,9,9,9,0]
]; 


basta ejecutarlo para ver

PATH (32): 5,9,9,9,0,0,0,0
0votos

Escrito por josejuan hace 5 años

Por cierto, el árbol de 1.000, en un AMD Phenom(tm) II X6 a 2,7Ghz son 49mS.

¿De qué tamaño podrían calcularse en 20 segundos? (por mantener lo de "unos pocos segundos")?

El coste del algoritmo es lineal respecto del número de números en el árbol, es decir, si es completo (empieza con 1 elementos) n^2/2, por lo que, en 49mS ha calculado 500.000 elementos y en 20 segundos serían 2e8 elementos, es decir, un árbol de 20.203 filas.

Resumiendo, sin paralelizar, debería poderse calcular la ruta óptima en un árbol de 20.203 filas.

De todos modos, lo interesante es ver como se puede paralelizar eficientemente el algoritmo para calcularlo usando tantos procesadores como tengamos disponibles.

Aunque probablemente no merezca la pena, porque el árbol, para que interese paralelizarlo (asumir el coste adicional de paralelizar) tendría que ser muy grande.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.