|
Intelligent Search Algorithms
-- Tony Abou-Assaleh
Note:This article assumes basic understanding of traditional search algorithms
like depth-first search and breadth-first search.
INTRODUCTION
Many traditional search algorithms are used in artificially intelligent applications.
However, for complex problems these algorithms are unable to find the solution within
practical time and space limits. As a result, many special techniques were developed,
which are called heuristic functions. Similarly, algorithms that use these techniques are
called heuristic algorithms. Thus, intelligent search algorithms are not really
intelligent. We call them that way because they achieve better performance by applying
these techniques than what they would achieve otherwise.
Heuristic algorithms are more efficient because they take advantage of feedback from
the data to direct the search path, while brute-force algorithms follow the same path
regardless of the data being tested. There are many problems that cannot be solved using
traditional search algorithms. Probably the most popular example is the Travelling
Salesman Problem (TSP). In such problems, finding a good solution becomes our goal instead
of finding the best solution. As we proceed in our search, we use current information
about the problem to predict which path is closer to the goal and follow it, although it
does not always guarantee to find the best possible solution. This technique helps us find
a solution within reasonable time and consuming a reasonable amount of space.
There are six main kinds of intelligent search algorithms:
1. Generate and Test Search
2. Best-first Search
3. Greedy Search
4. A* Search
5. Constraint Search
6. Means-ends analysis
Most other algorithms are improvements and/or combinations of these six methods. For
each method we will discuss how it works and where it can be best applied.
1. GENERATE AND TEST SEARCH
This simplest form of generate and test algorithm has the following three steps:
1. Generate a possible solution.
2. Compare it to the goal states.
3. If the solution was found return success; otherwise, go to step 1.
If there is a solution to the problem, this algorithm will find it. However, note that
it may take very long time before the solution is found. An improved version of this
algorithm is called hill-climbing algorithm. In hill climbing, we use a heuristic function
to estimate the distance from the goal state. Thus, we generate only the solutions that
will minimize this distance.
One of the disadvantages of this algorithm is that the algorithm may find a locally
good solution, while the desired goal state is just a few steps away. This happens when we
have a multiple-peak problem. If we start searching near a lower peak (locally good
solution) we will miss the optimal solution. Also, if we have a flat area where all the
possible solutions have same distance then the progress cannot proceed and the algorithm
halts. To partially overcome these disadvantages, a noise may be introduced into the
function that evaluates the distance from the goal state. Setting the noise to a high
volume in the beginning and decreasing it as we progress improves the performance of this
algorithm.
2. BEST-FIRST SEARCH
Best-first algorithm is an improved combination of breadth-first and depth-first
algorithms. The main advantage is in using a heuristic function to reorder the nodes in
the queue. Thus, we choose the best node from the queue to continue the search regardless
of the node's actual position in the problem graph.
The main steps of this algorithm are as follow:
1. Add the initial node (starting point) to the queue
2. Compare the front node to the goal state. If they match then the solution is found.
3. If they do not match then expand the front node by adding all the nodes from its links.
4. If all nodes in the queue are expanded then the goal state is not found (e.g. there is
no solution). Stop.
5. Apply the heuristic function to evaluate and reorder the nodes in the queue.
6. Go to step
This algorithm is widely used when using one of the brute-force algorithms is not very
efficient.
3. GREEDY SEARCH
This algorithm uses an approach that is very similar to the best-first algorithm.
Basically, it takes the closest node the goal state and continues searching from there.
However, usually it is very difficult to compute the exact distance from the goal state.
Therefore, a heuristic function is used to estimate this distance. Thus, a better
estimation function will result in a better performance, and consequently, find the
solution faster. Although Greedy algorithm has many common characteristics with the
breadth-first algorithm, the advantage of directing the search makes it more preferable.
4. A* SEARCH
One can think of A* algorithm as a very sophisticated greedy algorithm. This algorithm
merges two heuristic functions into one function. This function evaluates each node by
adding the estimated distance from the goal state to the distance from the initial state.
Using more feedback from the search nodes (current cost and estimated cost) gives this
algorithm completeness (if the solution exists, it will be found) and optimality (it will
find the best solution). All these advantages made A* algorithm the most popular search
algorithm in AI applications.
5. CONSTRAINT SEARCH
Every problem space has constraints that will limit the size of the solution space. For
example, you have $500 and you would like to buy some computer accessories. To begin with,
you cannot bye any accessory that costs more than $500. If you bye a printer for $200,
then the remaining solution space will consist only of accessories that cost no more than
$300. This technique is usually used as a combination with another search algorithm to
further improve the performance.
6. MEANS-ENDS ANALYSIS
Means-ends analysis is a different approach to find a solution. The main criterion for
directing the search is minimizing the change between states. The solution space is
defined as a set of states and a set of operations that can change these states. A
simplified version of this algorithm tries to identify the subset of states that lead
directly to the current state (backward reasoning) and a subset of states that results
from the current state (forward reasoning). Then the algorithm is applied to each of the
two parts using a recursive call. The recursion stops when the goal state matches the
current state (the solution is found) or when it is impossible to generate any new state
(solution does not exist).
This algorithm is one of the most efficient search algorithms, and therefore, it is
used in AI application when a complex search need to be done, as in planning applications.
CONCLUSION:
For every search algorithms there is a trade-off between complexity and efficiency.
Fast algorithms are usually harder to implement. From another point of view, which
algorithm to choose depends on the type and the size of the problem. Generate and test
search is more suitable for small problems with all states having same weight. On the
other hand, best-first is more appropriate for problems where the states are associated
with some additional information that affect the search. A combination of two or more
search algorithms is used to benefit from the advantages of each of them and minimize the
effect of the disadvantages.
REFERENCES:
Joseph P. Bigus and Jennifer Bigus (1998). Constructing Intelligent Agents with Java.
Wiley Computer Publishing. New York, N.Y.
Copyright (c) Tony Abou-Assaleh 1999.
|
