Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Uninformed Search Strategies

Uninformed search methods:
• Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search
• Iterative deepening search

**UNINFORMED SEARCH STRATEGIES**

•
__Uninformed__* *__strategies__** **use only
the information available in the problem definition

– Also known as blind searching

– ** Uninformed search methods**:

•
Breadth-first search

•
Uniform-cost search

•
Depth-first search

•
Depth-limited search

•
Iterative deepening search

**BREADTH-**

**FIRSTSEARCH**

**Definition:**

The root
node is expanded first, and then all the nodes generated by the node are
expanded.

•
Expand the * shallowest*
unexpanded node

•
Place all new successors at the end of a FIFO queue

**Implementation:**

**Properties of Breadth-First Search**

•
**Complete**

– Yes if b (max branching factor) is finite

•
**Time**

– 1 + b + b^{2} + … + b^{d} +
b(b^{d}-1) = O(b^{d+1})

– exponential in d

•
**Space**

– O(b^{d+1})

– Keeps every node in memory

– This is
the big problem; an agent that generates nodes at 10 MB/sec will produce

860 MB in
24 hours

•
**Optimal**

– Yes (if cost is 1 per step); not optimal in
general

**Lessons from Breadth First Search**

The
memory requirements are a bigger problem for breadth-first search than is
execution time

•
Exponential-complexity search problems cannot be
solved by uniformed methods for any but the smallest instances

**Ex: Route finding problem**

**Given:**

**Task: **Find the route from S to G using BFS.

**Step1:**

**Answer : **The path in the 2^{nd}** **depth level that is SBG (or ) SCG.

**Time complexity**

**DEPTH-FIRST SEARCH OR BACK TRACKING SEARCHING**

**Definition:**

Expand
one node to the depth of the tree. If dead end occurs, backtracking is done to
the next immediate previous node for the nodes to be expanded

•
Expand the * deepest*
unexpanded node

•
Unexplored successors are placed on a stack until
fully explored

•
Enqueue nodes on nodes in LIFO (last-in, first-out)
order. That is, nodes used as a stack data structure to order nodes.

•
It has modest memory requirement.

•
It needs to store only a single path from the root
to a leaf node, along with remaining unexpanded sibling nodes for each node on
a path

•
Back track uses less memory.

**Implementation:**

**Properties of Depth-First Search**

•
**Complete**

– No: fails in infinite-depth spaces, spaces
with loops

•
Modify to avoid repeated spaces along path

– Yes: in finite spaces

•
**Time**

– O(b^{m})

– Not great if m is much larger than d

– But if the solutions are dense, this may be
faster than breadth-first search

•
**Space**

– O(bm)…linear space

•
**Optimal**

– No

•
When search hits a dead-end, can only back up one
level at a time even if the “problem” occurs because of a bad operator choice
near the top of the tree. Hence, only does “chronological backtracking”

**Advantage:**

•
If more than one solution exists or no of levels is
high then dfs is best because exploration is done only a small portion of the
white space.

**Disadvantage:**

•
No guaranteed to find solution.

__Example: Route finding problem__

**Given problem:**

**Task: **Find a route between A to B

**Step 1:**

**Answer: **Path in 3^{rd}** **level is SADG

**DEPTH-LIMITED SEARCH**

A cut off (Maximum level of the depth) is introduced in this search technique to overcome the disadvantage of Depth First Sea rch. The cut off value depends on the number o f states.DLS can be implemented as a simple modification to the general tree search algo rithm or the recursive DFS algorithm.DLS im poses a fixed depth limit on a dfs.

**A variation of depth-first searc h that uses a
depth limit**

– Alleviates the problem of unbounded trees

– Search to a predet ermined depth l (“ell”)

– Nodes at depth l h ave no successors

•
Same as depth-first search if l = ∞

•
Can terminate for failure and cutoff

•
Two kinds of failure

**Standard failure: **indicates
no solution

**Cut off: **indicates no solution within the
depth limit

**Properties of Depth-Limited Search**

•
**Complete**

– Yes if l < d

•
**Time**

– N(IDS)=(d)b+(d-1)b²+……………………..+(1)

