Algoritmos Deterministicos

Algoritmos Deterministicos

Cada algoritmo en esta clase construye una solución paso a paso de una forma determinística, ya sea aplicando heurísticas o por medio de una búsqueda exhaustiva

Las buenas soluciones comúnmente se caracteriza porque los resultados intermedios tienen una pequeña cardinalidad. La heurística de selectividad mínima construye un árbol de profundidad por la izquierda paso a paso mientras trata de mantener relaciones intermedias tan pequeñas como sea posible.

Al principio, el conjunto de relaciones a ser unidas se dividen en dos subconjuntos. El conjunto de relaciones ya incorporados en el resultado intermedio denotado como Rusados y el conjunto de relaciones que aun quedan por unir con el resultado intermedio que se denota como Rrestantes. Entonces, en cada paso de el algoritmo la Relación Ri Rrestantes con el menor factor de selectividad.

Los algoritmos probabilísticos han atraído el interés de los investigadores de manera creciente en los últimos 20 años, y actualmente son un tema central de investigación en Ciencias de la Computación, Investigación Operativa, y Matemática Discreta. El poder de la “randomización” para resolver problemas proviene de que un algoritmo probabilístico es una distribución probabilística sobre una clase de algoritmos determinísticos. Para cualquier instancia dada de un problema, algunos de los algoritmos determinísticos en la base del algoritmo probabilístico pueden comportarse pobremente, pero eso puede ser compensado con buenas prestaciones de otros en forma tal que el comportamiento esperado sea bastante bueno.

Otra aplicación quizás inesperada de los algoritmos probabilísticos es en pruebas de teoremas de existencia relativos a propiedades de objetos combinatorios. Esta técnica de prueba es conocida en la literatura como método probabilístico. Las pruebas a través de algoritmos probabilísticos son comunmente mucho más simples que otras pruebas, y en muchos casos son las únicas conocidas.

The source of this article is Wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad