Hamilton Grafo Ponderado y los Problemas de Decisión de

Question

Me encontré con una pregunta en la anterior Mediados de Examen. alguien me podría aclarar?

Problema: Dado un Completo Grafo Ponderado G, encontrar un Hamiltoniano de Gira con el mínimo peso.

Problema B: Dado un Completo Grafo Ponderado G y el Número Real R, G tiene un Hamiltoniano de Gira con el peso en la mayoría de los R?

Supongamos que hay una máquina que resuelve B. ¿cuántas veces llamada de B (cada vez G y el número Real R), Podemos resolver Un problema con la máquina? supongamos que la suma de las Aristas en G hasta M.

1) We cannot do this, because there is uncountable state.

2) O(|E|) times

3) O(lg m) times

4) because A is NP-Hard, This is cannot be done.

Answer 1

Esta no es una respuesta, necesitaba más espacio que en el comentario a seguir mi discusión con Xoff

Yo estoy mostrando aquí que si usted sabe que el peso mínimo $R_m$ de un ciclo Hamiltoniano, se puede construir uno de peso $R_m$ $|E|$ llamadas a B.

Supongo que todos los que aquí el peso son positivos.

Yo denotar aquí $B(G,w,R)$ la llamada de $B$ $G$ con el peso de la función $w$ y el vinculado $R$.

Deje $\{e_1,...,e_n\}$ ser los bordes de la gráfica de $G$.

Tenga en cuenta el peso de la función $w_1$ tal que $w_1(e_1)=w(e_1)+R_m$$w_1(e_i)=w(e_i)$$i\neq 1$.

Si $B(G,w_1,R_m)$ es falso marcamos $e_1$.

Más generalmente definimos $w_k$ $w_k(e_k)=w_{k-1}(e_k)+R_m$ $w_k(e_i)=w(e_i)$ si $e_i$ está marcada por $w_k(e_i)=w_{k-1}(e_i)$ lo contrario.

De nuevo, si $B(G,w_k,R_m)$ es falso marcamos $e_k$.

Al final todos los bordes marcados pertenecen a un ciclo de peso $R_m$.

Answer 2

Los números reales no pueden ser manipulados por las máquinas : tienen infinitas tamaño y ni siquiera se puede responder a una simple pregunta como $$x=y$$ en números reales en tiempo finito.

Tener una máquina de $B$ que se ocupa de la infinita entrada es bastante extraño (salida de un solo bit, sin embargo). ¿Cómo se puede dar la entrada a $B$ ? ¿Cómo se puede manipular la entrada ?

Creo que la pregunta es no aceptar debido a este problema. Así que yo sería la respuesta 1 : no Podemos hacer esto, porque hay innumerables estado. Pero no es realmente satisfactorio, en realidad, depende de lo que sus pensamientos estaban en el maestro de la mente cuando escribió la pregunta.

Cualquier reales de manipulación en la computabilidad debe ser bien definido (son flotante los números, son computables reales definidas por un algoritmo, son lista infinita de dígitos o son definidos por infinitos intervalos cerrados como fracciones continuas). En función de las definiciones, usted puede o no puede hacer algunas cosas básicas como comparar o agregar números. Sin una adecuada definición, sólo podemos asumir el peor de los casos, y que no podemos manipular.