Page 179 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

For a complete search tree of depth 12, where every node at depths 0, ..., 11 has 10 Notes
children and every node at depth 12 has 0 children, there are 1 + 10 + 100 + 1000 + ...
12
13
12
+ 10 = (10 - 1)/9 = O(10 ) nodes in the complete search tree. If BFS expands 1000
nodes/sec and each node uses 100 bytes of storage, then BFS will take 35 years to run
in the worst case, and it will use 111 terabytes of memory!
9.3.2 Depth-first Search

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

May not terminate without a “depth bound,” i.e., cutting off search below a fixed depth D
(“depth-limited search”)

Not complete (with or without cycle detection, and with or without a cutoff depth)
d
Exponential time, O(b ), but only linear space, O(bd)
Can find long solutions quickly if lucky (and short solutions slowly if unlucky!)

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.

Self Assessment

State whether the following statements are true or false:
9. Blind search works with information about the search space.

10. Uninformed search strategies also known as heuristic search.
11. Depth-first Search may terminate with a depth bound.
12. Breadth-first Search enqueue nodes on nodes in FIFO.

9.4 Informed Search

It is not difficult to see that uninformed search will pursue options that lead away from the goal
as easily as it pursues options that lead to wards the goal. For any but the smallest problems this
leads to searches that take unacceptable amounts of time and/or space. Informed search tries to
reduce the amount of search that must be done by making intelligent choices for the nodes that
are selected for expansion. This implies the existence of some way of evaluating the likelihood
that a given node is on the solution path. In general, this is done using a heuristic function.

Unfortunately, uninformed search methods are very inefficient in most cases.
We now show how heuristic search strategies – ones that use problem specific knowledge – can
find solutions more efficiently. In computer science, a search algorithm is an algorithm for
finding an item with specified properties among a collection of items. The items may be stored
individually as records in a database; or may be elements of a search space defined by a
mathematical formula or procedure, such as the roots of an equation with integer variables; or
a combination of the two, such as the Hamiltonian circuits of a graph. Algorithms for searching
virtual spaces are used in constraint satisfaction problem, where the goal is to find a set of value
assignments to certain variables that will satisfy specific mathematical equations and inequations.
They are also used when the goal is to find a variable assignment that will maximize or minimize
a certain function of those variables.

LOVELY PROFESSIONAL UNIVERSITY 173