L2 - Search Algorithms

AI, States, nodes, trees, graphs, search algorithms, time complexity, space complexity, depth, state spaces, heuristics

What is meant by symbolic AI?

AI that uses logic-based rules and symbols

What is meant by stochastic AI?

AI that uses probability and randomness to make decisions, usually learning from data patterns

What is meant by AI winter?

A period of reduced interest, funding and development in AI research

What is meant by a state?

Representation of a physical configuration

What is meant by a node?

A data structure which is part of a search tree

What can a node include?

Parent, child, depth or path cost

What do states not include?

Parent, child, depth or path cost

What is the fringe for Depth First Search?

Last In, First Out

Travels as far as possible down a node, then moves to another

What is the fringe for Breadth First Search?

First In, First Out

Travels level by level

What is a search strategy?

Picking the order of node expansion

What is meant by completeness in a search strategy?

If a solution exists, does the strategy always find it

What is meant by time complexity in a search strategy?

Amount of time an algorithm takes to run, as input size increases

What is meant by space complexity in a search strategy?

Maximum amount of memory used by an algorithm

What is meant by optimality?

Is the least-cost solution always found?

What is the first component that time and space complexity are measured in?

b - Max branching factor

(Max no.of successors a node can have)

What is the second component that time and space complexity are measured in?

d - depth of least-cost solution

What is the third component that time and space complexity are measured in?

m - max depth of state space

(Longest possible path, may be ∞)

What is meant by an uninformed search strategy?

Only the information available in the problem is used

What are the uninformed search strategies?

Breadth First

Depth First

Uniform Cost Search

Depth Limited

Iterative Deepening

Bidirectional

Which search component is denoted by the character, l?

Depth limit

Which search component is denoted by the character, C*?

Cost of optimal path

Is BFS complete?

Yes, if branching factor is infinite

What is the time complexity of BFS?

Exponential in depth limit

What is the space complexity of BFS?

Keeps every node in memory

Is BFS optimal?

Yes

(If cost = 1 per step)

What is the problem with BFS?

Space complexity

Can generate nodes at 100MB/sec, so 24hrs = 8640GB

Is DFS complete?

No

Fails in infinite-depth and looped spaces

How do you deal with a DFS completeness issue?

Modify to avoid repeated states

Complete DFS in finite spaces

What is the time complexity of DFS?

Terrible if m > d

In terms of time complexity, when can DFS be faster than BFS?

If the solutions are dense

What is the space complexity of DFS?

Linear space

Is DFS optimal?

No.

Deep nodes may be discovered first

How can the issues with BFS and DFS be solved?

Limit depth

Iterative deepening

Heuristics

What are heuristics?

Rules of thumb that estimate the cost of reaching a goal

How does depth limited research work?

DFS with a depth limit, l

Diagram of iterative deepening search, where l = 3

Uses linear space and less time

Table of comparison of search algorithms

What is graph search used to detect?

Loops

What is the first step in graph search?

A closed list is provided

What is the second step in graph search?

Before node is expanded, list is checked

What is the third step in graph search?

Existing nodes are skipped, non-existent nodes are added

Which is more efficient, graph or tree search?

Graph

(Can be exponentially more efficient)

What are the informed search algorithms?

Best-first, greedy, A*

What is the fringe for Best-First Search?

Queue sorted in a decreasing order of desirability

How does greedy search work?

Expands the lowest cost node

Which formula h(n) is used in greedy search?

Estimated cost from node, n, to the closest goal

Is greedy search complete?

No.

Can get stuck in loops

What is the time complexity of greedy search?

A good heuristic can improve it

What is the space complexity of greedy search?

All nodes kept in memory

Is greedy search optimal?

No

How does A* search work?

Avoids nodes that are expensive

What is the formula for A* search?

f(n) = g(n) + h(n)

What is represented by g(n) in the A* search formula?

Cost so far to reach n

What is represented by h(n) in the A* search formula?

Estimated cost to goal from n

What is represented by f(n) in the A* search formula?

Estimated total cost of path through n to goal

Diagram of A* search

Is A* search optimal?

Yes, if the heuristic never overestimates the cost to reach the goal (admissible)

Is A* search complete?

Yes

Unless there are infinitely many nodes with f ≤ f (G)

What is time complexity of A* search?

Depends on quality of heuristic

Worst case - O(b^d)

What is space complexity of A* search?

Keeps all nodes in memory