Problema del cartero chino
En teoría de grafos (una rama de la matemática), el problema del cartero chino (PCC), o problema del circuito del cartero, o problema de la inspección y selección de rutas, consiste en encontrar el camino más corto o circuito cerrado, que visite cada arista de un grafo (conectado) no direccionado, o sea, que pase al menos una vez por cada arista del grafo, volviendo al punto (o nodo) de partida. Cuando el grafo posee un circuito euleriano (un paseo cerrado que alcance toda arista solamente una vez), ese circuito es una solución óptima.
Alan J. Goldman[1] del Instituto Nacional de Estándares y Tecnología (EE. UU.), usó por primera vez la denominación 'problema del cartero chino' para este problema, ya que originalmente fue estudiado por el matemático chino Mei-Ko Kuan[2] en 1962, quien precisamente era cartero.[3][4]
Caminos y circuitos eulerianos[5]
Para que un grafo tenga un circuito euleriano, ciertamente tendrá que estar conectado.
Supongamos que tenemos un grafo conexo G = (V, E); entonces, las siguientes declaraciones son equivalentes:
- Todos los vértices (nodos) de G tienen grado par.
- G consiste de las aristas de una unión disjunta de algunos ciclos, y de los vértices de esos ciclos.
- G tiene un circuito euleriano.
- 1 → 2 puede ser demostrado por indución sobre el número de ciclos;
- 2 → 3 también puede ser demostrado por inducción sobre el número de ciclos; y
- 3 → 1 es inmediata.
Un camino euleriano (un camino que no es cerrado, pero que utiliza todas las aristas de G apenas una vez y solamente una vez) existe si y solamente si G es conectado y tiene dos vértices de valencia impar.
Enlaces-T
Sea T un subconjunto del conjunto de vértices de un grafo. El conjunto de aristas cuyos vértices de grado impar son los vértices en T es llamado enlace-T (en un grafo conexo, un enlace-T existe si y solamente si |T| es par). El problema del enlace-T consiste en encontrar el menor enlace-T. Y el menor enlace-T necesariamente lleva a una solución del problema del cartero chino.
En efecto, un menor enlace-T necesariamente consiste de |T| caminos, no habiendo dos con una arista en común, uniendo los vértices de T en pares. Los recorridos serán de tal forma que la extensión total de cada uno de ellos es tan pequeña como sea posible. Un enlace-T mínimo puede ser obtenido por un algoritmo de correspondencia ponderada que usa O(n3) pasos computacionales.[6]
Solución
Si un grafo tiene un circuito euleriano (o un camino euleriano), entonces un circuito euleriano (o camino) visita cada arista, y así la solución resulta ser cualquier circuito euleriano (o camino).
Y si un grafo no es euleriano, debe contener vértices de grado impar, y por aplicación del lema del apretón de manos, debe haber un número par de esos vértices. Entonces, para resolver el problema del cartero chino, primero debemos encontrar el menor enlace-T, y transformamos el grafo original en otro euleriano simplemente duplicando el enlace-T. Resulta entonces que la solución al problema del cartero chino en el grafo original, podrá ser obtenida o generada, sobre la base de la determinación de un circuito euleriano para el nuevo grafo.
Variantes
Pocas variantes del problema del cartero chino han sido estudiadas en forma exhaustiva (NP-completo).[7]
- (Minimización) Problema del cartero chino para grafos mixtos - En esta situación, algunas de las aristas podrían estar direccionadas y solamente podrían ser recorridas en la dirección permitida. El problema transversal mínimo de un digrafo es conocido como "problema del barrendero callejero de Nueva York".
- (Minimización) Problema del cartero k-Chino - Encontrar todos los ciclos de k elementos a partir de un local designado, de tal forma que cada arista sea atravesada por lo menos por un ciclo. El objetivo es minimizar el costo del ciclo más caro.
- Problema del cartero rural - Dado un subconjunto de aristas, encontrar el ciclo hamiltoniano más barato conteniendo una de esas aristas (y posiblemente otras). Este es un caso especial del problema general del enrutamiento mínimo, que especifica con precisión los vértices o ciclos que debe contener.
Otra descripción del método de resolución en el caso general
El mejor resultado que puede esperarse se obtiene encontrando un camino que pase exactamente una sola vez por cada arista, es decir, un ciclo euleriano. Tal camino existe si y solamente si cada nodo del grafo es de grado par.
En caso contrario, un camino optimal pasa al menos dos veces por una misma arista. En este último caso, es más simple considerar el problema alternativo siguiente: en vez de permitir de pasar varias veces por la misma arista, se duplican las aristas del grafo en donde se permite pasar dos veces. Obviamente, el problema planteado entonces es del mismo tipo, pero ahora aplicado a un grafo diferente.
La idea es naturalmente la de ir ampliando poco a poco el grafo, hasta que el mismo sea euleriano, y cuando se obtenga, buscar un circuito euleriano en el grafo completo.
Para mejor comprender el algoritmo propuesto, es útil comenzar pensando el caso de un grafo en donde solamente se tienen dos nodos u y v de grado impar. Entonces, la solución óptima consiste en encontrar el camino más corto del nodo u al nodo v (utilizando por ejemplo el algoritmo de Dijkstra), completando el grafo con las aristas de este camino.
Demostración
Después de haber agregado al grafo las aristas del camino más corto entre u y v, cada nodo es de grado par, y por lo tanto el grafo es euleriano, y por lo tanto tiene una solución válida.
En un grafo cualquiera con más de dos nodos de grado impar, será siempre par el número de nodos de grado impar, y entonces la solución óptima podrá ser obtenida con el siguiente algoritmo:[6]
- Formar un nuevo grafo G’, constituido únicamente por los nodos de grado impar del grafo inicial G.
- Entre dos nodos de G’, agregar un arista nueva con una longitud igual al más corto camino entre esos dos nodos en el grafo G.
- Establecer la serie de pesos mínimos en G’, lo que puede hacerse con un algoritmo de complejidad .
- Aplicar reiteradamente este mismo procedimiento, o sea, para cada par de nodos u y v en G’, agregar las aristas del camino más corto u a v en G.
Notas y referencias
- (en inglés) Biography written for "Goldmanfest", a celebration of Alan Goldman (and his new status as Emeritus Professor) held on April 30, 1999, sitio digital del 'Department of Applied Mathematics and Statistics / Johns Hopkings University'.
- (en inglés) Martin Grotschel, Ya-xiang Yuan, Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman el 20 de octubre de 2015 en Wayback Machine., University of Illinois at Urbana-Champaign (UIUC), documento pdf.
- (en inglés) "Chinese Postman Problem", sitio digital 'NIST'.
- (en inglés) International activities, algorithms, applications, and operations research texts and monographs from 1957 to 1963, documento pdf, pág. 136.
- (en inglés) Loh Bo Huai Victor, Eulerian path and circuit, documento pdf, 24 de enero de 2010.
- ↑ (en inglés) Jack Edmonds, Ellis L. Johnson, Matching, Euler tours and the Chinese postman, Mathematical Programming 5 (1973), págs 88-124, North-Holland Publishing Company (texto completo).
- (en inglés) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A compendium of NP optimization problems, sitio digital 'KTH NADA'.
Véase también
Enlaces externos
- (en inglés) Chinese Postman Problem.
- (en inglés) Paths, Trees, and Flowers.
- (en inglés) .
- Esta obra contiene una traducción parcial derivada de «Problema da inspeção de rotas» de la Wikipedia en portugués, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.
- Esta obra contiene una traducción parcial derivada de «Problème du postier chinois» de la Wikipedia en francés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.