triangle 505

traveling-salesman problem A mathematical prob-

lem based on a real-life situation, called the traveling-

salesman problem, can be stated as follows:

There are a certain number of towns connected

in pairs by highways. The distances of all the

highway routes between towns are specified.

Plan a journey that visits all the towns and

returns to the starting point while minimizing

the total distance traveled.

Alternatively, one can try to minimize the travel costs

in moving from town to town, or the time taken to

complete the entire journey, for example. The desire to

find the efficient routes such as these is an important

practical problem. It can lead to significant financial

savings for transportation companies and other types

of industry.

The traveling-salesman problem is equivalent to

the challenge of finding a least-distance Hamiltonian

circuit in a

GRAPH

—a challenge in the field of

GRAPH

THEORY

.

One method for solving the traveling-salesman

problem is to simply list all the possible routes and see

which one is the most efficient. We can count the num-

ber of routes to be checked as follows:

Suppose there are ntowns in all. Starting in

one town there are n– 1 choices for which

town to visit next. Having reached that town,

there are n– 2 choices for which town to visit

second, and so on, all the way down to one

final choice of one town to visit before return-

ing to start. Noting that, for the purposes of

this problem, traveling a route in the forward

direction is equivalent to traveling that route in

the reverse direction, we thus have a total of

possible routes in all to consider.

(This argument makes use of the

MULTIPLICATION PRIN

-

CIPLE

.) For the very smallest values of n, this count is

small and it is quite feasible to program a computer to

check all the possible routes, but for any reasonably

sized practical problem, this formula yields an extraor-

dinarily large count. For instance, the problem for just

20 towns already yields over 60 quadrillion different

routes for consideration. Even the fastest computers of

today are unable to assist us in finding the most effi-

cient route in any reasonable amount of time.

What is sought is a manageable

ALGORITHM

that

works in a reasonable amount of time. One possible

approach is to use the nearest-neighbor algorithm:

Starting in one town, visit the nearest town

first, then visit the nearest town not already

visited, and so forth. Return to the start town

when no other choice is available.

A computer can easily be programmed to perform this

algorithm quickly. Unfortunately, although easy to per-

form, it is known that this procedure might not neces-

sarily yield the most efficient route overall.

It remains an unsolved problem as to whether there

is a simple procedure that is guaranteed to produce the

optimal route every time it is tried. Most mathematicians

believe that such an algorithm will never be found.

See also

NP COMPLETE

;

OPERATIONS RESEARCH

.

tree See

GRAPH

.

triangle (trigon) A

POLYGON

with three sides is

called a triangle. Precisely, a triangle is the closed geo-

metric figure formed by three line segments (the sides

of the triangle) joining three noncollinear points in the

plane (the vertices of the triangle). Each triangle con-

tains three interior

ANGLE

s.

The

PARALLEL POSTULATE

shows that the three inte-

rior angles of a triangle sum to 180°. This can also be

demonstrated physically with a pencil-turning trick:

Draw a large triangle on a piece of paper and

position a pencil in one corner of the triangle

against one side. Take note of the direction the

tip of the pencil is pointing.

Rotate the pencil through the angle given

by the corner in which it lies. Next slide the

pencil along the side of the triangle to the sec-

ond angle of the triangle. (Notice that this

action of sliding does not alter the direction in

which the pencil is currently pointing.) Rotate

the pencil through this second angle, being

sure to remain in the interior of the triangle.

Now slide the pencil along the second side of

the triangle to position it at the third angle of

the triangle. Rotate the pencil through this third

angle and slide the pencil back to its original

position. Notice that the pencil is now point-

ing in the opposite direction to its start.