Page 178 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes

Task Learn and revise various searching methods studied earlier in data structure.

Self Assessment

State whether the following statements are true or false:
5. Preconditions need to be satisfied before an operator can be applied.

6. A problem is any given situation that does not differs from a desired goal.
7. Though all the problems were not of crucial importance.
8. For many abstract problems it is possible to find an algorithmic solution.

9.3 Uninformed or Blind Search

Blind search, also called uninformed search, works with no information about the search space,
other than to distinguish the goal state from all the others. The following applets demonstrate
four different blind search strategies, using a small binary tree whose nodes contain words. Just
enter a word in the text input field (your word doesn’t have to be in the tree) and click on the
“Start Search” button in order to begin the search. The nodes will change color to red as they are
visited by the search.
Uninformed vs. Informed Search
Uninformed search strategies:

Also known as “blind search,” uninformed search strategies use no information
about the likely “direction” of the goal node(s)
Uninformed search methods: Breadth-first, depth-first, depth-limited, uniform-cost,
depth-first iterative deepening, bidirectional.

Informed search strategies:
Also known as “heuristic search,” informed search strategies use information about
the domain to (try to) (usually) head in the general direction of the goal node(s)

Informed search methods: Hill climbing, best-first, greedy search, beam search, A,
A*.

9.3.1 Breadth-first Search

Enqueue nodes on nodes in FIFO (first-in, first-out) order.
Complete

Optimal (i.e., admissible) if all operators have the same cost. Otherwise, not optimal but
finds solution with shortest path length.
d
Exponential time and space complexity, O(b ), where d is the depth of the solution and b
is the branching factor (i.e., number of children) at each node
Will take a long time to find solutions with a large number of steps because must look at
all shorter length possibilities first

A complete search tree of depth d where each non-leaf node has b children, has a
d
2
total of 1 + b + b + ... + b = (b (d+1) - 1)/(b-1) nodes

172 LOVELY PROFESSIONAL UNIVERSITY