el problema del agente viajero consiste en que dada un conjunto de ciudades un vendedor debe visitar cada una de ellas y regresar a su punto de partida con un recorrido mínimo.
yo explicare este problema :
la formula matemática de de el problema del agente viajero es P = {c0,c2,...,cn − 1} tal que
![d_P=\sum_{i=0}^{N-1}{d[c_i,c_{i+1mod(N)}]}](http://upload.wikimedia.org/math/1/6/5/165c5afad80aa59913b41c3d33760566.png)
donde P esta dada por una permutacion una permutacion viene siendo un conjunto finito de todos sus elementos diferentes.
aun no se halla un algoritmo para solucionar este problema pero el mas óptimo para utilizar es el método de la fuerza bruta
n ciudades = cantidad finita de rutas
método de la fuerza bruta
esto significa que al tener "n" ciudades sabemos que tenemos (n-1)! el signo de interrogacion lo referimos como el
factorial osea que rutas = (5-1)! esto quiere desir que hay 24 rutas al intentar hacer todos los caminos posibles estamos dando lugar a la solucion del problema por el método de fuerza bruta.
en definición el método de fuerza bruta consiste en dar todos los posibles rutas y luego después de ya tener todas las posibles rutas checar cual es la mas eficaz y la que ocupo menos pero esto incrementa muy fácil mente aquí les dejare una tabla de el tiempo que tarda este método;
tiempo ciudades
1 segundo para cada combinacion de ciudades hasta llegar ala décima ciudad
3 segundos para 10 ciudades
30 segundos para 11 ciudades
no determinado apartir de las 20 ciudades no se a podido determinar el tiempo por este método
aquí les dejare las ligas de algunos algoritmos que se le han aplicado a este problema sin llegar a un resultado solo se han logrado aproximaciones
heuristica
red neuronal
evolutiva
porque este problema es np completo y que es np completo
este problema es np porque este problema existen algoritmos para su solución pero no existe aun un algoritmo que defina el tiempo de este problema en un tiempo polinomial.
para entender esto yo visite YouTube para ver lo que pedía el problema.
complejidad computacional
en la complejidad existen diferentes tipos de problemas por ejemplo
de optimizacion; son aquellos que se busca minimizar o maximizar el valor de una solución algo parecido a la eficacia que lo emos estado viendo mediante grafías de el tiempo en que tardan en correr los programas.
de decisión;son aquellos que buscan una decisión "si" o "no".
algoritmos no deterministas
es un algoritmo que es imposible de realizar en la realidad esto quiere desir que es solo como una teoria
problemas np
los problemas np son algoritmos que no han sido resueltos en un tiempo polinomial
conclucion
este problema se me hizo muy interensante a que por años an intentado buscar un algoritmo para poder resolver este problema ya que si tiene una solucion solo que no han podido definir un tiempo polinomial ya que al incrementarse las ciudades a donde ira el vendedor el tiempo que tarda este programa en ejecutarlo es demaciado y vi que existian algunos algoritmos pero solo se acercavan y al pasar de las 200 ciudades el tiempo k tardaba en correr el programa era demaciado que no se podia calcular.
Sí existen algoritmos para el TSP, simplemente no son polinomiales. Faltó discutir la reducción de otro problema NP-completo al TSP. Otrografía no muy buena. La clase NP no se define de la manera que tí dices sino como la clase de aquellos problemas que se puede decidir en tiempo polinomial con una máquina turing no determinista. Faltan las referencias. 5 puntos. Te recomiendo hacer entradas por puntos extra si piensas pasar la materia.
ResponderEliminar