| Property |
Value |
| dbo:abstract
|
- El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resover planteamientos concretos del problema desde cien hasta miles de ciudades. El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y la fabricación de circuitos electrónicos. Un poco modificado, aparece como subproblema en muchos campos como la secuenciación de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem). En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dada una longitud “L”, el objetivo es decidir qué grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades. (es)
- El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resover planteamientos concretos del problema desde cien hasta miles de ciudades. El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y la fabricación de circuitos electrónicos. Un poco modificado, aparece como subproblema en muchos campos como la secuenciación de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem). En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dada una longitud “L”, el objetivo es decidir qué grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades. (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:archiveurl
|
- https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|archivedate=6 de febrero de 2005 (es)
- https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|archivedate=6 de febrero de 2005 (es)
|
| prop-es:author1Link
|
- David S. Johnson (es)
- Thomas H. Cormen (es)
- George Dantzig (es)
- Michael R. Garey (es)
- Eugene Lawler (es)
- Michael Held (es)
- William J. Cook (es)
- David S. Johnson (es)
- Thomas H. Cormen (es)
- George Dantzig (es)
- Michael R. Garey (es)
- Eugene Lawler (es)
- Michael Held (es)
- William J. Cook (es)
|
| prop-es:author2Link
|
- David S. Johnson (es)
- D. R. Fulkerson (es)
- Richard Karp (es)
- Charles E. Leiserson (es)
- Marek Karpinski (es)
- Heikki Mannila (es)
- Jan Karel Lenstra (es)
- David S. Johnson (es)
- D. R. Fulkerson (es)
- Richard Karp (es)
- Charles E. Leiserson (es)
- Marek Karpinski (es)
- Heikki Mannila (es)
- Jan Karel Lenstra (es)
|
| prop-es:author3Link
|
- Ronald L. Rivest (es)
- Selmer M. Johnson (es)
- Ronald L. Rivest (es)
- Selmer M. Johnson (es)
|
| prop-es:author4Link
|
- Clifford Stein (es)
- William J. Cook (es)
- Clifford Stein (es)
- William J. Cook (es)
|
| prop-es:authorLink
|
- Christos Papadimitriou (es)
- Sanjeev Arora (es)
- Christos Papadimitriou (es)
- Sanjeev Arora (es)
|
| prop-es:authorlink
|
- Leonard Adleman (es)
- Sanjeev Arora (es)
- Joseph S. B. Mitchell (es)
- William J. Cook (es)
- Leonard Adleman (es)
- Sanjeev Arora (es)
- Joseph S. B. Mitchell (es)
- William J. Cook (es)
|
| prop-es:bibcode
|
- 1989 (xsd:integer)
- 1994 (xsd:integer)
|
| prop-es:contribution
|
- 8 (xsd:integer)
- 352 (xsd:integer)
- A2.3: ND22–24 (es)
- Combinatorial Processes and Dynamic Programming (es)
- Exact Algorithms for NP-Hard Problems: A Survey (es)
- Long tours and short superstrings' (es)
- Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs (es)
- The Traveling Salesman Problem: A Case Study in Local Optimization (es)
- Approximating geometrical graphs via 'spanners' and 'banyans' (es)
|
| prop-es:doi
|
- 101007 (xsd:integer)
- 101016 (xsd:integer)
- 101126 (xsd:integer)
- 101137 (xsd:integer)
- 101145 (xsd:integer)
- 101287 (xsd:integer)
|
| prop-es:edition
| |
| prop-es:editor
|
- Bellman, R., Hall, M., Jr. (es)
- Bellman, R., Hall, M., Jr. (es)
|
| prop-es:editor1First
|
- E. H. L. (es)
- E. H. L. (es)
|
| prop-es:editor1Last
| |
| prop-es:editor2First
| |
| prop-es:editor2Last
|
- Lenstra (es)
- Lenstra (es)
|
| prop-es:editor2Link
|
- Jan Karel Lenstra (es)
- Jan Karel Lenstra (es)
|
| prop-es:fechaacceso
| |
| prop-es:first
|
- W. (es)
- S. R. (es)
- C. E. (es)
- Daniel (es)
- Gilbert (es)
- A. (es)
- L. A. (es)
- M. (es)
- Marcos (es)
- A. I. (es)
- G. B. (es)
- R. (es)
- A. P. (es)
- L. (es)
- D. (es)
- William (es)
- C. (es)
- Chris (es)
- Leonard (es)
- H. (es)
- D. S. (es)
- Stéphanie (es)
- Marek (es)
- Piotr (es)
- V. (es)
- G. (es)
- Richard E. (es)
- N. (es)
- P. (es)
- S. (es)
- M. R. (es)
- D. E. (es)
- J. K. (es)
- T. (es)
- R. L. (es)
- R. M. (es)
- T. H. (es)
- Daniel J. (es)
- G.J. (es)
- J. N. (es)
- C. H. (es)
- E. L. (es)
- D. B. (es)
- S. M. (es)
- Christos H. (es)
- W. J. (es)
- D. L. (es)
- A. H. G. (es)
- J. S. B. (es)
- Philip M., II (es)
- Sanjeev (es)
- W. (es)
- S. R. (es)
- C. E. (es)
- Daniel (es)
- Gilbert (es)
- A. (es)
- L. A. (es)
- M. (es)
- Marcos (es)
- A. I. (es)
- G. B. (es)
- R. (es)
- A. P. (es)
- L. (es)
- D. (es)
- William (es)
- C. (es)
- Chris (es)
- Leonard (es)
- H. (es)
- D. S. (es)
- Stéphanie (es)
- Marek (es)
- Piotr (es)
- V. (es)
- G. (es)
- Richard E. (es)
- N. (es)
- P. (es)
- S. (es)
- M. R. (es)
- D. E. (es)
- J. K. (es)
- T. (es)
- R. L. (es)
- R. M. (es)
- T. H. (es)
- Daniel J. (es)
- G.J. (es)
- J. N. (es)
- C. H. (es)
- E. L. (es)
- D. B. (es)
- S. M. (es)
- Christos H. (es)
- W. J. (es)
- D. L. (es)
- A. H. G. (es)
- J. S. B. (es)
- Philip M., II (es)
- Sanjeev (es)
|
| prop-es:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
- 898716055 (xsd:integer)
|
| prop-es:issue
|
- 1 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 5 (xsd:integer)
- 5187 (xsd:integer)
|
| prop-es:journal
|
- dbpedia-es:Journal_of_the_ACM
- Theoretical Computer Science (es)
- Journal of the ACM (es)
- SIAM Journal on Computing (es)
- Discrete Applied Mathematics (es)
- Science (es)
- J. Assoc. Comput. Mach. (es)
- INFORMS Journal on Computing (es)
- Information Processing Letters (es)
- Math. Oper. Res. (es)
- Operations Research (es)
- Perception & Psychophysics (es)
- Psychological Research (es)
- Reading: Addison-Wesley (es)
- Upravlyaemye Sistemy (es)
- Technical Report C-1987–28, Department of Computer Science, University of Helsinki (es)
- Journal of the Society for Industrial and Applied Mathematics (es)
|
| prop-es:jstor
| |
| prop-es:last
|
- Rubinstein (es)
- Rao (es)
- Lewis (es)
- Shafrir (es)
- Goldberg (es)
- Lawler (es)
- Smith (es)
- Cook (es)
- Mitchell (es)
- Ormerod (es)
- Rosenkrantz (es)
- Stein (es)
- Applegate (es)
- Berman (es)
- Yeo (es)
- Bixby (es)
- Johnson (es)
- Arora (es)
- Vickers (es)
- Dantzig (es)
- Medvedev (es)
- Garey (es)
- Lee (es)
- Kaplan (es)
- Park (es)
- Lenstra (es)
- Babin (es)
- Stearns (es)
- Held (es)
- Cormen (es)
- Espinoza (es)
- Karpinski (es)
- Karp (es)
- MacGregor (es)
- Bellman (es)
- Leiserson (es)
- Papadimitriou (es)
- Rivest (es)
- Serdyukov (es)
- Chvátal (es)
- Fulkerson (es)
- Adleman (es)
- Butavicius (es)
- Christofides (es)
- Deneault (es)
- Goycoolea (es)
- Gutin (es)
- Hassin (es)
- Kosaraju (es)
- Laportey (es)
- Lewenstein (es)
- Mannila (es)
- McGeoch (es)
- Orponen (es)
- Punnen (es)
- Rinnooy Kan (es)
- Shmoys (es)
- Sviridenko (es)
- Walshaw (es)
- Woeginger (es)
- Yannakakis (es)
- Zverovich (es)
- Rubinstein (es)
- Rao (es)
- Lewis (es)
- Shafrir (es)
- Goldberg (es)
- Lawler (es)
- Smith (es)
- Cook (es)
- Mitchell (es)
- Ormerod (es)
- Rosenkrantz (es)
- Stein (es)
- Applegate (es)
- Berman (es)
- Yeo (es)
- Bixby (es)
- Johnson (es)
- Arora (es)
- Vickers (es)
- Dantzig (es)
- Medvedev (es)
- Garey (es)
- Lee (es)
- Kaplan (es)
- Park (es)
- Lenstra (es)
- Babin (es)
- Stearns (es)
- Held (es)
- Cormen (es)
- Espinoza (es)
- Karpinski (es)
- Karp (es)
- MacGregor (es)
- Bellman (es)
- Leiserson (es)
- Papadimitriou (es)
- Rivest (es)
- Serdyukov (es)
- Chvátal (es)
- Fulkerson (es)
- Adleman (es)
- Butavicius (es)
- Christofides (es)
- Deneault (es)
- Goycoolea (es)
- Gutin (es)
- Hassin (es)
- Kosaraju (es)
- Laportey (es)
- Lewenstein (es)
- Mannila (es)
- McGeoch (es)
- Orponen (es)
- Punnen (es)
- Rinnooy Kan (es)
- Shmoys (es)
- Sviridenko (es)
- Walshaw (es)
- Woeginger (es)
- Yannakakis (es)
- Zverovich (es)
|
| prop-es:location
|
- Montreal (es)
- New York (es)
- Montreal (es)
- New York (es)
|
| prop-es:mr
|
- 455550 (xsd:integer)
- 1668147 (xsd:integer)
|
| prop-es:pages
|
- 1 (xsd:integer)
- 34 (xsd:integer)
- 56 (xsd:integer)
- 61 (xsd:integer)
- 80 (xsd:integer)
- 81 (xsd:integer)
- 166 (xsd:integer)
- 181 (xsd:integer)
- 185 (xsd:integer)
- 196 (xsd:integer)
- 211 (xsd:integer)
- 215 (xsd:integer)
- 217 (xsd:integer)
- 237 (xsd:integer)
- 356 (xsd:integer)
- 393 (xsd:integer)
- 527 (xsd:integer)
- 540 (xsd:integer)
- 563 (xsd:integer)
- 641 (xsd:integer)
- 753 (xsd:integer)
- 1021 (xsd:integer)
- 1027 (xsd:integer)
- 1298 (xsd:integer)
|
| prop-es:pmid
|
- 7973651 (xsd:integer)
- 11505612 (xsd:integer)
|
| prop-es:publisher
|
- dbpedia-es:Princeton_University_Press
- John Wiley & Sons (es)
- American Mathematical Society (es)
- IEEE Computer Society (es)
- Springer (es)
- Addison-Wesley (es)
- W.H. Freeman (es)
- MIT Press and McGraw-Hill (es)
- John Wiley and Sons Ltd (es)
- CMS Press (es)
- Group for Research in Decision Analysis (es)
- Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (es)
|
| prop-es:series
|
- Cahiers du GERAD (es)
- Technical Report 388 (es)
- Cahiers du GERAD (es)
- Technical Report 388 (es)
|
| prop-es:title
|
- dbpedia-es:Introducción_a_los_algoritmos
- dbpedia-es:Symposium_on_Theory_of_Computing
- Computers and Intractability: A Guide to the Theory of NP-Completeness (es)
- The Euclidean traveling salesman problem is NP-complete (es)
- A Multilevel Approach to the Travelling Salesman Problem (es)
- Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci (es)
- Solution of a large-scale traveling salesman problem (es)
- Genetic Algorithms in Search, Optimization & Machine Learning (es)
- Human performance on the traveling salesman problem (es)
- The traveling salesman problem with distances one and two (es)
- A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem (es)
- Better approximations for max TSP (es)
- Worst-case analysis of a new heuristic for the travelling salesman problem (es)
- Local Search in Combinatorial Optimisation (es)
- The Traveling Salesman Problem (es)
- The Traveling Salesman Problem and Its Variations (es)
- On approximation preserving reductions: Complete problems and robust measures' (es)
- A Dynamic Programming Approach to Sequencing Problems (es)
- An algorithm with an estimate for the traveling salesman problem of the maximum' (es)
- In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation (es)
- Dynamic Programming Treatment of the Travelling Salesman Problem (es)
- Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570 (es)
- In Proc. 44th IEEE Symp. on Foundations of Comput. Sci (es)
- An Analysis of Several Heuristics for the Traveling Salesman Problem (es)
- The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (es)
- Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (es)
- Human performance on visually presented traveling salesman problems (es)
- Computing with domino-parity inequalities for the TSP (es)
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems (es)
- Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, (es)
- Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP (es)
|
| prop-es:url
|
- https://archive.org/details/computersintract0000gare/page/211
- https://archive.org/details/travelingsalesma00lawl
- http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|doi=10.3758/BF03213088|fechaacceso=17 de diciembre de 2013 (es)
- http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9953|title=Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem (es)
- http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arora-tsp.pdf|title=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems (es)
- http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|title=Molecular Computation of Solutions To Combinatorial Problems (es)
- http://citeseer.ist.psu.edu/622594.html|title=Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems (es)
|
| prop-es:urlarchivo
|
- https://web.archive.org/web/20091229053516/http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|fechaarchivo=29 de diciembre de 2009 (es)
- https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|fechaarchivo=6 de febrero de 2005 (es)
- https://web.archive.org/web/20091229053516/http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|fechaarchivo=29 de diciembre de 2009 (es)
- https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|fechaarchivo=6 de febrero de 2005 (es)
|
| prop-es:volume
|
- 2 (xsd:integer)
- 4 (xsd:integer)
- 6 (xsd:integer)
- 9 (xsd:integer)
- 10 (xsd:integer)
- 18 (xsd:integer)
- 19 (xsd:integer)
- 25 (xsd:integer)
- 28 (xsd:integer)
- 45 (xsd:integer)
- 58 (xsd:integer)
- 65 (xsd:integer)
- 75 (xsd:integer)
- 117 (xsd:integer)
- 266 (xsd:integer)
- G-2005-02 (es)
|
| prop-es:year
|
- 1954 (xsd:integer)
- 1960 (xsd:integer)
- 1962 (xsd:integer)
- 1976 (xsd:integer)
- 1977 (xsd:integer)
- 1979 (xsd:integer)
- 1984 (xsd:integer)
- 1985 (xsd:integer)
- 1987 (xsd:integer)
- 1989 (xsd:integer)
- 1993 (xsd:integer)
- 1994 (xsd:integer)
- 1996 (xsd:integer)
- 1997 (xsd:integer)
- 1998 (xsd:integer)
- 1999 (xsd:integer)
- 2000 (xsd:integer)
- 2001 (xsd:integer)
- 2002 (xsd:integer)
- 2003 (xsd:integer)
- 2004 (xsd:integer)
- 2005 (xsd:integer)
- 2006 (xsd:integer)
- 2007 (xsd:integer)
- 2011 (xsd:integer)
|
| dct:subject
| |
| rdfs:comment
|
- El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. (es)
- El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. (es)
|
| rdfs:label
|
- Problema del viajante (es)
- Problema del viajante (es)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
