Decision Flashcards
(30 cards)
What is Dijkstra’s algorithm?
- Choose the starting node of order 1, permeant label 0 and 0 workings
- Choose the next node with the least weight and label this 2
- Look at the workings across the entire graph and then choose the one of least weight
- Remember to add the weight from connected nodes
- Recite the path of shortest length back through network using common sense
What is the simplex algorithm?
- Rearrange maximum equation to 0
- Add slack variables
- Column it
- Pivot column is the smallest negative in profit row
- Divide other rows by the pivot column to decide pivot row
- The intersect of row and column is pivot element
- Equate all values in privity column to 0 apart from pivot element that goes to 1
What is a tour?
A route that visits every vertex, returning to the starting vertex
What is a Hamiltonian cycle?
A tour that passes through every vertext once and only once returning to the original vertex
What is the travelling salesmen method?
- Choose a vertex and delete all connected arcs
- Find minimum spanning tree for remaining graph
- Add up tree weight then add the two shortest arcs of the deleted vertex
What is the route inspection method?
- Locate all odd vertices
- Put them in pairs and find shortest route between them
- Choose pairing of shortest weight and add extra arcs to the paths
- Calculate total weight of graph with repeated arcs
What is the method from linear programming?
- Define variables
- Set objective
- Apply constraints
- Draw graphically with constraints
What is the point testing method?
Take the vertices if the region and put into the maximise or minimise equation, best value is optimum point
What is the objective line method?
- Take the constraints and find X and y values
2. Keep the ruler parallel and move outwards to find the optimum point
What are spanning trees?
Any graph that connects all the nodes
What is Prims algorithm?
- Have a starting point
- Choose the shortest length
- Choose the shortest length from the nodes already used
- Cannot make a cycle
- Write our order and total weight
What is kruskals algorithm?
- Write out lengths from smallest to largest
- Start with arc of least length
- Take next edge, checking to see if it makes a cycle
- Continue until a connected graph is made
What is Prims algorithm using matrix form?
- Select a node and label it 1, then cross out that entire row
- Look down column and look for the smallest weight
- Identify this value and cross out that row
- Look down both columns and identify smallest value
What is a trail/ route?
A single sequceb with no jumps
What is a path?
A trail where no bode is used more than once
What is a closed trail?
The first and final nodes are the same
What is a cycle?
A closed trail where only the first and final nodes are the same
What is the order of a node?
The number of arcs leaving the node
What does eularian mean?
Each node is an even order
What is semi-eularian?
Exactly 2 odd nodes in the graph
What if a graph has more than 2 odd nodes?
It is neither eularian or semi-eularian
What is the first fit bin packing algorithm?
Place each object in the first available space
What is the first fit decreasing algorithm?
- Write the list into decreasing order of weight
2. Use first fit algorithm
What is a simple graph?
There’s no loops, no two nodes connected
