algorithm - most - ¿Qué es la manejabilidad de parámetro fijo? ¿Por qué es útil?
seo meta name (1)
Algunos problemas que son NP-hard también son manejables con parámetros fijos , o FPT. Wikipedia describe un problema como un parámetro fijo manejable si hay un algoritmo que lo resuelve en el tiempo f (k) · | x | O (1) .
¿Qué significa esto? ¿Por qué es útil este concepto?
Para empezar, bajo el supuesto de que P ≠ NP, no hay algoritmos exactos de tiempo polinómico para ningún problema de NP-difícil. Aunque no sabemos si P = NP o P ≠ NP, no tenemos algoritmos de tiempo polinómico para ningún problema de NP.
La idea detrás de la capacidad de resolución de parámetros fijos es tomar un problema de NP-duro, del cual no conocemos ningún algoritmo de tiempo polinomial, y tratar de separar la complejidad en dos partes, una parte que depende únicamente del tamaño de la entrada, y alguna pieza que depende de algún "parámetro" del problema.
Como ejemplo, considere el problema de mochila 0/1 . En este problema, se le da una lista de n objetos que tienen pesos y valores asociados, junto con un peso máximo W que puede llevar. La pregunta es determinar la cantidad máxima de valor que puede llevar. Este problema es NP-duro, lo que significa que no hay un algoritmo de tiempo polinómico que lo resuelva. Un método de fuerza bruta tomará tiempo alrededor de O (2 n ) al considerar todos los subconjuntos posibles de los elementos, lo que es extremadamente lento para n grande. Sin embargo, es posible resolver este problema en el tiempo O (nW), donde n es el número de elementos y W es la cantidad de peso que puede llevar. Si observa el tiempo de ejecución O (nW), notará que está dividido en dos partes: un componente que es lineal en el número de elementos (la parte n) y un componente que es lineal en el peso (la parte W). Si W es una constante fija, entonces el tiempo de ejecución de este algoritmo será O (n), que es de tiempo lineal, aunque el problema en general es NP-duro. Esto significa que si tratamos W como un "parámetro" ajustable del problema, para cualquier valor fijo de este parámetro, el problema terminará ejecutándose en tiempo polinomial (que es "manejable", en el sentido de la teoría de la complejidad de la palabra).
Como otro ejemplo, considere el problema de encontrar rutas largas y simples en un gráfico. Este problema también es NP-duro, y el algoritmo ingenuo para encontrar rutas simples de longitud k en una gráfica lleva tiempo O (¡n! / (N - k)!), Que para k grande termina siendo superexponencial. Sin embargo, utilizando la técnica de color-coding , es posible resolver este problema en el tiempo O ((2e) k n 3 log n), donde k es la longitud de la ruta que se debe encontrar y n es el número de nodos en la entrada grafico. Observe que este tiempo de ejecución también tiene dos "componentes:" un componente que es un polinomio en el número de nodos en el gráfico de entrada (la parte n 3 log n) y un componente que es exponencial en k (la parte (2e) k ). Esto significa que para cualquier valor fijo de k, hay un algoritmo de tiempo polinomial para encontrar rutas de longitud-k en el gráfico; el tiempo de ejecución será O (n 3 log n).
En ambos casos, podemos tomar un problema para el cual tenemos una solución de tiempo exponencial (o peor) y encontrar una nueva solución cuyo tiempo de ejecución sea un poco polinomial en n veces alguna función de aspecto loco de algún "parámetro" adicional. En el caso del problema de la mochila, ese parámetro es la cantidad máxima de peso que podemos cargar; en el caso de encontrar rutas largas, el parámetro es la longitud de la ruta a encontrar. En términos generales, un problema se denomina parámetro fijo manejable si existe algún algoritmo para resolver el problema definido en términos de dos cantidades: n, el tamaño de la entrada y k, algún "parámetro", donde el tiempo de ejecución es
O (p (n) · f (k))
Donde p (n) es una función polinomial y f (k) es una función arbitraria en k. Intuitivamente, esto significa que la complejidad del problema se escala polinomialmente con n (lo que significa que a medida que aumenta el tamaño del problema, el tiempo de ejecución se escalará muy bien), pero puede escalar arbitrariamente mal con el parámetro k. Esto separa la "dureza inherente" del problema, de manera que la "parte difícil" del problema se atribuye al parámetro k, mientras que la "parte fácil" del problema se carga al tamaño de la entrada.
Una vez que tiene un tiempo de ejecución que parece O (p (n) · f (k)), inmediatamente obtenemos algoritmos de tiempo polinómico para resolver el problema para cualquier k fijo. Específicamente, si k es fijo, entonces f (k) es algo constante, por lo que O (p (n) · f (k)) es solo O (p (n)). Este es un algoritmo de tiempo polinomial. Por lo tanto, si "arreglamos" el parámetro, recuperamos un algoritmo "manejable" para resolver el problema. Este es el origen del término parámetro fijo tratable.
(Una nota: la definición de Wikipedia de capacidad de parámetros fijos dice que el algoritmo debe tener un tiempo de ejecución f (k) · | x | O (1) . Aquí | x | se refiere al tamaño de la entrada, que he llamado n aquí. Esto significa que la definición de Wikipedia es la misma que decir que el tiempo de ejecución es f (k) · n O (1) . Como se mencionó en esta respuesta anterior , n O (1) significa "algo de polinomio en n", y por lo tanto esto La definición termina siendo equivalente a la que he dado aquí.
La capacidad de resolución de parámetros fijos tiene enormes implicaciones prácticas para un problema. Es común encontrar problemas que son NP-difíciles. Si encuentra un problema que es manejable por parámetros fijos y el parámetro es bajo, puede ser significativamente más eficiente usar el algoritmo manejable de parámetros fijos que usar el algoritmo normal de fuerza bruta. El ejemplo de código de colores anterior para encontrar rutas largas en un gráfico, por ejemplo, se ha utilizado con gran éxito en biología computacional para encontrar rutas de secuenciación en células de levadura, y la solución de mochila 0/1 se usa con frecuencia porque los valores comunes de W son Lo suficientemente bajo como para que sea práctico.
¡Espero que esto ayude!