Diseño automático de sistemas digitalesmétodos heurísticos para la colocación óptima de elementos

Resumen

Se aborda el problema de colocación a nivel abstracto utilizando el árbol de expansión mínima para la unión de un conjunto de puntos y el problema de asignación cuadrática como problema asociado al de colocación aplicándose al caso practico de colocación de componentes en el diseño automático de tarjetas de circuitos impresos. Se presenta una nueva transformación del problema de colocación en asignación cuadrática un algoritmo basado en la aplicación de tecnicas de relajación al intercambio por parejas y una función de evaluación para el problema practico basada en una definición de distancia que incorpora información sobre disponibilidad de pistas y dificultades de trazado de conexiones.