Problema del cartero chino: encontrar las mejores conexiones entre nodos de grados impares

9

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:A,B,C,D,E,F,G,H

  1. AB , , ,CDEFGH
  2. AC , , ,BDEHFG
  3. AD , , ,BCEGFH
  4. AE ....

donde significa "borde entre el nodo y el nodo ".ABAB

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)

Sim
fuente
44
Wikipedia dice que hay un algoritmo para el problema del cartero chino. O(n3)
hugomg
Lo sé, pero todavía tengo curiosidad por saber cómo hacerlo.
Sim
2
Estas notas de clase tratan el problema del cartero chino: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf
Alex ten Brink
Sim, estoy interesado en su software porque me enfrento a un problema de mapeo: help.openstreetmap.org/questions/13197/… Buena suerte con su proyecto. pm en pmbooks dot com
pruebe el artículo que vinculé, describe un algoritmo de coincidencia de longitud mínima, pero debido a mi falta de experiencia y la falta de pseudocódigo, lamentablemente no pude implementarlo.
Sim

Respuestas:

1

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.

David Richerby
fuente
1
Y no lo llamemos el "problema del cartero chino". El único vínculo con China es que fue introducido por Mei-Ko Kwan y su nacionalidad es irrelevante para el problema. Nombrarlo "chino" sugiere que lo más importante de él es su origen étnico. No nos referimos, por ejemplo, al conocido algoritmo para calcular rutas más cortas en gráficos como "el algoritmo holandés" o, peor aún, "el algoritmo del hombre blanco". (Sí, me opongo al "teorema del resto chino" por la misma razón, pero ese caballo
salió corriendo