Search

The two types of search

Goal based - trying to find a solution.

Utility based - trying to find an optimal solution, best when there is a big search area.

Tree Search (graph)

• Solution is a series of actions, aka (go: left, right and then forwards)

• Optimality tests are normally possible

• Uninformed (blind, aka doesn’t know close it is to the goal) and informed (heuristic, aka it knows how close it is to the goal)

Definitions

• Initial state - Where you start the problem

• Actions - Moving to the next state

• Goal test - The state you are trying to reach

• Path cost - How much of a negative impact going on that path is going to have on certain conditions relevant to the success of the problem

Evaluating algorithums

• Completeness - is a solution or goal guaranteed to be found?

• Time Complexity - how long will it take to compute?

• Space complexity - how much memory is required?

• Optimality - will the algorithm defiantly find the very best solution?

BFS

• Description: try all neighbouring nodes then move on to each of their neighbours

• Completeness: Yes

• Memory: Exponential growth

• Time: Exponential growth

• Optimality: Yes, only if each path is of equal cost

DFS

• Description: try the deepest node next

• Completeness: Yes

• Memory: Linear

• Time: Exponential

• Optimality: No (left most will be found first)

Iterative Deepening Search (IDS)

• Description: same as DFS except there is a depth (cost) bound

• Completeness: Yes

• Memory: Linear

• Time: Exponential, a tad more than DFS

• Optimality: Yes, only if equal in cost

A* Search

• Description:
  1. Look at all the neighbour nodes, all neighbour nodes will have an estimated cost of getting to the goal state
  2. Add the cost of going to that node, with its estimated cost of going to the goal
  3. Once a node is visited an A* score is kept including the cheapest path to it
  4. Go to the cheapest option, once the cost is greater than another known path, you then move to the cheaper one
  5. If the new nodes path cost is less than an existing known path, do not bother exploring it, and move onto the next cheapest option

• Completeness: Yes

• Memory: Exponential

• Time: Exponential (is better with a good heuristic)

• Optimal: Yes

Greedy (best-first search)

• Description:
  1. Picks the next node with the shortest estimated distance to the goal, don’t care about the distance already

• Completeness: No

• Optimal: No (but in practice is pretty good)

Local Search

• Typically attempts to improve an existing solution, no regard taken for the actions made

• Search space is huge

• Optimality tests are not reasonable or possible

• Properties
  • Non-deterministic: its not possible to predicts what will happen next (aka: kicking a ball)
  • Partially-Observable: not all aspects of the environment are known (aka: navigating without knowing traffic conditions)

Hill Climbing

Aims to get the the global maximum

• Next position is the best one thats near by

• But it can get stuck in a local maxima

Random-restart hill climbing

• Same as hill climbing

• But, once in a local maxima, it will retry in a new random spot

Tabu search

• Same as hill climbing

• But, will randomly choose a neighbour with a lower fitness value

Simulated Annealing

• Seems to take a binary search approach, and moves towards is the high fitness options

• Just works off probability, it is not guaranteed to work

Beam search

• Multi treaded search

• Pick the best options that all agents found

Exploitation and Exporation

exploitation - improve existing solutions

exporation - randomly create solutions

Constraint satisfaction problems

• Goal is to satisfy a set of rules

• An example is DFS can be used