Barriendo el parque

Enunciado

Varios comentarios solucionan este problema, pero sin dar detalles ni método.

Para resolver este tipo de problemas viene muy bien recordar una regla muy sencilla. Un dibujo se puede recorrer sin pasar dos veces por la misma línea sólo cuando hay ninguno o dos cruces con una cantidad impar de líneas. Si no hay ninguno, entonces puedes empezar en cualquier cruce, y acabarás en el mismo, y si hay dos, debes empezar por uno de ellos y acabar en el otro.

¿Por qué sucede eso? Pues porque cada vez que llegues a un cruce usas dos líneas: la de entrada y la de salida, de forma que en todos los cruces debe sumar una cantidad par, excepto tal vez en la de salida y la de llegada, en las que también será obligatorio si comienzas y acabas en el mismo sitio.

Sabiendo esto, vamos a contar cuántas líneas llegan a cada cruce. En el A coinciden 3, en el B, 3, en el C, 2, en el D, 4, en el E, 2, en el F, 3, en el G, 3, en el H, 5, en el I, 3. Eso hace un total de 6 cruces (nodos, en el lenguaje técnico) con caminos impares. Necesitamos quitar o añadir al menos dos caminos (lo que equivale a no recorrer, o recorrer dos veces algunos de los que hay), para volver pares cuatro de los seis nodos que no nos conviene.

Pero si quiere salir de H, recorrer todos los caminos, y volver a H, necesitamos que todos los nodos sean pares, lo que nos obligará a recorrer un mínimo de 3 caminos dos veces.

¿Cómo podemos averiguar la combinación menor? Tratando de estudiar si recorrer los caminos más cortos dos veces nos soluciona o no el problema (vuelve pares los vértices que nos interesa) y encontrando la combinación más baja posible.

Si buscas soluciones con tres caminos, encontramos las combinaciones HB + FI + AG (70 + 80 + 80 = 230) y también HG + IF + AB (50 + 80 + 100 = 230). Recorrer dos veces esos caminos, en cualquier orden, nos lleva a una solución óptima. Y si tratamos de seguir más caminos, recorreremos más longitud con seguridad, ya que es imposible lograr menos de esos 230 metros extras.

Por ejemplo, si optamos por duplicar HG, IF y AB, podemos hacer HBAHGABCDEFIDHGFIH, y sumaremos los 1320 obligatorios más los 320 extras, es decir, 1550. Aunque hay varios recorridos posibles, según por donde doblemos cada vez.

Si optamos por duplicar HB, FI y AG, por ejemplo podemos recorrer HBAHGAGFIHBCDEFIDH, obteniendo de nuevo 1550 metros. De nuevo hay varias opciones.