algorithm - programacion - ¿Cuál es el algoritmo de programación dinámica para encontrar un ciclo hamiltoniano en un gráfico?
programacion dinamica aplicada (2)
¿Qué es el algoritmo de programación dinámica para encontrar un ciclo hamiltoniano en un gráfico no dirigido? He visto en alguna parte que existe un algoritmo con complejidad de tiempo O(n.2^n) .
De hecho, existe un algoritmo de programación dinámica O (n2 n ) para encontrar ciclos hamiltonianos. La idea, que es general y puede reducir muchos enfoques O (n!) De retroceso a O (n 2 2 n ) u O (n2 n ) (al costo de usar más memoria), es considerar los subproblemas que son conjuntos con "puntos finales" especificados .
Aquí, como desea un ciclo, puede comenzar en cualquier vértice. Así que arregla uno, llámalo x . Los subproblemas serían: “Para un conjunto dado S y un vértice v en S , ¿hay un camino que comience en x y que atraviese todos los vértices de S , que termine en v ?” Llame a este, digamos, poss[S][v] .
Al igual que con la mayoría de los problemas de programación dinámica, una vez que define los subproblemas, el resto es obvio: recorrer todos los 2 n conjuntos de vértices en un orden "creciente", y para cada v en cada uno de esos S, puede calcular poss[S][v] como:
poss [S] [v] = (existe
uen S, de modo que poss [S− {v}] [u] es Verdadero y existe un bordeu->v)
Finalmente, hay un ciclo hamiltoniano si hay un vértice v tal que exista un borde v->x y poss[S][v] sea Verdadero, donde S es el conjunto de todos los vértices (excepto x , dependiendo de cómo lo definió).
Si desea el ciclo Hamiltoniano real en lugar de simplemente decidir si existe uno o no, haga que poss[S][v] almacene la u real que lo hizo posible en lugar de solo Verdadero o Falso; De esa manera puedes rastrear un camino al final.
No puedo extraer ese algoritmo en particular, pero hay más sobre Hamiltonian Cycles en The Hamiltonian Page de lo que probablemente nunca necesitarás. :)
Esta página pretende ser una lista completa de artículos, código fuente, preimpresiones, informes técnicos, etc., disponibles en Internet sobre el Ciclo de Hamilton y los Problemas de la ruta de Hamilton, así como algunos problemas asociados.