Algoritmia/Algoritmos de escalada

Los algoritmos de escalada representan una técnica muy utilizada en ciertas clases de problemas de optimización. La idea es comenzar con una solución sub-óptima del problema y, repetidamente, mejorar la misma hasta que cierta condición sea maximizada.

La metodología a seguir en este tipo de algoritmos es la siguiente:

Construir una solución sub-óptima que reúna los requisitos del problema
Tomar la solución y mejorarla hasta que se alcance la solución o no se pueda mejorar más

Este tipo de algoritmos suelen compartir la propiedad de ser eficientes en tiempo y espacio. Por el contrario, no siempre encuentran una solución óptima al problema planteado.

Uno de los problemas de escalada más famosos es el problema del flujo de red. Aunque pueda parecer un problema específico, es importante debido a su alto poder expresivo; por ejemplo, muchos problemas algorítmicos encontrados en la práctica pueden considerarse como casos especiales de flujo de red.

Ejemplos

Método de las raíces de Newton

Consideremos el problema de encontrar un número positivo x tal que cos(x) = x³. Podríamos tratar de encontrar el cero de f(x) = cos(x) - x³.

Sabemos que f '(x) = -sin(x) - 3x². Ya que cos(x) ≤ 1 para todo x y x³ > 1 para x>1, deducimos que nuestro cero está entre 0 y 1. Comenzaremos probando con el valor inicial x₀ = 0,5

{\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&0,5-{\frac {\cos(0,5)-0,5^{3}}{-\sin(0,5)-3\times 0,5^{2}}}&=&1,112141637097\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &=&{\underline {0}},909672693736\\x_{3}&&\vdots &&\vdots &=&{\underline {0,86}}7263818209\\x_{4}&&\vdots &&\vdots &=&{\underline {0,86547}}7135298\\x_{5}&&\vdots &&\vdots &=&{\underline {0,8654740331}}11\\x_{6}&&\vdots &&\vdots &=&{\underline {0,865474033102}}\end{matrix}}

Los dígitos correctos están subrayados. En particular, x₆ es correcto para el número de decimales pedidos. Podemos ver que el número de dígitos correctos después de la coma se incrementa desde 2 (para x₃) a 5 y 10, ilustando la convergencia cuadrática.

Problema del flujo de red