El acoplamiento , 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 el acoplamiento a veces se denominan complementos .
Considere un árbol que potencialmente contiene una ruta de longitud infinita: 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 del árbol sin explorar. Sin embargo, si se utiliza una búsqueda en amplitud , la existencia de una ruta infinita ya no es un problema: cada nodo se visita de manera ramificada según su distancia desde la raíz, por lo que una ruta infinita solo afectará la parte de la raíz. buscar viajando por 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 de que uno de los programas se ejecute durante un período de tiempo infinito, esta transición nunca sucederá. El enfoque de la amplitud de visitar a cada niño en el mismo nivel del árbol corresponde al acoplamiento, donde se realiza un solo paso para cada programa antes de pasar al siguiente. Así, se avanza en cada programa, independientemente de la posible existencia de un programa de tiempo de ejecución infinito.
En el caso de un número infinito de programas, todos potencialmente infinitamente largos, ni la amplitud ni la profundidad serían suficientes para asegurar el progreso de 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 primer paso del segundo programa y el segundo paso del primer programa; a continuación, realice el primer paso del tercer programa, el segundo paso del segundo programa y el tercer paso del primer programa; y así.
- Nota: Podríamos acoplar el mecanismo de combinación de algoritmos de profundidad primero (sin cola de milano) y de ancho (sin cola de milano). Esta aplicación recursiva del algoritmo de acoplamiento a sí mismo conduce a un número infinito de nuevos algoritmos, cada uno de los cuales implica un acoplamiento ligeramente menor.
Etimología
- Una analogía con los extremos entrelazados de una junta de cola de milano en la carpintería .