Posts Tagged ‘Search Engines’

Best-First Search (Greedy Search)

September 4th, 2010 2 comments

Best-first search is a search algorithm, which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a “heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.”

Some authors have used “best-first search” to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths, which are judged closer to a solution, are extended first. This specific type of search is called greedy best-first search.

Efficient selection of the current best candidate for extension is typically implemented using a priority queue

Iterative Deepening Search

September 4th, 2010 2 comments

Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. On each iteration, IDDFS visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited, assuming no pruning, is effectively breadth-first.

Depth-Limited Search

September 4th, 2010 No comments

Like the normal depth-first search, depth-limited search is an uninformed search. It works exactly like depth-first search, but avoids its drawbacks regarding completeness by imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths or get stuck in cycles. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs.

Types of AI search Techniques

September 4th, 2010 No comments

Solution can be found with less information or with more information. It all depends on the problem we need to solve. Usually when we have more information it will be easy to solve the problem. There are two kinds of AI search techniques:

Uninformed search and Informed search.

Uninformed Search

Sometimes we may not get much relevant information to solve a problem. Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. If it is not there then we have to search the whole house to get it. The best solution would be to search in the places from the table to the wardrobe. Here we need to search blindly with fewer clues. This type of search is called uninformed search or blind search. There are two popular AI search techniques in this category:

Breadth first search and Depth first search.

Informed search

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 call heuristic search. Instead of searching one path or many paths, just like that informed search uses the given heuristic information to decide whether to explore the current state further. Hill climbing is an AI search algorithm that explores the neighboring states, chooses the most promising state as successor, and continues searching for the subsequent states. Once a state is explored, hill climbing algorithm simply discards 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.