Cubierta de borde ponderada mínima: ¿el algoritmo codicioso es subóptimo?
La publicación aquí: Resolver la cobertura del borde mínimo utilizando el algoritmo de coincidencia máxima proporciona una manera de obtener la cobertura del borde mínimo a partir de una coincidencia máxima agregando con avidez bordes en la parte superior de la coincidencia máxima hasta que se cubran todos los vértices. Ahora, pensando en el problema de la cobertura del borde ponderado mínimo, parecería que este enfoque se puede ampliar. Primero, encuentre la coincidencia ponderada mínima con los bordes máximos , y luego agregue los bordes del peso más pequeño con avidez, primero los de peso más pequeño.
Sin embargo, leyendo la sección 19.3 del libro "Optimización combinatoria: poliedros y eficiencia" de Schrijver, se presenta un algoritmo más complicado. Esto hace que parezca que mi enfoque anterior no es óptimo. ¿Es posible encontrar un contraejemplo, preferiblemente en un gráfico de dos partes, donde mi algoritmo codicioso no podría proporcionar una solución óptima? No he podido encontrar uno con algunos gráficos de juguetes.
Respuestas
Aquí hay un contraejemplo de su algoritmo propuesto:
La solución óptima consta de 3 bordes y cuesta 3 + 1 + 1 = 5, pero la coincidencia de cardinalidad máxima de costo mínimo, que consta de 2 bordes y cuesta 3 + 3 = 6, se elegirá en el primer paso de su algoritmo e inmediatamente regresó, ya que ya es una solución. (La única otra coincidencia de cardinalidad máxima cuesta 1 + 6 = 7).