Mapa mental
D1 Maths

Mind map: D1 maths
Contenido del mapa
D1 Maths
Minimum Connectors
- Kruskal
- Pick shortest edge
- Pick next shortest edge (no cycle)
- Repeat until all vertices = chosen
- Pick next shortest edge (no cycle)
- Pick shortest edge
- Prim
- Select vertex
- Select shortest edge connected to that vertex
- Select shortest edge connected to any vertex already connected
- Repeat until all vertices = connected
- Select shortest edge connected to any vertex already connected
- Select shortest edge connected to that vertex
- Matrix
- Choose column, label it 1, and cross out its row
- Choose smallest entry in that column and circle it
- Cross out this row and label it 2
- Continue until all vertices = selected
- Cross out this row and label it 2
- Choose smallest entry in that column and circle it
- Choose column, label it 1, and cross out its row
- Select vertex
- Kruskal
Travelling Salesperson Problem
- Lower bound algorithm
- Total of 2 smallest weights of arcs to first node
- Ignore first node and all arcs joined to it
- Find the minimum connector
- Sum of minimum connector and 2 smallest weights = lower bound
- Repeat for all vertices and choose the highest
- Sum of minimum connector and 2 smallest weights = lower bound
- Find the minimum connector
- Ignore first node and all arcs joined to it
- Total of 2 smallest weights of arcs to first node
- n nodes = (n-1)!/2 cycles
- Optimum solution = in between lower and upper bound algorithms
- Upper bound algorithm
- Pick arc with the minimum weight joined to starting node
- Repeat until all nodes are chosen
- Add arc that joins last to first node
- Repeat for all vertices and choose the lowest
- Add arc that joins last to first node
- Repeat until all nodes are chosen
- Pick arc with the minimum weight joined to starting node
- Lower bound algorithm
Packing Algorithm
- First Fit
- Place each object in turn in available space in which it will fit
- First Fit Decreasing
- Arrange in decreasing order then first fit
- First Fit
Flow Charts
- Oval = start/stop
- Rectangle = instruction
- Diamond = question
Linear Programming
- If vertices of feasible region = integers the use to solve problem
- If not, then look at integer points closest to vertex
- Take 2 values of x either side and find max value of y in feasible region
- Sub in x and y values into constraints
- Choose the smallest values
- Sub in x and y values into constraints
- Take 2 values of x either side and find max value of y in feasible region
- If not, then look at integer points closest to vertex
- Shade unwanted region
- State x=?, y=?, x≥0, y≥0, max/min function, constraints, draw graphs
- Vertex method
- Draw function as line graph and move parallel towards lines and first vertex = answer
- Objective line method
- Swap coefficients of x and y
- Draw line then move parallel until it reaches feasible region
- Swap coefficients of x and y
- If vertices of feasible region = integers the use to solve problem
Route Inspection/Chinese Postman problem
- Only possible with Eulerian/semi
- If semi, must repeat some edges
- Locate all odd vertices
- Find pairings for which total = smallest
- Add up lengths of edges and pairing distances
- Find route
- Add up lengths of edges and pairing distances
- Find pairings for which total = smallest
- Locate all odd vertices
- If semi, must repeat some edges
- Only possible with Eulerian/semi
Order of an algorithm
- Efficiency = run-time
- Order = efficiency depending on size
- Size = complexity
- Efficiency α order
- Bubble/shuttle sort = quadratic order 1/2(n(n-1))
- Exponential order = very low efficiency
Simplex Algorithm
- Table with one row per equation and one column per variable
- Top row = objective function equation
- In each basis column, find 1 and read to final entry = value
- Choose most negative entry in objective row = pivot element in pivot column
- Do ratio test and choose minimum
- Add/subtract multiples of pivot row to/from other rows
- You are aiming to get the pivot column to 0s and get rid of negative numbers in objective row
- Add/subtract multiples of pivot row to/from other rows
- Do ratio test and choose minimum
Sorting Algorithms
- Bubble
- Work left to right along list comparing 1st and 2nd then 2nd and 3rd (swapping if necessary)
- 2nd pass with n-1 numbers etc
- Keep going for n-1 passes until complete pass with no swaps
- 2nd pass with n-1 numbers etc
- Work left to right along list comparing 1st and 2nd then 2nd and 3rd (swapping if necessary)
- Shuttle
- Compare 1st and 2nd item and swap if necessary
- Compare 2nd and 3rd item and swap if necessary
- If a swap is made go back to 1st and 2nd items
- Repeat until n-1 passes
- If a swap is made go back to 1st and 2nd items
- Compare 2nd and 3rd item and swap if necessary
- Compare 1st and 2nd item and swap if necessary
- Total passes/swaps = 1/2(n(n-1))
- Bubble
Información
- Descripción
- A2 Maths Mapa Mental sobre D1 Maths, creado por Grace Morris el 10/05/2017.
- Creado por
- Grace Morris
- Visitas
- 0
- Valoración
Más sobre Graph and Network Algorithms