AJENTE VIAJERO-FUERZA BRUTA
Páginas: 2 (411 palabras)
Publicado: 23 de julio de 2015
ALGORITMO DE PROBLEMAS DEL AGENTE VIAJERO (PAV) – FUERZA BRUTA
1. HISTORIA:
El problema del agente viajero fue definido en los años 1800 por el matemático irlandés W.R. Hamilton y ThomasKirkman. El juego Icosan(dar el recorrido de Hamilton por las aristas de un dodecaedro para visitar una y solo una vez cada vértice y que el de llegada coincida con el de partida) de Hamilton fue un puzlesrecreativo basado en encontrar un ciclo de Hamilton. Luego de esto el problema se volvió más notorio cuando George Dantzik y Ray Fulkerson publicaron una solución del del problema del agente viajero en49 ciudades de estados unidos. Y también M. Held and R.M Karp quien introdujo la introducción de heurísticas (son métodos obtienen buenas soluciones en tiempos de computo muy cortos) basadas enprogramación dinámica.
2. CONCEPTO DEL AGENTE VIAJERO- FUERZA BRUTA:
Pues bien, el problema del agente viajero (PAV) o bien traveling salesman problem (TSP) como se conoce a nivel mundial. Es unproblema que se estudia en investigación de operaciones y de manera muy especial en la optimización combinatoria. Se utiliza como base para resolver una gran cantidad de problemas que se presentan en la vidareal y también lo utiliza otra área como la teoría de la complejidad computacional para validar algoritmos que se van descubriendo día con día. Otras de las áreas en las que se puede observar elproblema del agente viajero es la teoría de gráficas.
Primeramente los algoritmos de fuerza bruta son capaces de encontrar la solución a cualquier problema por complicado que sea. Su fundamento es muysiempre, probar todas las posibles combinaciones, recorrer todos los caminos hasta dar con la situación que es igual que la solución.(“Graph Theory” by Tero Harju,1994-2012)
El método de la fuerzabruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles. Considerando la siguiente red simétrica, los caminos posibles se reduce a la...
ALGORITMO DE PROBLEMAS DEL AGENTE VIAJERO (PAV) – FUERZA BRUTA
1. HISTORIA:
El problema del agente viajero fue definido en los años 1800 por el matemático irlandés W.R. Hamilton y ThomasKirkman. El juego Icosan(dar el recorrido de Hamilton por las aristas de un dodecaedro para visitar una y solo una vez cada vértice y que el de llegada coincida con el de partida) de Hamilton fue un puzlesrecreativo basado en encontrar un ciclo de Hamilton. Luego de esto el problema se volvió más notorio cuando George Dantzik y Ray Fulkerson publicaron una solución del del problema del agente viajero en49 ciudades de estados unidos. Y también M. Held and R.M Karp quien introdujo la introducción de heurísticas (son métodos obtienen buenas soluciones en tiempos de computo muy cortos) basadas enprogramación dinámica.
2. CONCEPTO DEL AGENTE VIAJERO- FUERZA BRUTA:
Pues bien, el problema del agente viajero (PAV) o bien traveling salesman problem (TSP) como se conoce a nivel mundial. Es unproblema que se estudia en investigación de operaciones y de manera muy especial en la optimización combinatoria. Se utiliza como base para resolver una gran cantidad de problemas que se presentan en la vidareal y también lo utiliza otra área como la teoría de la complejidad computacional para validar algoritmos que se van descubriendo día con día. Otras de las áreas en las que se puede observar elproblema del agente viajero es la teoría de gráficas.
Primeramente los algoritmos de fuerza bruta son capaces de encontrar la solución a cualquier problema por complicado que sea. Su fundamento es muysiempre, probar todas las posibles combinaciones, recorrer todos los caminos hasta dar con la situación que es igual que la solución.(“Graph Theory” by Tero Harju,1994-2012)
El método de la fuerzabruta no implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles. Considerando la siguiente red simétrica, los caminos posibles se reduce a la...
Leer documento completo
Regístrate para leer el documento completo.