Teoría de gráficos: ¿Cuáles son algunas aplicaciones de la vida real en las que es necesario resolver el problema de corte máximo?

El corte de gráfico se usa para la segmentación de imágenes.

A partir de la imagen de entrada, se crea un gráfico. Los píxeles se definen como vecinos si son adyacentes ya sea horizontal, vertical o diagonalmente. Cada borde recibió un costo correspondiente a una propiedad de imagen local. Se puede basar en el gradiente de intensidad local, el cruce por cero laplaciano, la dirección del gradiente o el modelo de mezcla de colores.

Luego se usan dos “marcadores”. Por lo general, un marcador de objeto y un marcador de fondo.

El marcador de objeto es un conjunto de píxeles colocados en el objeto que desea obtener.

El marcador de fondo es un conjunto de píxeles colocados en el fondo.

Los marcadores no necesitan ser muy precisos. Un simple rectángulo dibujado con el mouse puede ser el marcador de fondo, y un punto simple seleccionado con el mouse puede ser el marcador del objeto.

Tienes un gráfico y dos conjuntos de vértices. Puede usar el algoritmo de corte gráfico. Como resultado, obtienes una frontera entre tus dos conjuntos de vértices. Por lo tanto, una segmentación de la imagen.

Mire grab-cut, un algoritmo de segmentación basado en corte de gráficos (aquí los resultados son de la implementación de OpenCv). Observe que el marcador de fondo es un rectángulo simple (y el marcador de objeto es el centro del rectángulo).

Gráficos recortados en visión artificial – Wikipedia

Un ejemplo de dónde se puede usar un corte máximo (o el corte máximo k) es al asignar centros de distribución. Digamos que está construyendo un nuevo hospital en una zona densamente poblada, ya que el sistema actual de ambulancias tiene un tiempo de respuesta demasiado alto. Al utilizar un corte máximo con los tiempos de respuesta de los hospitales, incluida la ubicación proyectada a las ubicaciones de los incidentes como longitudes de borde, puede determinar el tiempo máximo que una ambulancia necesitaría para llegar a una determinada ubicación y el área de cobertura de los hospitales. Con esta información, también puede estimar el tamaño requerido del nuevo hospital para acomodar el área.

(la ubicación real en el hospital tiende a ser un poco más compleja, pero esto proporciona una buena aproximación automatizada de la calidad de una ubicación)

Problemas similares incluyen: ¿dónde construyo una nueva estación de metro, dónde construyo un nuevo supermercado, pueden fusionarse las ubicaciones sin sacrificar la accesibilidad o puedo identificar grupos de existencias no correlacionadas en función de su covarianza?

Tenga en cuenta que estos modelos suelen ser parte de un modelo grande que también realiza un seguimiento de los costos, los ingresos y la pérdida / aumento potencial de los clientes.

Una aplicación que conozco es en visión artificial. solía distinguir el primer plano del fondo.