Search Techniques In Artificial Technology Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Artificial Intelligence which is also known as AI is the intelligence of machines and the part of computer science that aims to create it. It is the science and engineering of creating intelligent machines, particularly intelligent computer programs. It is associated to the comparable task of using computers to comprehend human intelligence but Artificial Intelligence doesn't have to restrict itself to approaches that are naturally evident. Intelligence is the computational role of the ability to accomplish goals in the world.

In this assignment I wish to look at the search techniques within Artificial Intelligence such as Breath First Search, Depth First Search and Heuristic Search. Search is the focal topic within Artificial Intelligence. In several problems the arrangement of steps required to resolve the problem is not known in advance and needs to be determined by logical trial and error of alternatives. Artificial Intelligence search is a smart method of deciphering problems in the field of Artificial Intelligence. Including some intelligence to the search techniques has been valuable. Many search techniques established in the area of Artificial Intelligence. Search has to do with finding your way around. We usually consider this by abstracting into a simple abstract world. When talking about search techniques in AI we mention a search/problem space and moves in this space. We talk about rules for navigating within the space and about a 'goal' state to reach. The states that can be reached are now and then referred to as children of a 'node'.

A problem space is an array of states and a set of operators. The operators map from one state to another. There will also be several more states that can be called initial states, several states which are needed to reach what is known as a goal state and there will be states in between initial states and goal states which are known as intermediate states. The solution to the particular problem is nothing but an order of operators that map an initial state to a goal state. This sequence forms a solution path. The shortest path from the initial state to the goal state is the best one to use. The shortest path has only limited operations compared to all other probable solution pathways. The solution route configures a tree like structure where each node is a state. So searching is simply exploring a tree from the root node.

A Solution may be found using less information or with the help of more information. It all depends mainly on the problem which you need to resolve. Typically when more information is available the easier it is to solve the problem. There are two varieties of Artificial Intelligence search techniques, these are uninformed search and informed search.

Occasionally enough relevant information is not available to solve a problem. For example you misplaced your car key and could not recall where you left them last, we have to search for the key with some information such as in which places we usually leave them. It may be the pocket of your jacket or the kitchen countertop. If it is not there then we have to search the house in its entirety to find them. The best solution would be to search in the places from the table to the wardrobe. Here we need to search blindly with no clues. This type of search is called uninformed search or blind search. There are two popular Artificial Intelligence search techniques in this group, they are known as Breadth First search and Depth First Search.

Breadth First Search (BFS), searches from the initial state breadth-wise. That is it searches all the states in the tree level by level. Once all the states in one level have been explored it will jump to the next level. After the solution is located the search will cease. The breadth first search is certain to find the solution if a solution exists. BFS will not get trapped exploring a blind alley. An alternative approach is to explore only one branch deeper until the solution is found or until there is no new state to explore and then start searching the adjoining level, this is known as Depth First Search (DFS).

1BFS Example

Depth First Search (DFS) can find the solution providing the solution exists in the first branch. If this is the case depth first search can find the solution rapidly. If the solution occurs in other branches further away, then there won't be much of a variance between depth first search and breadth first search. The difficulty that occurs with DFS is that it can get trapped in an indefinite loop. An alternative way would be to search in both directions. That is one search from initial state to goal state and another search from goal state to initial state. This technique is known as a bidirectional search. Uninformed search is also referred to as brute force search. A depth-first search is the most instinctive and simple strategy. It can well be implemented without a library but by a recursive descending purpose. The disadvantage of this certain strategy is it is not guarantee to find the best possible solution which generally is referred to as the lowest goal in the tree/graph. Even worse if the tree/graph to be searched has infinite depth it is probable that depth-first does not find the solution at all.

2DFS Example

*Breadth-first has the advantage over depth-first search that it guarantees to always find the best solution in the first try. It has no problems with multiple goals or inifite depth of the search space. The drawback is - additional to exponential time complexity - it has exponential space complexity in the worst case. A breadth-first strategy will check all nodes of a lower hierarchy before further descending to higher ones.

We can solve the problem in an efficient manner if we have relevant information, clues or hints. The clues that help solve the problem constitute heuristic information. So informed search is also called heuristic search. Instead of searching one path or many paths just like that informed search uses the given heuristic information to decide whether or not to explore the current state further. Hill climbing is an AI search algorithm that explores the neighboring states and chooses the most promising state as successor and continue searching for the subsequent states. Once a state is explored, hill climbing algorithm simply discard it. Hill climbing search technique can make substantial savings if it has reliable information. It has to face three challenges: foothill, ridge and plateau. Best first search is a heuristic search technique that stores the explored states as well so that it can backtrack if it realizes that the present path proves unworthy.

Heuristic search is an Artificial Intelligence search technique that employs heuristic for its moves. Heuristic is a rule of thumb that probably leads to a solution. Heuristics play a major role in search strategies because of exponential nature of the most problems. Heuristics help to reduce the number of alternatives from an exponential number to a polynomial number. In Artificial Intelligence, heuristic search has a general meaning, and a more specialized technical meaning. In a general sense, the term heuristic is used for any advice that is often effective, but is not guaranteed to work in every case. Within the heuristic search architecture, however, the term heuristic usually refers to the special case of a heuristic evaluation function. Heuristics are like tour guides. The time complexity of a heuristic search algorithm depends on the accuracy of the heuristic function.

There is nothing magical about a heuristic function. It must use only information that can be readily obtained about a node. Typically a trade-off exists between the amount of work it takes to derive a heuristic value for a node and how accurately the heuristic value of a node measures the actual path cost from the node to a goal. A standard way to derive a heuristic function is to solve a simpler problem and to use the actual cost in the simplified problem as the heuristic function of the original problem. A simple use of a heuristic function is to order the neighbors that are added to the stack representing the frontier in depth-first search. The neighbors can be added to the frontier so that the best neighbor is selected first. This is known as heuristic depth-first search. This search chooses the locally best path, but it explores all paths from the selected path before it selects another path. Although it is often used, it suffers from the problems of depth-fist search.

Another way to use a heuristic function is to always select a path on the frontier with the lowest heuristic value. This is called best-first search. It usually does not work very well; it can follow paths that look promising because they are close to the goal, but the costs of the paths may keep increasing.

A* algorithm is a typical heuristic search algorithm, in which the heuristic function is an estimated shortest distance from the initial state to the closest goal state, and it equals to traveled distance plus predicted distance ahead.