búsqueda reticular (lattice search)búsqueda reticular (lattice search)
Definición: La búsqueda reticular (lattice search) encuentra un máximo de una función unimodal de una única dimensión de búsqueda (un único factor) en un conjunto finito,
evaluando la función en puntos ubicados segun una secuencia de Fibonacci modificada:
Esta modificación resulta de la mejora obtenida por descarte del punto inferior luego de una evaluación: si el conjunto se halla en [a, b] y f(x) < f(y), el nuevo intervalo es [x+1, b] descartando el punto x del conjunto remanente de búsqueda.
El procedimiento a seguir es el mismo de la búsqueda de Fibonacci, excepto en lo que respecta a la ubicación de los puntos que ya no obedece a la secuencia de Fibonacci sino a la de Fibonacci modificada equivalente a
K_n = F_(n+1) - 1,
reflejando así la mejora que se acumula con el crecimiento de n, ya que se elimina un punto extra luego de cada evaluación. El cociente de ubicación es K_(n-1)/K_n, que también se acerca a la relación áurea con el crecimiento de n. Algunos autores denominan búsqueda de Fibonacci a la búsqueda reticular. La siguiente tabla con 5,10,15 y 20 evaluaciones muestra la diferencia entre ambas. Mirando la columna de 20 evaluaciones, la búsqueda de Fibonacci detecta el máximo entre 10946 en el intervalo de incertidumbre inicial, superada por la reticular pero mejor que la obtenida por relación áurea (entre 9349 puntos).
n 5 10 15 20
===================================
F_n 8 89 987 10946
K_n 12 143 1596 17710
relación 6 76 843 9349
áurea
===================================
La búsqueda reticular encuentra el máximo en la ubicación más precisa posible dentro de un dado intervalo de incertidumbre en una búsqueda con un esfuerzo experimental fijo (digamos 20 evaluaciones). Si el número es K_N, el esfuerzo experimental fué N determinaciones. Si el número en el conjunto no coincide con un número K_N de la secuencia modificada, se corrige agregando puntos mudos al final del conjunto.
Si K_(N-1) < m < K_N, arreglar el conjunto así: {x1, ..., xm, y1, ..., yk}, donde k = K_N - m. Así el (mínimo) número de evaluaciones que garante encontrar el máximo de una función unimodal será N.
19.may.2000
Pulsar tecla de vuelta
Glosario de Carlos von der Becke.