Search Algorithms in AI

Lecture 3 - Part 1: Search in Problem Solving

• Goal-based agents are used in problem-solving
• Lecture is about search in problem solving
• Search methods for state space are covered
• Uninformed and informed search algorithms are discussed
• Graph theory review is part of the lecture

Important Chapter Summary

• Uninformed search strategies include Breadth-First Search (BFS) and Depth-First Search (DFS)
• Informed search strategies include Uniform-Cost Search (UCS), Best-First Search, and A* search
• Depth-First Iterative deepening (IDS) and Bidirectional search (BS) are also discussed
• Time and space complexity for each algorithm are included

Lecture Outline (Chapter 3)

• Graph theory is briefly reviewed
• Strategies for state space search are outlined
• Uninformed search algorithms are discussed
• Informed search algorithms are discussed
• Asymptotic complexity (Big O) is reviewed

Recap: Predicate Calculus

• Predicate calculus expressions offer well-defined formal semantics and sound and complete inference rules
• Predicate calculus is a good representation language

Objectives: Problem-Solving Agent

• Agents act by setting goals and considering actions to achieve them
• A problem is a goal and the means to achieve it
• Search is the process of exploring the means to achieve a goal

Search for Solutions (Generate and Test)

• Generating action sequences is a key part of search
• Data structures for search trees are important

Search Strategies (Properties of Search Methods)

• Completeness: guaranteeing all solutions are found
• Time complexity: the time taken for a search
• Space complexity: memory used for a search
• Optimality: finding the best/optimal solution
• Admissibility: finding the optimal solution quickly
• Irrevocability: potentially finding suboptimal solutions

Search Technique/Algorithms

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Search Problems in the Algorithm Class

• Sequential Search
• Binary Search
• N-Queen Problem
• Sum-of-Subsets Problem
• Graph Coloring Problem
• Hamiltonian Circuits Problem
• 0-1 Knapsack Problem
• Traveling Salesperson Problem

Search Questions

• Is the problem solver guaranteed to find a solution?
• Will the problem solver always terminate?
• When a solution is found is it guaranteed to be optimal?
• What is the complexity of the search process in terms of time and memory usage?
• How can the interpreter most effectively reduce search complexity?
• How can an interpreter be designed to efficiently use a representation language?

Goal-Based Agents

• Goal-based agents succeed by considering future actions and their outcomes
• Problem-solving agents find sequences that lead to desirable states
• General-purpose search algorithms can solve these problems

Goal-Driven Search vs Data-Driven Search

• Goal-Driven search starts at the goal and works backwards
• Most search methods are data-driven, starting from an initial state

Examples of Search Problems

• Chess: looking for a move to improve position
• Route planning: minimizing distance between locations
• Theorem proving: finding reasoning steps to prove a theorem
• Machine learning: finding a concept to categorize

Search Terminology

• States: places the search can visit
• Search space: set of possible states
• Search path: the states the agent actually visits
• Solution: a state accomplishing the problem
• Strategy: choosing the next step in a path
• Goal formulation: deciding the actions and states to consider; given a goal
• Problem formulation: deciding what actions and states to consider given a goal
• Search: the exploration process

Well-Defined Problems and Solutions

• A problem is defined by four components:
  • Initial state
  • Actions
  • Goal test
  • Path cost

Specifying a Search Problem

• Initial state: tracking visited states
• Operators: functions that change states
• Goal test: determining if search succeeded

Two types of Search Algorithms

• Uninformed search algorithms have no problem information other than its definition
• Informed search algorithms have some idea of where to look for solutions

General Search Considerations

• Path or artefact: is it the route or destination
• Completeness: finding all solutions
• Time and space trade-offs: balancing speed and memory
• Soundness: ensuring found solutions are valid
• Additional information: extra data for the agent

Measuring Problem-Solving Performance

• Completeness
• Optimality
• Time complexity
• Space complexity

Graph and Agenda Analogies

• Graph analogy: states are nodes, operators are edges
• Agenda analogy: (State, Operator) pairs are put onto an agenda; operator used to generate new state from a given state

Example Problem

• Goal: finding a boy's name from letters D, N, A
• Initial state: empty string
• Searching, Operators, and Goal testing

Uniform Search Strategies

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Breadth-First Search (BFS)

• New state, S, reached, agenda items placed at bottom of the agenda
• Graph Analogy: expanding a node level by level

Exercise: Web Spidering

• BFS is preferred for web spidering because the web is assumed to be connected

Graph Theory Review (Data Structures)

Graph Terminology

• Graph: G=(V,E)
• Vertex set: V
• Edge set: E (adjacent vertices)

Directed and Undirected Graphs

• Directed graphs have ordered pairs (u, v) for edges
• Undirected graphs have unordered pairs {u, v} for edges

Proper Graphs and Subgraphs

Paths in Graphs

Simple Paths and Cycles

A Connected Undirected Graph

Connected Components of an Undirected Graph

Biconnected Undirected Graphs

Size of a Graph

Representing a Graph by an Adjacency Matrix

Adjacency List Representation of a Graph

Definition of an Undirected Tree

Definition of a Directed Tree

An Ordered Tree

An Ordered Tree (Definition)

An Ordered Tree (Types)

Tree Traversal (Preorder)

Tree Traversal (Inorder)

Tree Traversal (Postorder)

Exercise: Tree Traversal

Spanning Tree

Example Spanning Tree of a Graph

Classification of Edges of G with Spanning Tree T

Minimum Spanning Tree (MST)

Examples

Search Strategies

Uninformed Search Strategies

Breadth-First Search (BFS) (Genetic Professor's Son Name)

An example for BFS

BFS Exercise

BFS of the 8-puzzle

DFS Property

An example for DFS

DFS Exercise

DFS vs BFS

Recap: Breadth-First Search (BFS)

Depth-Limited Search

Iterative Deepening (Depth-first) Search (IDS)

IDS

Bidirectional Search

Bidirectional Search ...

Comparing Uninformed Search Strategies

Uninformed Search?

Uniform Cost Search (UCS)

Difference: Best-first search, UCS, and A*

Uniform Cost Search (UCS)

Uniform-Cost Search (UCS)

Example of Uniform-Cost Search

Exercise for UCS

Conclusion

Conclusion (Summary)

Test your knowledge on search algorithms in artificial intelligence, including iterative deepening search, bidirectional search, and depth-first search. This quiz covers key aspects like time complexity, completeness, and advantages of different search strategies.