•
**Space**

– O(bl)

•
**Optimal**

– No if l > d

**Advantage:**

•
Cut off level is introduced in DFS Technique.

**Disadvantage:**

•
No guarantee to find the optimal solution.

__E.g.: Route finding problem__

**Given:**

The
number of states in the given map is five. So it is possible to get the goal
state at the maximum depth of four. Therefore the cut off value is four.

**Task: **find a path from A to E.

**Answer: **Path = ABDE Depth=3

**ITERATIVE DEEPENING SEARCH (OR) DEPTH-FIRST
ITERATIVE DEEPENING (DFID):**

**Definition:**

•
Iterative deepening depth-first search It is a
strategy that steps the issue of choosing the best path depth limit by trying
all possible depth limit

Uses
depth-first search

Finds the
best depth limit

**Gradually increases the depth limit; 0, 1, 2, …
until a goal is found**

**Iterative Lengthening Search:**

The idea
is to use increasing path-cost limit instead of increasing depth limits. The
resulting algorithm called iterative lengthening search.

**Implementation:**

**Properties of Iterative Deepening**

**Search:**

•
**Complete**

– Yes

•
**Time **:** N(IDS)=(d)b+(d-1)b ^{2}+…………+(1)b^{d}**

– O(b^{d})

•
**Space**

– O(bd)

•
**Optimal**

– Yes if step cost = 1

– Can be modified to explore uniform cost tree

**Advantages:**

•
This method is preferred for large state space and
when the depth of the search is not known.

•
Memory requirements are modest.

•
Like BFS it is complete

**Disadvantages:**

Many
states are expanded multiple times.

**Lessons from Iterative Deepening Search**

•
If branching factor is b and solution is at depth
d, then nodes at depth d are generated once, nodes at depth d-1 are generated
twice, etc.

– Hence b^{d} + 2b^{(d-1)} +
... + db <= b^{d} / (1 - 1/b)^{2} = O(b^{d}).

– If b=4,
then worst case is 1.78 * 4^{d}, i.e., 78% more nodes searched than
exist at depth d (in the worst case).

•
Faster than BFS even though IDS generates repeated
states

– BFS generates nodes up to level d+1

– IDS only generates nodes up to level d

•
In general, iterative deepening search is the
preferred uninformed search method when there is a large search space and the
depth of the solution is not known

__Example: Route finding problem__

**Given:**

**Answer: **Since it is a IDS tree the lowest
depth limit (i.e.) A-F-G is selected as the solution path.

**BI-DIRECTIONAL SEARCH**

**Definition:**

It is a
strategy that simultaneously searches both the directions (i.e) forward from
the initial state and backward from the goal state and stops when the two
searches meet in the Middle.

•
Alternate searching from the start state toward the
goal and from the goal state toward the start.

•
Stop when the frontiers intersect.

•
Works well only when there are unique start and
goal states.

•
Requires the ability to generate “predecessor”
states.

•
Can (sometimes) lead to finding a solution more
quickly.

**Properties of Bidirectional Search:**

1.
Time Complexity: O(b ^{d/2})

2.
Space Complexity: O(b ^{d/2})

3.
Complete: Yes

4.
Optimal: Yes

**Advantages:**

Reduce
time complexity and space complexity

**Disadvantages:**

The space
requirement is the most significant weakness of bi-directional search.If two
searches do not meet at all, complexity arises in the search technique. In
backward search calculating predecessor is difficult task. If more than one
goal state exists then explicitly, multiple state searches are required.

**COMPARING UNINFORMED SEARCH STRATEGIES**

•
**Completeness**

– Will a solution always be found if one
exists?

•
**Time**

– How long does it take to find the solution?

– Often
represented as the number of nodes searched

•
**Space**

– How much memory is needed to perform the
search?

– Often represented as the maximum number of
nodes stored at once

•
**Optimal**

– Will the optimal (least cost) solution be
found?

•
**Time and
space complexity **are measured in

– b – maximum branching factor of the search
tree

– m – maximum depth of the state space

– d – depth of the least cost solution

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.