El cola de milano , en el diseño de algoritmos , es una técnica que entrelaza diferentes cálculos y los realiza de manera prácticamente simultánea. Los algoritmos que utilizan cola de milano a veces se denominan cola de milano .
Consideremos un árbol que potencialmente contiene un camino de longitud infinita (pero cada nodo tiene solo un número finito de hijos): si se realiza una búsqueda en profundidad en este entorno, la búsqueda puede recorrer un camino infinito y nunca regresar, lo que podría dejar parte del árbol sin explorar. Sin embargo, si se utiliza una búsqueda en amplitud , la existencia de un camino infinito ya no es un problema: cada nodo se visita de manera ramificada según su distancia desde la raíz, por lo que un camino infinito solo afectará la parte de la búsqueda que recorra ese camino.
Podemos considerar este árbol como análogo a una colección de programas; en este caso, el enfoque de profundidad corresponde a ejecutar un programa a la vez, pasando al siguiente solo cuando el programa actual ha terminado de ejecutarse. En el caso en que uno de los programas se ejecute durante una cantidad infinita de tiempo, esta transición nunca ocurrirá. El enfoque de amplitud de visitar cada hijo en el mismo nivel del árbol es un ejemplo de ensamblado, donde se realiza un solo paso para cada programa antes de pasar al siguiente. Por lo tanto, se avanza en cada programa, independientemente de la posible existencia de un programa que no termina.
Otro ejemplo es simular una máquina de Turing no determinista M mediante una determinista (por ejemplo, mediante una máquina de Turing universal ). En tal caso, necesitamos utilizar el método de cola de milano en caso de que una de las ramas de cálculo de M contenga un bucle infinito.
En el caso de un número infinito de programas, todos potencialmente infinitamente largos, ni el orden de amplitud ni el orden de profundidad serían suficientes para asegurar el progreso en todos los programas. En su lugar, se puede utilizar la siguiente técnica: realizar el primer paso del primer programa; a continuación, realizar el segundo paso del primer programa y el primer paso del segundo programa; a continuación, realizar el tercer paso del primer programa, el segundo paso del segundo programa y el primer paso del tercer programa; y así sucesivamente. Esto también se conoce como diagonalización (como se utiliza, por ejemplo, en el paquete "universe" o la mónada "Omega" de Haskell).
Una analogía con los extremos entrelazados de una unión de cola de milano en la carpintería .