Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/19

Click to flip

19 Cards in this Set

  • Front
  • Back
approximate algorithm
describes any algorithm that produces solutions that are, most of the time, reasonably close to the optimal solution.
complete weighted graph
a graph whose edges have numbers attached to them where the numbers represent a variable
brute-force algorithm
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
cheapest-link algorithm
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
complete graph
a graph where every pair of vertices are joined by an edge
efficient algorithm
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
factorial
how many different ways there are of rearranging something
# Hamilton Circuits = (N-1)! in a complete graph KN
hamilton circuit
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
hamilton path
path that visits each vertex of a graph once and only once
NOTE: you can have a hamilton path without a hamilton circuit
inefficient algorithm
an algorithm for which the number of steps needed to carry it out grows disproportionately with the size of the problem
nearest-neighbor algorithm
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
optimal algorithm
an algorithm that when correctly implemented, is guaranteed to produce an optimal solution
relative error
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.
repetitive nearest-neighbor algorithm
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
traveling salesman problem
finding the best, cheapest route of visiting a number of cities
weighted graph
any graph whose edges have numbers attached to them
weight
numbers attached to edges
Finding edges in KN
N(N-1)/2edges
# of Hamilton circuits
(N-1)!