Greedy A* and Algorithms need in those….

Greedy Search

Simply greedy search always choose to visit the candidate node with the smallest estimate. That which appears to be closest to goal.
Evolution function h(n)(heuristic) = estimate of cost from n to goal
E.g. hsld(n) = straight-line distance from n to goal.

In other words:
we find a search strategy that always selects the first feasible solution. First fit, or greedy, selection trivially prunes the candidate space. For problems with multiple choices, such as path finding, greedy selection prunes the search space by treating each choice as independent, even if choosing one option at choice  t n  constrains the option space at the next step t n+1 . It can be trivially shown that greedy approaches can result in suboptimal solutions.

A* Search

Greedy search minimises estimated cost to goal, and thereby reduces search cost, but is neither optimal nor complete. Uniform -cost search minimises path cost so far and is optimal and complete, but is costly.
Just add the two together to get estimate of total path length of solution as our evaluation function.

Evaluation function :
f(n)= g(n)+h(n)
here f(n)= estimated total cost of path through n to goal.
h(n) =  estimated cost to goal from n
g(n) = Cost so far to reach n.

Manhattan Distance:

Simply the Manhattan distance function computes the distance that would be travelled to get from one data point to the other if a grid-like path is followed. The Manhattan distance between two items is the sum of the differences of their corresponding components. So when we are using Manhattan distance in the A* search h(n) becomes The Manhattan distance.

IDA* search:

Simply IDA means depth-limited search to use f-cost limit, rather than depth limit.
Here in IDA* search:

Complete? YES
Optimal? YES
Space? Linear in path length
Time? time is not countable and it is not a good feature in this method.

In other words, IDA means IDA* is a variant of the A* search algorithm which uses iterative deepening to keep the memory usage lower than in A*. It is an informed search based on the idea of the uninformed iterative deepening depth-first search.

BFS:

“BFS” means Breadth First Search. Simply this contains a graph search algorithm that begins at the root node and explores all the neighbouring nodes. Then for each of those nearest nodes, it explores their unexplored neighbour nodes, and so on, until it finds the goal.

DFS:

DFS means, Depth First Search (DFS) searches deeper into the problem space. Breadth-first search always generates successor of the deepest unexpanded node. Depth First Search uses last-in first-out stack for keeping the unexpanded nodes. More commonly, depth-first search is implemented recursively, with the recursion stack taking the place of an explicit node stack.

In other words, Depth-first search is an algorithm for traversing or searching a treetree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s