2, Unit 5 - Network Optimization
Need summary here, like that provided for Course 2 Units 1-4.
Ideas from Course 2, Unit 5
- Optimization: The process of looking for the best solution, whether this is a shortest path, a minimal spanning tree, or a minimal circuit.
- Tree: A vertex edge graph which has no circuits. (See Course
1 Unit 4 for introductory work with graph models.) For example:
- Minimal spanning tree: A subset of a vertex edge graph which
connects all vertices, without making any circuits and by minimizing
total edge lengths. (Lengths might represent actual distances, cost,
or time, etc.) There are algorithms for producing a minimal
spanning tree. (See page 323 Activity 7 for KruskalÍs algorithm,
and page 324 Activity 9 for the nearest-neighbor algorithm.) For
- Traveling salesperson problem: A particular problem represented
by a vertex edge graph, in which the goal is to create a circuit from
the start point to every vertex, without repeating any vertex, minimizing
the total edge lengths. There is no algorithm for producing an
optimal solution. Brute force methods are impractical if more than
a few vertices are involved.
- Best-edge algorithm: One best-edge algorithm is to start with
just vertices then add the shortest edge that will not create a circuit,
and repeat this process until it is not possible to add an edge without
creating a circuit. A new edge added does not have to be connected
to previously-added edges. The result is a minimal spanning tree.
- Brute force method: This is another algorithm for solving
optimizing problems. Basically, all solutions are found and then the
best is chosen. Obviously this is not practical in many situations.
- Hamiltonian circuit: As with other circuits, the goal is to
start at one vertex, and return to the same vertex, without repeating
an edge, but with the additional condition that each vertex can
only be visited once.
- Shortest path lengths: A path starts at one vertex, visits
all other vertices without repeating an edge, and ends at another vertex.
The shortest path has the shortest total edge lengths. This is different
from a minimal spanning tree in that circuits may be included.