12.9 Traveling Salesperson Problem

Finding the cheapest vertex-visiting cycle by brute-force listing of every route, weighed against the faster but fallible nearest-neighbor shortcut.

Contemporary Mathematics, 12.9 Traveling Salesperson Problem

Status

FlagsLoading your progress…

2 exercises

12.9 Exercise 1

A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This…

2.5

12.9 Exercise 3

Suppose you have a complete weighted graph with vertices N, M, O, and P.

Use the formula $\left(n - 1\right) !$ to calculate the number of distinct Hamilton cycles in the graph.
Use the formula $\frac{\left(n - 1\right) !}{2}$ to calculate the greatest number of different weights possible for the Hamilton cycles.
Are all of the distinct Hamilton cycles listed here? How do you know?
Cycle 1: N → M → O → P → N
Cycle 2: N → M → P → O → N
…

2.5