La combinación , en el diseño de algoritmos , es una técnica que entrelaza diferentes cálculos , realizándolos esencialmente de forma simultánea. Los algoritmos que utilizan cola de milano a veces se denominan cola de milano .
Considere un árbol que potencialmente contiene una ruta 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 moverse por una ruta infinita y nunca regresar, dejando potencialmente parte de el árbol inexplorado. 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 forma ramificada según su distancia a la raíz, por lo que un camino infinito sólo afectará a la parte del búsqueda recorriendo ese camino.
Podemos considerar este árbol como análogo a una colección de programas; en este caso, el enfoque de profundidad primero corresponde a ejecutar un programa a la vez, pasando al siguiente solo cuando el programa actual haya terminado de ejecutarse. En el caso de que uno de los programas se ejecute durante un tiempo infinito, esta transición nunca ocurrirá. El enfoque de amplitud primero de visitar a cada niño en el mismo nivel del árbol es un ejemplo de encaje, donde se realiza un solo paso para cada programa antes de pasar al siguiente. De este modo, se avanza en cada programa, independientemente de la posible existencia de un programa que no termine.
Otro ejemplo es la simulación de una máquina de Turing no determinista M mediante una determinista (por ejemplo, mediante una máquina de Turing universal ). En tal caso, necesitamos usar 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 ellos potencialmente infinitamente largos, ni el primero en amplitud ni el primero en 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, realice el segundo paso del primer programa y el primer paso del segundo programa; a continuación, realice el tercer paso del primer programa, el segundo paso del segundo programa y el primer paso del tercer programa; etcétera. Por lo tanto, esto también se conoce como diagonalización (como se usa, por ejemplo, en el paquete "universo" de Haskell o en la mónada "Omega").
Una analogía con los extremos entrelazados de una unión en cola de milano en carpintería .