El polinomio de tiempo del algoritmo para la búsqueda de un Hamiltoniano pie en un gráfico [cerrado]

Question

Existe un polinomio tiempo algoritmo para la búsqueda de un Hamiltoniano pie en una gráfica?

Mi algoritmo es N factorial y es realmente lento.

Answer 1

Sólo pidió a la pregunta del millón de dólares.Encontrar un camino de Hamilton es un NP-completo el problema.Algunos NP-duro de los problemas pueden ser resueltos en el polinomio tiempo usando programación dinámica, pero (a mi conocimiento) este no es uno de ellos.

Answer 2

En general, como la decisión de la versión de el) Camino Hamiltoniano problema es NP-completo, usted no puede esperar para obtener un polinomio de tiempo para el algoritmo de búsqueda de caminos Hamiltonianos.Usted puede ligeramente la velocidad con la habitual N!→ N²2^N programación dinámica truco (calcular hp[v][w][S] = "hay un camino que tiene los extremos de v y w y cuyos vértices son el subconjunto S" para cada subconjunto S y cada dos vértices v y w en la que el uso de DP), pero que sigue siendo exponencial.

Sin embargo, hay muchos tipos de gráficos para que Hamiltonianos caminos van a existir siempre, y que se pueden encontrar fácilmente (véase el trabajo de Posa, Dirac, Mineral, etc.)

Por ejemplo, el siguiente es cierto: Si cada vértice de la gráfica tiene un grado al menos n/2, a continuación, la gráfica tiene un camino Hamiltoniano.Usted puede encontrar uno en O(n²), o IIRC incluso de O(n log n) si lo haces más inteligentemente.
[Boceto:En primer lugar, sólo tiene que conectar todos los vértices en algunos "Hamiltoniano" del ciclo, no importa si los bordes son en realidad en el gráfico.Ahora, para cada arista (v,w) del ciclo que realmente no está en la gráfica, considere el resto del ciclo:v...w.Como deg(v)+gr(w)>=n, existen consecutivos de x,y en la lista (en ese orden) tal que w es un vecino de x y v es un vecino de y.[Prueba:Considere la posibilidad de {el conjunto de todos los vecinos de w} y {el conjunto de todos los sucesores en su lista de vecinos de v};ellos deben intersectarse.] Ahora cambie su ciclo [v...xy...wv] a [vy...wx...v] en su lugar, tiene, al menos, uno menos no válido borde, así que usted necesitará en la mayoría de las n iteraciones para obtener un verdadero ciclo Hamiltoniano.Más detalles aquí.]

BTW:si lo que buscas es sólo un paseo que incluye todos los borde una vez, eso se llama Euleriano a pie y para los gráficos que tiene (número de vértices de grado impar es de 0 o 2), uno puede muy fácilmente ser encontrado en el polinomio de tiempo (rápido).

Answer 3

Es NP completo.Pero si se las arreglan para encontrar un buen método, que me haga saber y yo te mostraré cómo hacerse rico.

Answer 4

Encontrar un algoritmo mejor para el menor es raro, ya que es NP duro.Pero hay algunas heurísticas que usted puede probar, y quizás desee consultar tus notas de la conferencia de esos ;) .

De menor complejidad, usted podría encontrar una breve(ish) a pie utilizando el algoritmo voraz.

Answer 5

Hmmm..esto depende de lo que sus definiciones son.Un camino hamiltoniano es, sin duda NP-completo.Sin embargo, una de hamilton a pie que se pueden visitar las aristas y los vértices más de una vez (sí, todavía se llama hamiltonianos tan larga como la de agregar el pie poco al final) puede ser calculado en S(p^2logp) o o(max(c^2plogp, |E|)) tanto tiempo como el gráfico cumple una condición determinada que Dirac primera conjetura y la Takamizawa demostrado.Ver Takamizawa (1980) "Un algoritmo para encontrar un corto cerrado que abarca a pie en un gráfico".

Pablo

Answer 6

Dependiendo de la forma en que los gráficos se trabaja con se generan usted podría ser capaz de conseguir espera polinomio vez contra un random ejemplo, haciendo codiciosos extensión de ruta de acceso y, a continuación, un azar borde de intercambio al que se atasca.

Esto funciona bien contra generado aleatoriamente relativamente escasa, gráficos garantizado para tener un Hamiltoniano pie.

Answer 7

Mi Consulta:Demostrar que un problema de búsqueda RHAM para encontrar un ciclo Hamiltoniano en el grafo G es auto-reducible Un problema de búsqueda R es la auto-reducible si es de cocción se reduce a un problema de decisión
SR={ x : R(x) ≠ ∅ }