Search Algorithms

Different Types of Search Algorithms

• Exhaustive Search Methods:
• Random Search
• BFS
• -DFS
• Itterative dbs
• Heristic Search Methods:
• Dijstra
• -A*
• - Min Max
• - Monty Carlo

Random Walk

• (This is an Exhaustive Search Method)

BFS: Breadth-first Search

• First In First out
• (This is an Exhaustive Search Method)

DFS: Depth First Search

• Uses Recurision
• (This is an Exhaustive Search Method)

Itterative DFS

• Operates in a way more similar to BFS
• Que: Last in First out
• So you have
• (This is an Exhaustive Search Method)

Dijstra

• Summary!
• Everything is going to be weighted in number values
• Tells you the fastest way to get to each point
• Always removes the Shortest Node
• Doesn't really have a goal, just finds the shortest path to every node (if you wanted to stop it you would just have to stop it when it reaches the node you want)
• Starting at A in this case, for the sake lets say we are trying to get to I
• A is removed from the stack, then it looks at all the neighbours and write down its distance values
• So B:2, G:4, D:1.2
• From those numbers its going to take the smallest number (shortest past)
• So now it has: B:2, G:4, E: 2.4
• Then C:4, G:4, E: 2.4
• Then C:4, G:4, F: 3.6
• 

A*

• Summary!
• If he doesn't give a heuristic to use then use Euclidean distance
• Euclidean Distance: Straight line distance b/w two points.
• The heuristic has to be equal to or less than the actual distance of the path.
• The heuristic has to underestimate the distance for it to work.
• A* star is going to check the distance + the heuristic
• 

Slide 8

Sliding Tile Puzzle 1

• STEPS
• Write down all the numbers in the order they appear
• Proceed to Do inversions
• Then take the inversion total and add to formula
• Inversion: When a tile perceives a tile with a lower number on it
• Solvable States
• "If width is odd, and the number of inversion total is even then its solvable"
• "If the width is even, and the X (blank) is on an even row from the bottom, then the inversion must be odd to be solvable"
• "If the width is even, and the X (blank) is on an odd row from the bottom then the inversion must be even to be solvable"