Page 187 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

18. Any subproblem may not be decomposed into subproblems. Notes
19. The AND/OR-tree search function is only applicable in the case where we wish to solve a
simplified planning problem.

20. To obtain a specific implementation we only need to set up the appropriate rule base.

9.6 Summary

The AI system are developed using the knowledge of an expert person (or persons) in the
field where the system will be applied.

Each node or vertex in the graph corresponds to a problem state, and arcs between nodes
correspond to transformations or mapping between the states.

Search can be characterized as finding a path through a graph or tree structure.
The process of generating all of the children of a parent is also known as expanding the
node.
A search procedure is a strategy for selecting the order in which nodes are generated and
a given path selected.
The problem space of means-end analysis has as initial state and one or more goal states,
a set of operators Ok with given preconditions for their application, and a difference
function that computes the difference between two states Si and Sj.
Information might relate to the problem space as a whole or to only some states.
The depth-first search is preferred over the breadth-first when the search tree is known to
have a plentiful number of goals. Otherwise, depth-first may never find a solution.

9.7 Keywords

Backtracking: It helps in undoing what has been done so far and permits to try a totally different
path to attain the global peak.

Blind or Uninformed: It is a search algorithm that is one that uses no information other than the
initial state, the search operators, and a test for a solution.
Breadth-first Searches: These are performed by exploring all nodes at a given depth before
proceeding to the next level.
Depth-first Searches: These are performed by diving downward into a tree as quickly as possible
Hill Climbing: It is like depth-first searching where the most promising child is selected for
expansion.
Informed Search Methods: These often depend on the use of heuristic information i.e. information
about the problem (the nature of the states, the cost of transforming from one state to another,
the promise of taking a certain path, and the characteristics of the goals) can sometimes be used
to help guide the search more efficiently.

Local Maximum: It is a state that is better than al its neighbours but not so when compared to
states to states that are farther away.
Plateau: A flat area of the search space, in which all neighbours have the same value.

Ridge: Described as a long and narrow stretch of elevated ground or a narrow elevation or
raised path running along or across a surface.

LOVELY PROFESSIONAL UNIVERSITY 181