Editing Travelling salesman problem (section)

===Metric===
<!-- linked from redirect [[Metric TSP]] -->
In the ''metric TSP'', also known as ''delta-TSP'' or Δ-TSP, the intercity distances satisfy the [[triangle inequality]].

A very natural restriction of the TSP is to require that the distances between cities form a [[metric (mathematics)|metric]] to satisfy the [[triangle inequality]]; that is, the direct connection from ''A'' to ''B'' is never farther than the route via intermediate ''C'':
:<math>d_{AB} \le d_{AC} + d_{CB}</math>.

The edges then build a [[metric space|metric]] on the set of vertices. When the cities are viewed as points in the plane, many natural [[distance function]]s are metrics, and so many natural instances of TSP satisfy this constraint.

The following are some examples of metric TSPs for various metrics.
*In the Euclidean TSP (see below), the distance between two cities is the [[Euclidean distance]] between the corresponding points.
*In the rectilinear TSP, the distance between two cities is the sum of the absolute values of the differences of their ''x''- and ''y''-coordinates. This metric is often called the [[Manhattan distance]] or city-block metric.
*In the [[maximum metric]], the distance between two points is the maximum of the absolute values of differences of their ''x''- and ''y''-coordinates.

The last two metrics appear, for example, in routing a machine that drills a given set of holes in a [[printed circuit board]]. The Manhattan metric corresponds to a machine that adjusts first one coordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both coordinates simultaneously, so the time to move to a new point is the slower of the two movements.

In its definition, the TSP does not allow cities to be visited twice, but many applications do not need this constraint. In such cases, a symmetric, non-metric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the inter-city distance <math>d_{AB}</math> is replaced by the [[shortest path]] length between ''A'' and ''B'' in the original graph.