Estoy escribiendo un programa, resolviendo el problema del cartero chino (también conocido como problema de inspección de ruta) en un diagrama no dirigido y actualmente enfrento el problema para encontrar los mejores bordes adicionales para conectar los nodos con un grado impar, para poder calcular un circuito euleriano.
Puede haber (considerando el tamaño del gráfico que quiere ser resuelto) una enorme combinación de aristas que deben calcularse y evaluarse.
Como ejemplo están los nodos impar grados . Las mejores combinaciones podrían ser:
- , , ,
- , , ,
- , , ,
- ....
donde significa "borde entre el nodo y el nodo ".
Por lo tanto, mi pregunta es: ¿existe un algoritmo conocido para resolver ese problema en una complejidad mejor que la fuerza bruta pura (calcular y evaluar a todos)?
€: Después de un esfuerzo de investigación, encontré este artículo, hablando sobre el "algoritmo de coincidencia de longitud mínima de Edmonds", pero no puedo encontrar ningún pseudocódigo o descripciones de aprendizaje de este algoritmo (o al menos no los reconozco, como Google ofrece muchos éxitos y algoritmos de coincidencia de J. Edmonds)
Respuestas:
Como se observó en los comentarios, Wikipedia ofrece una reducción de la inspección de ruta a coincidencias de peso mínimo . Vladimir Kolmogorov ha publicado una implementación rápida de la versión ponderada del algoritmo de flor de Edmonds, en C ++ [1].
[1] V. Kolmogorov, Blossom V: una nueva implementación de un algoritmo de coincidencia perfecta de costo mínimo . Computación de programación matemática , 1 (1): 43–67, 2009.
fuente