Special Topics in AI | Module 03: Searching Algorithms

Searching

The most commonly used technique of problem solving in artificial intelligence.

Problem Solving Agent

A goal-driven agent and focuses on satisfying the goal.

Problem Solving Agent

Generating the solution by keeping the different condition in mind.

Problem Solving Agent

It solves problem by finding sequences of actions that lead to desirable states (goals).

Problem Solving Agent

To solve a problem, its first step is the goal formulation, based on the current situation.

Goal Formulation

What is the first step of a problem solving agent to solve a problem based on the current situation?

Initial state, actions, transition model, goal test, path cost

Five (5) Components of a Problem

Initial State

The state from which agent start.

Initial State

Starting point of a problem; where to start.

Actions

A description of the possible actions available to the agent.

Actions

Possible rules or steps of how state moves.

Transition Model

A description of what each action does.

Transition Model

For formulating this in problem formulation, we take state 𝑠 and action 𝑎 for that state and then specify the resulting state 𝑠.

Transition Model

What happens after each specified action/s.

Goal Test

Determine whether the given state is goal state or not.

Path Cost

Sum of cost of each path from initial state to the given state.

Path Cost

Cost function; measures how good or efficient a solution is.

Varies between different factors.

Goal Formulation

Based on the current situation and the agent’s performance measure.

It organizes steps required to achieve that goal.

Goal Formulation

Intelligent agent maximize their performance measure by adapting a goal and aim at satisfying it.

Goal

Help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider.

Goal Formulation

It is the step where you specify what are the successful world states.

Problem Formulation

The process of deciding what actions should be taken to achieve the formulated goal.

Problem Formulation

The process of deciding what actions and states to consider, given a goal.

Problem Formulation

The agent’s task is to find out how to act, now and in the future, so that it reaches a goal state.

Problem Formulation

Before it can do this, it needs to decide what sorts of actions and states it should consider.

Search

Explore possible actions or paths.

Searching

The process of looking for a sequence of actions that reaches the goal.

Search Algorithm

Takes a problem as an input and returns a solution in the form of an action sequence.

Solution

Choose the best sequence of actions.

Execution

Once a solution is found, the actions it recommends can be carried out.

Execution

Once a solution has been executed, the agent will formulate a new goal.

Searching Algorithm

The agent can examine different possible sequences of actions, and choose the best.

Searching Algorithm

Defined as taking a problem and returns a solution.

Searching Algorithm

Once a solution is found, the agent follows the solution and carries out the list of actions – execution phase

Formulate, search, execute

What is the design of an agent?

Complete

A search algorithm is said to be ___ when it gives a solution or returns any solution for a given random input.

Completeness

It answers the question:

Is the strategy guaranteed to find a solution when there is one?

Optimal

If a solution found is best (lowest path cost) among all the solutions identified, then that solution is said to be an ___ one.

Optimality

It answers the question:

Does the strategy find the highest-quality solution when there are several different solutions?

Time Complexity

The time taken by an algorithm to complete its task.

Time Complexity

If the algorithm completes a task in a lesser amount of time, then it is an efficient one.

Time Complexity

It answers the question:
How long does it take to find a solution?

Space Complexity

It is the maximum storage or memory taken by the algorithm at any time while searching.

Space Complexity

It answers the question:

How much memory is needed to perform the search?

8 Queens Problem

Its goal is to place eight queens on a chessboard such that no queen attacks any other.

Uninformed Search Method

Does not have any domain knowledge such as closeness, location of the goal state etc.

Uninformed Search Method

It behaves in a brute-force way.

It only knows the information about how to traverse the given tree and how to find the goal state.

Blind Search Algorithm, Brute-Force Algorithm

Another term for Uninformed Search Method.

Informed Search Method

Requires details such as distance to reach the goal, steps to reach the goal, cost of the paths which makes this algorithm more efficient.

Heuristic Function

The goal state of an informed search method can be achieved by using this function.

Heuristic Function

This function is used to achieve the goal state with the lowest cost possible in informed search method.

Heuristic Function

This function estimates how close a state is to the goal in informed search method.

Heuristic Search, Directed Search

Another term for Informed Search Method.

Breadth First Search

One of the most common search strategies.

Breadth First Search

It generally starts from the root node and examines the neighbor nodes and then moves to the next level.

Breadth First Search

Uses First-in First-out (FIFO) strategy as it gives the shortest path to achieving the solution.

Breadth First Search

Used where the given problem is very small and space complexity is not considered.

Depth First Search

Uses Last-in, First-out (LIFO) strategy and it can be implemented by using stack.

Depth First Search

Uses backtracking.

Starts from the initial state and explores each path to its greatest depth before it moves to the next path.

Depth Limited Search

Has a pre-defined limit up to which it can traverse the nodes.

Depth Limited Search

Solves one of the drawbacks of DFS as it does not go to an infinite path.

Standard Failure

Denotes that the given problem does not have any solutions.

Cut off Failure Value

Indicates that there is no solution for the problem within the given limit.

Iterative Deepening Depth-First Search

A combination of depth-first search and breadth-first search.

Iterative Deepening Depth-First Search

Finds the best depth limit by gradually adding the limit until the defined goal state is reached.

Bidirectional Search

Completely different from all other search strategies.

Bidirectional Search

Executes two simultaneous searches called forward search and backwards-search and reaches the goal state.

Bidirectional Search

The graph is divided into two smaller sub-graphs.

In one graph, the search is started from the initial start state and in the other graph, the search is started from the goal state.

When these two nodes intersect each other, the search will be terminated.

Bidirectional Search

Requires both start and goal start to be well defined and the branching factor to be the same in the two directions.

Uniform Cost Search

It is considered the best search algorithm for a weighted graph or graph with costs.

Uniform Cost Search

It searches the graph by giving maximum priority to the lowest cumulative cost.

Uniform Cost Search

It can be implemented using a priority queue.

Greedy Best-First Search Algorithm

An informed search algorithm that uses the properties of both depth-first search and breadth-first search.

Greedy Best-First Search Algorithm

Traverses the node by selecting the path which appears best at the moment.

A* Search Algorithm

A combination of both uniform cost search and greedy best-first search algorithms.

A* Search Algorithm

Uses the advantages of both with better memory usage.

A* Search Algorithm

Uses the sum of both the cost and heuristic of the node to find the best path.

FIFO Queue

What data structure and strategy does breadth-first search use?

LIFO Stack

What data structure and strategy does depth-first search use?

LIFO Stack

What data structure and strategy does depth-limited search use?

Stack

What data structure does iterative deepening depth-first search use?

Two Queues

What data structure does bidirectional search use?

Priority Queue

What data structure does uniform cost search use?

O(b^d)

What is the time complexity of Breadth-First Search?

O(b^m)

What is the time complexity of Depth-First Search?

O(b^l)

What is the time complexity of Depth-Limited Search?

O(b^d)

What is the time complexity of Iterative Deepening Depth-First Search?

O(b^(d/2))

What is the time complexity of Bidirectional Search?

O(b^d)

What is the space complexity of Breadth-First Search?

O(bm)

What is the space complexity of Depth-First Search?

O(bl)

What is the space complexity of Depth-Limited Search?

O(bd)

What is the space complexity of Iterative Deepening Depth-First Search?

O(b^(d/2))

What is the space complexity of Bidirectional Search?