Algoritmo para problema de “Casamiento Estable”

Aunque el problema es conocido como “casamiento estable” (y se soluciona pensando en esta idea), su utilidad es muy amplia y se puede aplicar a una basta gama de problemas actuales. Este problema fue estudiado por primera vez hace ya unos 50 años por Gale y Shapley, con el fin de seleccionar de la manera más óptima y justa a candidatos que postulan a las diferentes universidades. Parece bastante simple la idea, pero veamos un ejemplo que más o menos ilustra las complicaciones del problema: Supongamos que existen n empresas y n candidatos para trabajar (si, nadie quedará sin empleo esta vez), cada empresa necesita tan sólo 1 empleado y vamos a suponer que todos los candidatos postulan a todas las empresas. Seguir leyendo…

Anuncios

¿Cómo trabaja un Algoritmo Genético Simple?

Para hacer una verdadera introducción a los “algoritmos genéticos” probablemente necesitaríamos escribir un libro y no un artículo como este. Intentaremos explicar de dónde viene el nombre algoritmo genético, qué es lo que son, qué +tipos de problemas resuelven, cómo trabajan, qué ventajas y qué desventajas tienen.. Concluiremos con un ejemplo simple de un algoritmo genético (en pseudolenguaje) explicado con lujo de detalles.

¿Por qué Algoritmo Genético?

Un algoritmo genético es básicamente una técnica de búsqueda basada en la teoría de evolución de Darwin. Esta técnica intenta imitar los mecanismos de selección natural, de acuerdo a los cuáles los individuos más aptos de una población son los que sobreviven, pues son capaces de adaptarse más fácilmente a los cambios que se producen en su entorno. En la actualidad se sabe que éstos cambios se efectúan a nivel genético (por esto es el nombre que se le da al algoritmo) y que los atributos más deseables (los que permiten una mejor adaptación en el entorno) son los que se transmiten a los descendientes cuando un individuo se reproduce sexualmente.


Seguir leyendo…

Programa algebraico de Multiplicación Veloz o Algoritmo de Karatsuba

Imaginemos que tenemos 2 números a,b con una cantidad muy grande de dí­gitos. Debido a las limitaciones de nuestro sistema computacional, no es posible multiplicar directamente y obtener el resultado a*b, es decir, un programa simple como
Leer más…