El algoritmo FAN es un algoritmo para la generación automática de patrones de prueba (ATPG) . Fue inventado en 1983 por Hideo Fujiwara y Takeshi Shimono en el Departamento de Ingeniería Electrónica de la Universidad de Osaka , Japón. [1] Fue el algoritmo ATPG más rápido en ese momento y posteriormente fue adoptado por la industria. El algoritmo FAN logró reducir la cantidad de retrocesos al adoptar nuevas heurísticas como la sensibilización única y el retroceso múltiple. [1] La sensibilización única consiste en determinar tantos valores de señal como sea posible que se puedan implicar de forma única. El retroceso múltiple es el retroceso simultáneo de más de una ruta, lo que es más eficiente que el retroceso a lo largo de una sola ruta. Para reducir la cantidad de retrocesos, es importante encontrar la inexistencia de la solución lo antes posible. Cuando descubrimos que no existe una solución, debemos retroceder inmediatamente para evitar la búsqueda innecesaria posterior. Estas heurísticas pueden conducir a la detección temprana de inconsistencias y disminuir la cantidad de retrocesos. El algoritmo FAN se ha presentado en varios libros [2] [3] [4] y en muchos artículos de conferencias como ACM/IEEE Design Automation Conference, et al. [5].