Diapositiva PPT
2.5.3. Funciones de redispersión.
Estrategias de redispersión (para dispersión cerrada):
- Intervalos constantes mayores que 1:
hi(x) = (h(x) + C*i) mod B; para algún Cɭ
- Ej.: B= 8, C= 3, h(x)= 4, se buscaría en: 4, 7, 2, 5, 0, 2, 6, 1.
- B y C deben ser primos entre sí, para buscar en todas las posiciones.
- No se soluciona el problema, ya que se crean grupos a saltos de C.
- Permutaciones aleatorias:
hi(x) = (h(x) + Di) mod B; para Di= (D1, D2, ...) una permutación de 1, 2, ..., B-1
- La permutación es fijada de antemano.
- Se soluciona el problema para determinadas permutaciones Di.
- Método para obtener una permutación:
- Sea B una potencia de 2. Se toma una constante K, en el intervalo (1, ..., B-1).
- Empezamos con un valor cualquiera D1= Di
- Di+1:= 2*Di
- Si Di+1>B entonces
Resta:= Di+1 - B; Di+1:= Resta ? K; Di = (5, 1, 2, 4, 3, 6, 7, 5, ...)