¿Lightning permite resolver problemas NP-completos?

Question

Soy un MS/BS ciencias de la computación hombre que se pregunta acerca de por qué rayos no se puede (o puede?) se utiliza para resolver problemas del tipo NP completo de problemas de forma eficiente, pero no entiendo la física detrás de un relámpago, así que voy a postear aquí.

Lo que parece peculiar para mí sobre los rayos es que parece seguir la "más fácil" ruta a un destino dado, frente a sólo el camino más corto. Esto parece análoga (idénticos?) para los pesos en el problema del viajante de comercio.

Desde el rayo proceso ioniza el aire y parece recoger el camino más sencillo, rápido, tengo 2 preguntas:

1) ¿el rayo utilizar un método similar al de Dijkstra enfoque (por ejemplo que un "lo suficientemente bueno" ruta de acceso se encuentra en el polinomio de tiempo, pero no necesariamente el mejor de todas las opciones")? Es básicamente un NP "solver"?

Si la respuesta a la pregunta anterior es "no" y de hecho es la mejor elección:

2) ¿Podría el proceso de selección de los relámpagos ser utilizado en un algoritmo de computadora para resolver un viajante de comercio-tipo de problema en el polinomio de tiempo, y

3) Si no, podría arbitraria de la serie de la ponderación de los nodos de estar físicamente en algún lugar y tener la electricidad pasa a través de él y hacer que los resultados se alimenta de nuevo en algún tipo de mecanismo informático para que cada vez que un usuario quiere saber un camino más corto?

Si usted podría usar este método para resolver problemas del tipo NP-duro rápidamente los problemas, usted tendría su nombre en las noticias y tal vez en los libros de historia. Así que ¿por qué nadie ha utilizado un rayo para resolver este problema?

ACTUALIZACIÓN: Otro aspecto que me parece interesante: cuando los relámpagos se ioniza el aire para encontrar el camino más corto. Si el mundo fuera totalmente plana (y las nubes eran también) esto ionizar el aire igualmente. Lo que me lleva a creer que la ruta "elegido" por el rayo incorpora todos los puntos, lo que parece ser un requisito para la búsqueda de la mejor de todas las soluciones.

Answer 1

1) sí, es básicamente va a encontrar una solución no óptima. En cada punto, la parte superior de la ray busca el mayor gradiente de potencial, la carga en los alrededores de volumen crece, determinando que el material circundante (aire en este caso) hasta que un mayor gradiente de la muestra y el rayo continúa en esa dirección. Esta es la razón por la lightining camino se ve como un rompecabezas; es básicamente un Monte Carlo de búsqueda.

Por no decir, que no se puede aplicar esto para encontrar soluciones eficientes de la travelsman problema. Esto requeriría hacer una programable de configuración con pesas relacionados con la capacitancia de modo que el arco eléctrico se encuentra la mejor ruta que también resuelve su matriz de adyacencia problema. Esto sería, probablemente, sólo se ve obstaculizada por el hecho de que el arco, para hacer el recorrido, debe quemar su camino a través de la capacitancia de la barrera, por lo menos que encontrar un barato, repleaceable material que también puede ser configurable (el peso se debe ajustar a la matriz de adyacencia de pesos) será más barato para hacer este cálculo en un ordenador estándar.