List Of Algorithms Flashcards
Bubble sort
Quick sort
First fit
First fit decreasing
Full bin
Kruskal’s
Prims normal
Prims (Distance Matrix)
Dijikstra’s
You go from lowest to largest when selecting the order of the vertexes considered
After each new final output is written you do another pass
Route Inspection Algorithm
PSP UB
SP LB
Nearest Neighbour
Planetary algorithm
What does the route inspection algorithm do?
Find the minimum tour (general idea)
What is the aim of the algorithms to do with the Salesman Problem
Find a tour (generally)
What is a tour?
Tour - A walk which visits every vertex and which returns to its starting vertex
What does the planetary algorithm attempt to do?
Determine if a graph is planar or not
What does the nearest neighbour algorithm do?
Finds a upper bound to the Salesman’s problem
What is the difference between the simplex algorithm and the other 2?
The other 2 involve greater than or equal to constraints
What is the difference between the 2 stage simplex method and the Big M method?
The 2 stage simplex creates a new objective function to be minimised, whilst the Big M just manipulates the original objective function
What are the 3 steps to floyd’s algorithm?
Set up
Iteration
Interpretation
Explain the set up phase of floyd’s algorithm?
Remember everything is down then right.
You set up your distance table. Down the leading diagnal you have dashes
If there is no direct route then you put infinity
For the route table sameyou write ABCD down the page
ABCD
ABCD
ABCD
ABCD
How do you do the iteration stage of floyd’s algorithm?
Copy the first row and column and highlight them. Then for each box work out the value (X+Y) and compare it with the original value. If smaller than replace it.
If you replace it change the letter in the route table to the corresponding detour (the letter will the the one which has been highlighted)
Do this for each row and column
How do you do the interpretation stage of Floyd’s algorithm?
Remember down then right/
Find what detour is needed to get from A to D (eg C) then find what detour is needed to get from A C and repeat until you get C to C. (This will look like going across the row) Then write it in reverse/sensible order
