¿Cómo debo generar las particiones/pares para el problema del cartero chino?

Question

Estoy trabajando en un programa para la clase que implica resolver el Chinese Postman problem. Nuestra tarea solo requiere que escribamos un programa para resolverlo en un gráfico codificado, pero estoy tratando de resolverlo solo para el caso general.

La parte que me está dando problemas es generar las particiones de emparejamientos para los vértices impares.

Por ejemplo, si tuviera los siguientes vértices impares etiquetados en un gráfico:

1 2 3 4 5 6 

Necesito encontrar todos los posibles emparejamientos/particiones que puedo hacer con estos vértices.

he dado cuenta de que voy a tener i paritions dadas:

n = num of odd verticies 
    k = n/2 
    i = ((2k)(2k-1)(2k-2)...(k+1))/2^n 

Por lo tanto, teniendo en cuenta los 6 vértices impares anteriores, sabremos que tenemos que generar i = 15 particiones.

Los 15 partions se vería así:

1 2 3 4 5 6 
1 2 3 5 4 6 
1 2 3 6 4 5 
... 
1 6 ... 

Entonces, para cada partición, tomo cada par y encontrar la distancia más corta entre ellos y la suma de ellos para esa partición. Se selecciona la partición con la distancia total más pequeña entre sus pares, y luego doblo todos los bordes entre la ruta más corta entre los vértices impares (que se encuentran en la partición seleccionada).

Estos representan los bordes que el cartero tendrá que caminar dos veces.

Al principio pensé que había elaborado un algoritmo adecuado para la generación de estas particiones:

1. empezar con todos los vértices impares ordenados en orden creciente

   12 34 56

2. Seleccionar el par detrás del par que actualmente tiene el vértice máximo

   12 [34] 56

3. Aumenta el segundo dígito en este par en 1. Dejar todo a la izquierda de la par seleccionado el mismo, y crea todo a la derecha de el par seleccionado los números restantes del conjunto, ordenados en orden creciente.

   12 35 46

4. Repita

Sin embargo, esto es defectuosa.Por ejemplo, he dado cuenta de que cuando llegue hasta el final y el par de selección está en la posición más a la izquierda (es decir,):

[16] .. ..

El algoritmo trabajé fuera se detendrá en este caso, y no genera el el resto de los pares que comienzan [16], porque no hay par a la izquierda para alterar.

Por lo tanto, está de vuelta al tablero de dibujo.

¿Alguien que haya estudiado este problema antes tiene algún consejo que pueda ayudarme a orientarme en la dirección correcta para generar estas particiones?

Answer 1

Puede construir las particiones utilizando un algoritmo recursivo.

Tome el nodo más bajo, en este caso nodo 1. Esto debe estar emparejado con uno de los otros nodos sin emparejamiento (2 a 6). Para cada uno de estos nodos, cree con el partido 1, luego encuentre todos los pares de los 4 elementos restantes usando el mismo algoritmo en los cuatro elementos restantes.

En Python:

def get_pairs(s): 
    if not s: yield [] 
    else: 
     i = min(s) 
     for j in s - set([i]): 
      for r in get_pairs(s - set([i, j])): 
       yield [(i, j)] + r 

for x in get_pairs(set([1,2,3,4,5,6])): 
    print x 

Esto genera las siguientes soluciones:

[(1, 2), (3, 4), (5, 6)] 
[(1, 2), (3, 5), (4, 6)] 
[(1, 2), (3, 6), (4, 5)] 
[(1, 3), (2, 4), (5, 6)] 
[(1, 3), (2, 5), (4, 6)] 
[(1, 3), (2, 6), (4, 5)] 
[(1, 4), (2, 3), (5, 6)] 
[(1, 4), (2, 5), (3, 6)] 
[(1, 4), (2, 6), (3, 5)] 
[(1, 5), (2, 3), (4, 6)] 
[(1, 5), (2, 4), (3, 6)] 
[(1, 5), (2, 6), (3, 4)] 
[(1, 6), (2, 3), (4, 5)] 
[(1, 6), (2, 4), (3, 5)] 
[(1, 6), (2, 5), (3, 4)]