Algoritmo de Lee

El algoritmo de Lee es una posible solución para problemas de enrutamiento en laberintos basada en la búsqueda en anchura . Siempre proporciona una solución óptima, si existe, pero es lento y requiere una cantidad considerable de memoria.

Inicialización

Seleccione el punto de inicio y márquelo con 0.

i  := 0

Expansión de ondas

REPETIR

Marcar con i+1 todos los vecinos sin etiquetar de los puntos marcados con i.

i  := i+1

HASTA QUE ((objetivo alcanzado) o (no se puedan marcar puntos))

Rastreo inverso

diríjase al punto de destino

REPETIR

Ve al siguiente nodo que tenga una calificación más baja que el nodo actual.

agregar este nodo a la ruta

HASTA (se alcanza el punto de partida)

Autorización

Bloquear el paso para futuros cableados

Borrar todas las marcas

Por supuesto, la expansión de la onda solo marca puntos en el área enrutable del chip, no en los bloques o partes ya cableadas, y para minimizar la segmentación, conviene mantenerse en una sola dirección el mayor tiempo posible.

• http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf

• Wolf, Wayne (2002), Diseño VLSI moderno , Prentice Hall, págs.  518 y siguientes, ISBN 0-13-061970-1
• Lee, CY (1961), "Un algoritmo para conexiones de rutas y sus aplicaciones", IRE Transactions on Electronic Computers , EC-10 (3): 346–365 , doi : 10.1109/TEC.1961.5219222 , S2CID 40700386 
• Rubin, F (1974), "El algoritmo de conexión de ruta de Lee", IRE Transactions on Electronic Computers , C-23 (9): 907–914 , doi : 10.1109/TC.1974.224054 , S2CID 32651989 

Remzi Osmanli