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

Karteikarten

D1 Networks

Maisie Carroll Maths A level Englisch 21 Karten

Dijkstras Algorithm label?

Karten in diesem Stapel (21)

  1. 1MINIMUM SPANNING TREES?- smallest tree to connect all nodes
    - Kruskals
    - Prims
    - no. of arcs for n nodes = n - 1
  2. 2Kruskals Alogrithm?- list all arcs smallest -> largest in weight
    - choose arc w/ smallest weight
    - from remaining arcs, choose the smallest, as long as it DOESN'T FORM CYCLE W/ ARCS ALREADY CHOSEN
    - repeat step 3 until all nodes in/directly connected
    * cross out arcs not used, tick ones used
    * add up total weight if not given
    * if they say you CANNOT use an arc, say 'remove (arc), add in (other arc). Then weight will go up/down by..'
    * 'New MST =..'
  3. 3Prims Alogrithm- select any node. Call it initial tree
    - select shortest arc connecting the tree to a new node
    - incorporate that arc and node into the tree
    - repeat 2 + 3 until all nodes connected
    * remember that the shortest arc may not be connected to the node you just joined!
  4. 4Prims on a matrix?- choose start vertex, LABEL THE COLUMN corresponding with the vertex (1) and DELETE THE ROW
    - look in all columns numbered so far, circle the smallest undeleted number then delete the rest of the ROW
    - label column corresponding to this vertex w/ next available label then delete the row
    - repeat 2 + 3 until all rows deleted
    - if asked, draw MST w/ all the circled points
  5. 5SHORTEST ROUTE?- Dijkstras
    - sometimes ask for shortest trail
  6. 6Dijkstras Algorithm label?Dijkstras Algorithm label?
  7. 7Dijkstras Algorithm?- give start node permanent label of 0 and order 1
    - give every node connected to the start node a temporary label by recording it's distance from the START
    - find the smallest temporary label of WHOLE NETWORK and make this label permanent
    - update temporary labels for any node that can be reached DIRECTLY from most recent permanent node if distance is less than temp. label
    - repeat 3 + 4 until the destination node has been given a permanent label
    -Go backwards through the network, retracing the path of shortest length from the
    destination node to the start node
  8. 8Algebraic Network Questions?- still use Dijkstras
    -Q will usually give algebraic function a limit so that you know it'll be bigger/smaller than another node/arc
    - can use simultaneous equations if it comes up
    LOOK IN BOOKLET FOR EXAMPLES
  9. 9What are Route Inspection Problems used for?to find the shortest closed trail
  10. 10What if the graph is Eulerian?every node is even, so total weight of route is total weight of network
  11. 11What if the graph is Semi - Eulerian?(exactly 2 odd nodes)
    - add up whole network
    - add up shortest trail from first odd node to second
    - add together
  12. 12What do you use for a graph that has more than one pair of odd nodes?Chinese Postman
  13. 13Explain this algorithm?1) list odd ordered nodes
    2) list possible pairings and their weights when getting from one to other (e.g. AB + CD -> 4 + 5 = 9)
    3) choose smallest weight
    4) shortest closed trail = total weight of tree + smallest weight you just picked
  14. 14Any extra questions they can ask?LOOK IN BOOKLET
  15. 15What are Travelling Salesperson problems?finding shortest cycle which lists every node exactly once and returns to the start
  16. 16What are these cycles called?Hamiltonian Cycles
  17. 17How do you find the Upper Bound?Nearest Neighbour
  18. 18Describe Nearest Neighbour?- choose any node
    - from nodes not already selected, find nearest node to last
    - repeat until all nodes selected
    - join last node to first node directly if possible (or if not by the shortest route)
  19. 19What are the problems with Nearest Neighbour?- greedy algorithm: best short term solution but poor choices for last few arcs
    - sometimes it gets stuck if graph isn't complete
  20. 20How do you find the Lower Bound?- choose a node as 'special node' and delete it + all arcs connected to it
    - find MST for remaining arcs/nodes
    - add in the two smallest arcs connected to the 'special node'
  21. 21Is there a Solution?No, not exactly, the optimal solution will be between the LB and UB (put as <= not <)

Informationen

Beschreibung
A level Maths (D1) Karteikarten am D1 Networks, erstellt von Maisie Carroll am 15/03/2017.
Erstellt von
Maisie Carroll
Aufrufe
1
Bewertung

Mehr zu Graph and Network Algorithms

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?