Artificial Intelligence/Search

Introduction

The general concept of ‘searching’ is about looking for something. For example, we want to drive to some destination and we need to find the car key. Locating the car key is a simple search problem. In computer science, searching techniques are strategies that look for solutions to a problem in a search space. The solutions or ‘goal states’ could sometimes be an object, a goal, a sub-goal or a path to the searched item. In the car key example, the search goal is the car key and the search space is confined to the owner’s home. The car key can be located anywhere in the owner’s house.

In general, a computer search problem has the following characteristics:

A goal state – the definition of a need
An initial state – a current position or a set of conditions
A set of actions - strategies and actions to select and evaluate an option in the search space
Goal test criteria – criteria used to test if an option is a solution
A path cost - the cost of the actions in a search path

Search Space

The search space can be represented by a ‘graph’ which is based on graph theory. The ‘graph’ structure is not to be confused with the graphs that the readers might have learned from their regular mathematics courses. A computer ‘tree’ data structure is a special kind of graph. A tree has a root node on the top of the structure and it has at most one path to each node. Each node may be connected to a lower level of neighbors which are called child nodes (successors). Nodes that have no children are called leaf nodes.

Using the car key example, the owner’s home is defined as the search space. It has the ‘home’ node as the root of a tree. The home node has three child nodes (the room nodes) and other child nodes such as desks and drawer in the rooms. The set of possible permutations that can be examined by a search method in order to find a solution.

Types of Search