Ch. 6 Traveling Salesman Problems

Front 1

approximate algorithm

Back 1

describes any algorithm that produces solutions that are, most of the time, reasonably close to the optimal solution.

Front 2

complete weighted graph

Back 2

a graph whose edges have numbers attached to them where the numbers represent a variable

Front 3

brute-force algorithm

Back 3

1) make a list of all possible Hamilton circuits of graph
2) calculate total weight for each circuit
3)choose optimal circuit
OPTIMAL not efficient

Front 4

cheapest-link algorithm

Back 4

1) pick cheapest edge available (if more than one, pick at random) and mark it
2)pick next cheapest edge and mark
3)continue picking and marking cheapest edge as long as it doest
a) close to form a circuit
b)create 3 edges out of a singe vertex
4) connect last two remaining vertices to close circuit
EFFICIENT not optimal

Front 5

complete graph

Back 5

a graph where every pair of vertices are joined by an edge

Front 6

efficient algorithm

Back 6

an algorithm for which the amount of computational effort required to implement the algorithm grows in some reasonable proportion with the size of the input to the problem

Front 7

factorial

Back 7

how many different ways there are of rearranging something
# Hamilton Circuits = (N-1)! in a complete graph KN

Front 8

hamilton circuit

Back 8

circuit that visits each vertex of a graph once and only once, and starts and ends on the same vertex
NOTE: a hamilton circuit automatically has a hamilton path

Front 9

hamilton path

Back 9

path that visits each vertex of a graph once and only once
NOTE: you can have a hamilton path without a hamilton circuit

Front 10

inefficient algorithm

Back 10

an algorithm for which the number of steps needed to carry it out grows disproportionately with the size of the problem

Front 11

nearest-neighbor algorithm

Back 11

1) start at designated starting vertex, or if not designated, pick
2) from starting vertex, go to nearest neighbor (vertex which corresponding edge is smallest weight)
3) from each vertex, go to nearest neighbor, choosing only those unvisited vertices (more than one nearest neighbor- pick one and continue until all vertices visited)
4) from last vertex, return to starting vertex
EFFICIENT

Front 12

optimal algorithm

Back 12

an algorithm that when correctly implemented, is guaranteed to produce an optimal solution

Front 13

relative error

Back 13

a relative measure of how far a given Hamilton circuit is from the optimal circuit
given by E= (W - Opt =)/Opt where W is weight of any given circuit and Opt is the weight of the optimal circuit.

Front 14

repetitive nearest-neighbor algorithm

Back 14

1) let X be any vertex. Find nearest neighbor circuit using X as starting vertex and calculate total cost of circuit
2) repeat process w/each other vertex of graph as start
3) of nearest neighbor circuits, keep the best one. If there is a designated starting vertex, rewrite circuit using that vertex as reference pt.
EFFICIENT

Front 15

traveling salesman problem

Back 15

finding the best, cheapest route of visiting a number of cities

Front 16

weighted graph

Back 16

any graph whose edges have numbers attached to them

Front 17

weight

Back 17

numbers attached to edges

Front 18

Finding edges in KN

Back 18

N(N-1)/2edges

Front 19

# of Hamilton circuits

Back 19

(N-1)!