Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Travelling_salesman_problem> ?p ?o }
- Travelling_salesman_problem abstract "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.TSP is a special case of the travelling purchaser problem and the Vehicle routing problem.In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (perhaps, specifically, exponentially) with the number of cities.The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimise the time spent slewing the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed.".
- Travelling_salesman_problem thumbnail GLPK_solution_of_a_travelling_salesman_problem.svg?width=300.
- Travelling_salesman_problem wikiPageExternalLink TSPLIB95.
- Travelling_salesman_problem wikiPageExternalLink TravelingSalesmanProblem.
- Travelling_salesman_problem wikiPageExternalLink tt1801123.
- Travelling_salesman_problem wikiPageExternalLink TSPLIB95.
- Travelling_salesman_problem wikiPageExternalLink index.html.
- Travelling_salesman_problem wikiPageID "31248".
- Travelling_salesman_problem wikiPageLength "62816".
- Travelling_salesman_problem wikiPageOutDegree "194".
- Travelling_salesman_problem wikiPageRevisionID "681765567".
- Travelling_salesman_problem wikiPageWikiLink 2-opt.
- Travelling_salesman_problem wikiPageWikiLink APX.
- Travelling_salesman_problem wikiPageWikiLink Alpha_processor.
- Travelling_salesman_problem wikiPageWikiLink Analysts_traveling_salesman_theorem.
- Travelling_salesman_problem wikiPageWikiLink Ant_colony_optimization.
- Travelling_salesman_problem wikiPageWikiLink Ant_colony_optimization_algorithms.
- Travelling_salesman_problem wikiPageWikiLink Approximation_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Arc_length.
- Travelling_salesman_problem wikiPageWikiLink Artificial_intelligence.
- Travelling_salesman_problem wikiPageWikiLink Best,_worst_and_average_case.
- Travelling_salesman_problem wikiPageWikiLink Bitonic_tour.
- Travelling_salesman_problem wikiPageWikiLink Bottleneck_traveling_salesman_problem.
- Travelling_salesman_problem wikiPageWikiLink Bounded_convergence_theorem.
- Travelling_salesman_problem wikiPageWikiLink Branch-and-bound.
- Travelling_salesman_problem wikiPageWikiLink Branch_and_bound.
- Travelling_salesman_problem wikiPageWikiLink Branch_and_cut.
- Travelling_salesman_problem wikiPageWikiLink Brian_Kernighan.
- Travelling_salesman_problem wikiPageWikiLink Brute-force_search.
- Travelling_salesman_problem wikiPageWikiLink Brute_force_search.
- Travelling_salesman_problem wikiPageWikiLink Canadian_traveller_problem.
- Travelling_salesman_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Travelling_salesman_problem wikiPageWikiLink Category:Graph_algorithms.
- Travelling_salesman_problem wikiPageWikiLink Category:Hamiltonian_paths_and_cycles.
- Travelling_salesman_problem wikiPageWikiLink Category:NP-complete_problems.
- Travelling_salesman_problem wikiPageWikiLink Category:NP-hard_problems.
- Travelling_salesman_problem wikiPageWikiLink Category:Operations_research.
- Travelling_salesman_problem wikiPageWikiLink Category:Travelling_salesman_problem.
- Travelling_salesman_problem wikiPageWikiLink Chebyshev_distance.
- Travelling_salesman_problem wikiPageWikiLink Chemistry.
- Travelling_salesman_problem wikiPageWikiLink Christofides_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Cognitive_psychology.
- Travelling_salesman_problem wikiPageWikiLink Combinatorial_optimization.
- Travelling_salesman_problem wikiPageWikiLink Complete_graph.
- Travelling_salesman_problem wikiPageWikiLink Complexity_class.
- Travelling_salesman_problem wikiPageWikiLink Computational_complexity_theory.
- Travelling_salesman_problem wikiPageWikiLink Computer_science.
- Travelling_salesman_problem wikiPageWikiLink Concorde_TSP_Solver.
- Travelling_salesman_problem wikiPageWikiLink Cross-entropy_method.
- Travelling_salesman_problem wikiPageWikiLink Cross_entropy_method.
- Travelling_salesman_problem wikiPageWikiLink Cutting-plane_method.
- Travelling_salesman_problem wikiPageWikiLink Cutting_plane.
- Travelling_salesman_problem wikiPageWikiLink Cutting_stock_problem.
- Travelling_salesman_problem wikiPageWikiLink D._R._Fulkerson.
- Travelling_salesman_problem wikiPageWikiLink DEC_Alpha.
- Travelling_salesman_problem wikiPageWikiLink DNA_sequencing.
- Travelling_salesman_problem wikiPageWikiLink Decision_problem.
- Travelling_salesman_problem wikiPageWikiLink Delbert_Ray_Fulkerson.
- Travelling_salesman_problem wikiPageWikiLink Directed_graph.
- Travelling_salesman_problem wikiPageWikiLink Distance_function.
- Travelling_salesman_problem wikiPageWikiLink Distance_matrix.
- Travelling_salesman_problem wikiPageWikiLink Dominated_convergence_theorem.
- Travelling_salesman_problem wikiPageWikiLink Drill.
- Travelling_salesman_problem wikiPageWikiLink Dynamic_programming.
- Travelling_salesman_problem wikiPageWikiLink Edge_(graph_theory).
- Travelling_salesman_problem wikiPageWikiLink Emergence.
- Travelling_salesman_problem wikiPageWikiLink Euclidean_distance.
- Travelling_salesman_problem wikiPageWikiLink Euclidean_minimum_spanning_tree.
- Travelling_salesman_problem wikiPageWikiLink Euclidean_space.
- Travelling_salesman_problem wikiPageWikiLink Eulerian_graph.
- Travelling_salesman_problem wikiPageWikiLink Eulerian_path.
- Travelling_salesman_problem wikiPageWikiLink Eulerian_tour.
- Travelling_salesman_problem wikiPageWikiLink Evolutionary_computation.
- Travelling_salesman_problem wikiPageWikiLink Evolutionary_computing.
- Travelling_salesman_problem wikiPageWikiLink Exponential_time_hypothesis.
- Travelling_salesman_problem wikiPageWikiLink Factorial.
- Travelling_salesman_problem wikiPageWikiLink File:Showing_a_step_of_the_two-opt_heuristic.png.
- Travelling_salesman_problem wikiPageWikiLink Function_problem.
- Travelling_salesman_problem wikiPageWikiLink Genetic_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Geometric_measure_theory.
- Travelling_salesman_problem wikiPageWikiLink George_Dantzig.
- Travelling_salesman_problem wikiPageWikiLink Glossary_of_graph_theory.
- Travelling_salesman_problem wikiPageWikiLink Graph_(mathematics).
- Travelling_salesman_problem wikiPageWikiLink Graph_theory.
- Travelling_salesman_problem wikiPageWikiLink Graph_traversal.
- Travelling_salesman_problem wikiPageWikiLink Greedy_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Gödel_Prize.
- Travelling_salesman_problem wikiPageWikiLink Hamiltonian_cycle.
- Travelling_salesman_problem wikiPageWikiLink Hamiltonian_path.
- Travelling_salesman_problem wikiPageWikiLink Hamiltonian_path_problem.
- Travelling_salesman_problem wikiPageWikiLink Hassler_Whitney.
- Travelling_salesman_problem wikiPageWikiLink Heidelberg_University.
- Travelling_salesman_problem wikiPageWikiLink Held–Karp_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Heuristic.
- Travelling_salesman_problem wikiPageWikiLink Heuristic_(computer_science).
- Travelling_salesman_problem wikiPageWikiLink Heuristic_algorithm.
- Travelling_salesman_problem wikiPageWikiLink Icosian_Game.
- Travelling_salesman_problem wikiPageWikiLink Icosian_game.
- Travelling_salesman_problem wikiPageWikiLink Integer_linear_program.
- Travelling_salesman_problem wikiPageWikiLink Integer_programming.