Aprendizaje Interactivo de Teoría de Grafos
Aprendizaje Interactivo de Teoría de Grafos
Guest User
Using app without sign in
Buscador de caminos hamiltonianos
Halla un camino que visita cada vértice exactamente una vez
Selecciona un algoritmo y genera pasos para comenzar la visualización
Un camino hamiltoniano visita cada vértice de un grafo exactamente una vez; un ciclo hamiltoniano además regresa al vértice inicial. Decidir si tal camino existe es NP-completo, en claro contraste con el camino euleriano, comprobable en tiempo lineal.
Los algoritmos exactos usan retroceso: extender un camino parcial un vértice a la vez, podando cuando el vértice actual no tiene vecino sin visitar. La programación dinámica sobre subconjuntos (la misma técnica de máscara de bits que Held-Karp) resuelve el problema en O(n al cuadrado por 2 elevado a n). Reglas de poda útiles son las comprobaciones de grado y las pruebas de conectividad del grafo restante. Para clases especiales de grafos, como torneos o grafos que cumplen condiciones de grado de Dirac u Ore, la existencia está garantizada y hay algoritmos constructivos.
Los caminos hamiltonianos aparecen en el ensamblaje de genomas, el diseño y prueba de circuitos, los juegos de rompecabezas como el recorrido del caballo y como núcleo estructural del TSP. En entrevistas, la solución de programación dinámica con máscara de bits es una pregunta difícil habitual, y el contraste con el camino euleriano evalúa la claridad conceptual.
No se conoce ningún algoritmo polinómico, así que la formulación honesta es retroceso con poda. La poda es lo que lo hace utilizable en absoluto.
CaminoHamiltoniano(grafo):
para cada vértice inicial s:
si retroceder([s], {s}): devolver el camino
devolver ninguno
retroceder(camino, visitados):
si visitados contiene todos los vértices: devolver verdadero
u = camino.último
para cada vecino v de u no visitado:
// Podas que se pagan solas:
// - algún vértice sin visitar ya inalcanzable -> fallar
// - dos o más vértices sin visitar de grado 1
// en el grafo restante -> fallar
visitados.añadir(v)
si retroceder(camino + [v], visitados): devolver verdadero
visitados.quitar(v) // deshacer y probar el siguiente
devolver falsoLa poda por alcanzabilidad es la que más importa. Tras elegir un camino parcial, ejecuta un recorrido rápido sobre los vértices sin visitar; si alguno queda ahora incomunicado del extremo actual, la rama está muerta y puede abandonarse de inmediato en lugar de tras explorar todo un subárbol. En grafos dispersos esto convierte una búsqueda intratable en una rápida, aunque el peor caso siga siendo exponencial.
Busca un camino hamiltoniano desde A en un grafo de cinco vértices, y observa por qué ese mismo grafo no tiene ningún ciclo hamiltoniano.
Grafo de ejemplo: Aristas no dirigidas A-B, B-C, C-D, D-E, más las dos cuerdas A-C y B-D.
Existen dos caminos hamiltonianos, A-B-C-D-E y A-C-B-D-E, pero ningún ciclo hamiltoniano. El vértice E de grado 1 resuelve casi por sí solo ambas preguntas: se obliga a ser extremo del camino y descarta cualquier ciclo, ya que un ciclo exige que todo vértice tenga grado al menos 2. Comprobar los grados antes de buscar es barato y con frecuencia decisivo.
Tiempo: O(V!) ingenuo, O(V^2·2^V) con PD · Espacio: O(V·2^V) con PD
El retroceso ingenuo explora permutaciones y es O(V factorial) en el peor caso, algo desesperado más allá de unos 12 vértices. La programación dinámica de Held-Karp sobre subconjuntos lo hace mucho mejor: el estado es un subconjunto de vértices visitados junto con el extremo actual, lo que da 2 elevado a V por V estados, y cada transición cuesta O(V), así que el total es O(V al cuadrado por 2 elevado a V) en tiempo y O(V por 2 elevado a V) en memoria. Eso es practicable hasta unos 20 vértices, donde 2 elevado a 20 por 20 son unos 20 millones de estados. El problema es NP-completo, así que no se espera que exista un algoritmo polinómico; el retroceso con poda a menudo termina rápido en grafos dispersos reales pese al peor caso exponencial.
Confirma qué problema tienes en realidad antes de recurrir a maquinaria exponencial, porque dos de estos son fáciles.
| Alternativa | Prefiérela cuando | Coste |
|---|---|---|
| Camino euleriano | Necesitas cada ARISTA una vez en lugar de cada vértice. Tiempo lineal contando grados. | O(V + E) |
| PD de Held-Karp | Menos de unos 20 vértices y necesitas un sí o un no definitivo. | O(V^2·2^V) |
| Heurísticas de TSP | El grafo es completo con pesos y quieres una buena gira en lugar de una prueba de existencia. | O(n^2) por pasada de 2-opt |
| Condiciones suficientes de Dirac y Ore | Solo necesitas demostrar que existe un ciclo. Si todo grado es al menos V/2, existe, sin búsqueda alguna. | O(V) |
| Ordenación topológica | El grafo es un DAG. Existe camino hamiltoniano exactamente cuando los vértices consecutivos del orden topológico único son adyacentes. | O(V + E) |
Leer el artículo completo: Eulerian Paths and Circuits
Algoritmos relacionados: Camino Euleriano (No Dirigido), Problema del Viajante, Búsqueda en Profundidad