En el mundillo de los ordenadores existen dos grupos de problemas, divididos por el tiempo que se tarda en resolverse. Se llaman problemas P los problemas que se resuelven en poco tiempo (por ejemplo hayar el resultado de multiplicar un numero de N cifras al cuadrado), y problemas NP a los problemas que se resuelven en mucho tiempo (por ejemplo saber cual es modo por el cual organizando unos objetos en una caja de modo que ocupen el menor espacio). A partir de un cierto numero de elementos los problemas NP se hacen irresolubles para los ordenadores actuales, al menos que esperemos miles de años. Se conjetura con que P=NP, es decir que existe algun algoritmo tal que resuleve un problema NP en un tiempo P. Encontar dicho algoritmo conlleva resolver la conjetura y uno de los supuestos problemas del milenio.
Resolver un problema
NP-completo de forma deterministica en el tiempo que se tarda en resolver
un problema P implica que todo problema NP puede resolverse en el intervalo
de tiempos correspondientes a la resolucion de un problema P.
Obtener la solucion
de un problema NP-completo determinista en un tiempo atribuible a un problema
P, verificaria que P=NP.
EL ALGORITMO “LLAMA ANTIENTROPICA”
Este algoritmo
haya la distancia mas corta que une dos puntos (A,B) de un grafo y encuentra
el recorrido que corresponde a esa distancia. Resuelve en un grafo de “ciudades”
donde los puntos se interpretan como “ciudades”. Para resolver este problema
habria que considerar todos los caminos posibles y compararlos entre ellos,
lo que lo convierte en un problema NP ya que con un grafo de n elementos
el numero de posibles caminos es n! Que es exponencial (NP).
El algoritmo “Llama
Antientropica” interpreta el grafo como si fuera un circuito de polvora.
En el punto A se prende una llama con el Tiempo en T1, la llama recorre
el circuito por todas las bifurcaciones a una velocidad v constante. Pueden
construirse dos algoritmos diferentes segun se quiera que la llama se vifurque
en la interseccion de caminos o no. La llama recorre aquellos caminos que
no han sido “quemados” antes. La llama termina recorriendo el camino
mas corto de A a B. Cuando la llama llega a B se para el crono en T2.
Este algoritmo convierte este problema exponencial (k^n,NP), en un problema donde para solucionar solo se requieren kn pasos, siendo k const.
Algoritmo para la resolucion del Problema del Agente Viajero Euclideo (PAVE)
El problema del agente viajero euclideo es un problema NP- completo.
Es mi intencion exponer de forma conceptual un nuevo algoritmo para la resolucion del problema del agente viajero en estas lineas, un algoritmo que se muestra dificil su programacion dados mis escasos conocimientosen en el area. Dicho algoritmo se encarga de la resolucion del subtipo de problemas del agente viajero denominados euclidianos, donde el peso de las aristas que unen cada vertice es la distancia entre los vertices. Trata asi mismo dicho algoritmo de resolver a priori (aun sin comprovacion experimental de dicho algoritmo ) de forma deterministica un problema NP-completo en tiempo polinomial
Algoritmo de correcion en descenso escalonado (CDE)
La explicacion mas sencilla sobre el algoritmo CDE proviene de la representacion de algunos ejemplo que sea tan ilustrativos como generales, de tal modo que la aplicación del algoritmo sobre cualquier otro problema sea facilmente deducible de dichos ejemplos.
Veamos pues dichos ejemplos, en la figura 1 se muestra un conjunto de 32 vertices (puntos en azul) donde se han omitido las uniones entre pares de vertices. El valor de dichas uniones o aristas viene dado por la longitud de las mismas. El problema trata de encontrar el camino cerrado mas corto que una todos los vertices.
1) Para empezar se haya el centro geometrico C (en rojo)de dichos vertices, para ello se suman las coordenadas (x,y) de todos los vertices involucrados y se divide entre el numero de vertices. Se representa dicho punto en el plano. Para este caso C es (0.25,0.29).
2) Con centro en C se construyen circulos (en rojo) tal que cada circulo contenga un vertice del plano, de tal modo que todos los vertices esten contenidos en dichos circulos. Mediante semirectas (en verde) que pasan por el punto C y cada uno de los vertices se proyectan todos los puntos sobre la circunferencia mas exterior. Se unen los puntos proyectados (en verde) con su contiguo mediante aristas (en negro).
3) A continuacion se realiza el proceso de Correccion en Descenso Escalonado. Manteniendo el circuito representado sobre el circulo exterior se proyectan los puntos sobre el circulo inmediatamente mas pequeño, excepto el punto que correspondia al circulo mas exterior (este punto no se mueve, ya esta en su posicion original). Cabria la posibilidad de que en dicha nueva configuracion el circuito representado no fuere el mas corto. Pero el camino mas corto apenas variara del original.
5) A continuacion se proyectan los puntos (escepto los que llegaron a su posicion) sobre el circulo inmediatamente menor conservando el nuevo circuito si lo hubiere, y se vuelve a realizar la correccion. El descenso y la correcion se llevan a cabo hasta que todos los puntos retornan a los originales. El algoritmo termina en dicho momento, quedado registrado el circuito obtenido en el ciclo.
Conclusiones
Existen ciertas añadidos al algoritmo de forma que se adapte
mejor a cada problema; como elegir un centro de gravedad distinto según
alguna propiedad. En caso de que las distancias en la correccion sean las
mismas los puntos se proyectan en un circulo imaginario un poco mas bajoetc.
El tiempo requerido por el algoritmo de CDE para resolver un problema
del agente viajero euclidiano es proporcional al numero de elemento al
cuadrado, pues se repiten N por escalon, por N escalones.
Pudiera ser posible que este algoritmo resolviera dicho problema de
manera determinista, pues es factible que durante el descenso escalonado
el aumento de entropia del camino mas corto respecto al camino ovtenido
mediante la primera proyeccion aumenta de modo que es capaz de corregirse
en el propio descenso.
I.A