Resumo da origem e no que conssiste o problema do caixeiro-viajante

1) APRESENTAÇÂO
O que é um caixeiro-viajante? Caixeiro-viajante é uma profissão antiga, de uma pessoa que vende produtos fora de onde eles são produzidos. Antigamente, quando não havia a facilidade do transporte entre cidades, os caixeiros-viajantes eram a única forma de transportar produtos entre diferentes regiões fora das grandes cidades. Mercador ambulante que percorre as ruas e estradas a vender objetos manufaturados, tecidos, jóias, etc.
Como surgiu? The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment. The travelling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a recreational puzzle based on finding a Hamiltonian cycle. Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after 1930’s. *E o que é esse ciclo HAMILTONIANO? Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou, seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou circuito hamiltoniano) em G. E, um grafo que possua tal circuito é chamado de grafo hamiltoniano.** The icosian game is a mathematical game invented in 1857 by William Rowan Hamilton. The game's object is finding a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, and the ending point is the same as the starting point. The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph and was subsequently marketed in Europe in many forms.*
No que consiste? O problema do caixeiro-viajante (PCV), ou travelling salesperson problem (TSP), consiste na procura de um circuito que