Optimización de corte de gráfico
La optimización de corte de gráfico es un método de optimización combinatoria aplicable a una familia de funciones de variables discretas , que recibe su nombre del concepto de corte en la teoría de redes de flujo . Gracias al teorema de corte mínimo de flujo máximo , determinar el corte mínimo en un gráfico que representa una red de flujo es equivalente a calcular el flujo máximo en la red. Dada una función pseudo-booleana , si es posible construir una red de flujo con pesos positivos tal que
entonces es posible encontrar el óptimo global de en tiempo polinomial calculando un corte mínimo del gráfico. El mapeo entre cortes y asignaciones de variables se realiza representando cada variable con un nodo en el gráfico y, dado un corte, cada variable tendrá un valor de 0 si el nodo correspondiente pertenece al componente conectado a la fuente, o 1 si es pertenecen al componente conectado al fregadero.
No todas las funciones pseudobooleanas se pueden representar mediante una red de flujo y, en el caso general, el problema de optimización global es NP-difícil . Existen condiciones suficientes para caracterizar familias de funciones que se pueden optimizar mediante cortes de gráficos, como las funciones cuadráticas submodulares . La optimización del corte de gráficos se puede extender a funciones de variables discretas con un número finito de valores, que se pueden abordar con algoritmos iterativos con fuertes propiedades de optimización, calculando un corte de gráfico en cada iteración.
La optimización del corte de gráficos es una herramienta importante para la inferencia sobre modelos gráficos como los campos aleatorios de Markov o los campos aleatorios condicionales , y tiene aplicaciones en problemas de visión por computadora como la segmentación de imágenes , [1] [2] eliminación de ruido , [3] registro [4] [5] y emparejamiento estéreo . [6] [7]
