Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Karteikarten

Travelling Salesman Problem

Doc Boff Further Maths AS level Englisch 13 Karten

Karten in diesem Stapel (13)

  1. 1For a complete graph with n vertices, how do we work out the number of of Hamiltonian cycles?1/2(n-1)!
  2. 2How do you conduct the nearest neighbor algorithm? (on complete graph)1. Chose vertex to start
    2. Go to next edge with the lowest weight and repeat until all vertices have been included.
    3. Return directly to the starting vertex.
  3. 3What changes for the nearest neighbor algorithm on a incomplete graph?Draw in edges to make it complete and then label then with the minimum weight connecting them.
    Make sure not change the route into the actual route (e.g. if you added in A to D, the A to D may be A to B to C to D)
  4. 4If we have a complete adjacency matrix, how would we conduct the nearest neighbor algorithm?1. Circle starting vertex and then cross out it's row.
    2. Choose the minimum value from directly under it
    3. Circle the next vertex and cross out its row. Circle the minimum value from directly under it.
    4. Repeat, and make into a cycle by choosing the value in line with both the last vertex and the first.
    5. Add up all values and note down the order of cycle
  5. 5If we have a incomplete adjacency matrix, how would we conduct the nearest neighbor algorithm?1. Complete the adjacency matrix according to the graph
    2. Conduct nearest neighbor algorithm for complete adjacency matrix (if there is no direct route then find minimum value of journey)
    3. Note down actual route
  6. 6What makes a value an upper bound?If it's a Hamiltonian cycle.
  7. 7The best upper bound is the value which is the....Lowest
  8. 8The best lower bound is the value which is the.....Highest
  9. 9How do we conduct the lower bound algorithm?1. Delete a vertex and all the edges associated with it
    2. Use Prim's or Kruskals's algorithm to find minimum spanning tree for the remaining n-1 vertices
    3. Finally add the two shortest edges from the deleted edges to the answer
  10. 10Why might a lower bound not be an answer?Because it's not a Hamiltonian cycle
  11. 11How would we find a lower bound using an adjacency matrix?1. Remove column and row for a vertex
    2. Conduct prim's algorithm (remember you can choose a minimum under any circled vertex)
    3. Draw graph of this
    4. Find the shortest length 2 length and add onto answer
  12. 12How do we express an upper and lower bound together?As an inequality
  13. 13When finding Hamiltonian cycles, you shouyld remember to start them all.....At the same point (to avoid duplication)
    Also know that ABCDA and ADCBA are the same, just backwards.

Informationen

Beschreibung
Travelling Salesman Problem
Erstellt von
Doc Boff · Nov 2018
Aktualisiert
7 Dez 2018
Aufrufe
4
Bewertung

Mehr zu Graph Paths, Cycles and Route Problems

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?