Advertencia: no soy un programador competitivo. No sé lo que puedes y no puedes hacer. Sin embargo, sí sé algo sobre cómo resolver problemas de correspondencia.
Como saben, la coincidencia bipartita es increíblemente flexible. Puede arrojar todo tipo de restricciones extrañas a los problemas de coincidencia y luego golpearlo con el martillo bipartito.
No estoy tan familiarizado con la teoría de gráficos, por lo que me apoyo principalmente en el flujo al resolver problemas de coincidencia bipartita. Creo que puedes resolver el flujo máximo en algo como O (VE). No me sorprendería saber que este no es el enfoque más eficiente para todas las instancias de coincidencia bipartita.
- Un hombre llega a su oficina en 2 horas y regresa en 3 horas. La ruta a su oficina incluye un sendero inclinado hacia arriba, 8 km y senderos inclinados hacia abajo. Cada vez que viaja hacia arriba, su velocidad es de 60 km / h, mientras que en un plano de 80 km / h, y cubre hacia abajo a una velocidad de 100 km / h. ¿A qué distancia está su oficina?
- ¿Qué algoritmos de programación de procesos usa Android?
- ¿Podemos encontrar si la matriz no contiene un elemento mayoritario en un tiempo casi constante?
- ¿Cuál es mi concepto erróneo con respecto al algoritmo de clasificación de fusión aquí?
- ¿De dónde provienen los datos de entrenamiento para analizar las consultas en inglés en un árbol para Facebook GraphSearch?
¿Cómo te pones mejor? Resolviendo muchos problemas y probándolos. Creo que una comprensión sólida del flujo y la circulación es realmente muy útil. Una vez que obtenga el patrón, la coincidencia bipartita será muy fácil.
Revisaré un problema de coincidencia bastante simple (capítulo 7, problema 20 de Algo Design por Kleinberg y Tardos) en caso de que no tenga mucha experiencia con la conversión de problemas a coincidencias:
Tienes n condiciones climáticas para medir. Para aumentar la fiabilidad, desea medir cada condición k veces. Tienes m globos meteorológicos para medir estas condiciones. Ningún globo puede medir la misma condición dos veces. Sin embargo, cada globo solo puedo medir los tipos de condiciones S_i establecidos. Además, cada globo solo puede capturar 2 mediciones antes de que explote y regrese a la tierra. ¿Cómo se combinan los globos con las medidas?
Muy bien, obtengamos un gráfico bipartito para esto.
Nuestros dos conjuntos son globos y medidas, así que hagamos un vértice para cada globo y un vértice para cada condición. Cada globo i puede medir cada condición c en S_i, así que conectemos el globo i a cada condición c en S_i.
¡Genial, tenemos un gráfico bipartito! Pero no hemos tenido en cuenta la cantidad limitada de mediciones que puede tomar cada globo o la cantidad de veces que queremos medir cada condición, etc. ¿Cómo se pueden agregar estas restricciones?
Recuerde que la coincidencia bipartita se puede resolver como un problema de flujo máximo. Flow nos permite imponer todo tipo de restricciones en la coincidencia. Primero, descubramos qué significa una unidad de flujo en este contexto. En este problema, una unidad de flujo es una medida porque las mediciones “fluyen” desde los globos a las condiciones.
Impresionante, ahora podemos convertir la coincidencia en flujo agregando una fuente y un nodo sumidero. Conecte la fuente a los globos y el fregadero a las medidas. Vamos a imponer restricciones.
Cada globo solo puede tomar 2 medidas, por lo que permite establecer la capacidad de borde que va desde la fuente a los globos a 2.
Cada globo solo puede medir una condición una vez, así que configuremos las capacidades de borde entre globos y mediciones en 1.
Cada medida debe tomarse k veces, medir más de lo que sería un desperdicio, así que configuremos las capacidades que van desde los globos hasta el fregadero en k.
Ahora podemos obtener el flujo máximo, pero ¿cómo podemos determinar si las condiciones se pueden medir? Una unidad de flujo es una medida, por lo que el flujo máximo es el número máximo de mediciones tomadas. Tenemos n condiciones y necesitamos medir cada k veces, por lo que queremos un total de n * k mediciones. Si el flujo es igual a n * k, entonces podemos medir todas las condiciones. Desde allí, puede retroceder a través del flujo para descubrir qué va a dónde.
¿Cuál es el patrón aquí? Calcule sus conjuntos, conviértalos en flujo y luego agregue restricciones. A veces necesita agregar nodos intermedios o capas adicionales entre los conjuntos. A veces necesitas usar la circulación. En general, creo que el flujo es una forma efectiva de ver los problemas de coincidencia bipartita. Pero nuevamente, creo que la mejor manera de mejorar estos problemas es resolver muchos de ellos.
