Chapter 4: Informed Search Methods  Chapter 4: Informed Search Methods

Chapter 4
1. What is heuristics
2. Differentiate best-fit search, greedy search, A* search.

Last edited by blacksnake on Wed Feb 23, 2011 11:00 am; edited 1 time in total (Reason for editing : breakdown of questions) What is Heuristic

Heuristic is any advice tha is often effective, but isnt guaranteed to work in every case. heuristics and Types of Algo.

Heuristic - In computer science, a heuristic algorithm, or simply a heuristic, is an algorithm that is able to produce an acceptable solution to a problem in many practical scenarios, in the fashion of a general heuristic, but for which there is no formal proof of its correctness.

References:
http://en.wikipedia.org/wiki/Heuristic_%28computer_science%29
http://searchsoftwarequality.techtarget.com/definition/heuristics

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

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.

In computer science, A* (pronounced "A star") is a computer algorithm that is widely used in path finding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes.

References:

http://en.wikipedia.org/wiki/Best-first_search
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/A*_search_algorithm
www2.cs.uh.edu/~ceick/ai/search6.ppt

Best-first search’s idea: use an evaluation function f (n) for each node. Order the nodes in fringe in decreasing order of desirability while Greedy best-first search expands the node that appears to be closest to goal and lastly, A* search’s idea: avoid expanding paths that are already expensive.    Re: Chapter 4: Informed Search Methods

Heuristics

The said word is derived from the greek word which means "to find" or to "discover".That word said to be referred to any technique that improves the average-case performance on a problem-solving task, but does not necessarily improve the worst-case performance. In the specific area of search algorithms, it refers to a function that provides an estimate of solution cost.

Best-fit search

This search selects the best node first to traverse or expand next. When it does, it would be a straight march to the goal by choosing the best node that appears to be the best according to the evaluation function.

Greedy Search

Greedy search is one of the simpliest best-first search strategies by minimizing the estimated cost to reach a goal. To do so, the node whose state is judged to be closest to the goal state is always expanded first. Though this cost for most problems can be estimated. This search also applies cost estimates called heuristic function.

A* Search

This search applies an admissible heuristic, the function that never overestimates the cost to reach the goal and optimistic by nature in which they think the cost of solving the problem is less than it actually is.

Difference between those search methods (refer to best-fit, greedy and A*):

The difference is the use of function in order to reach the goal. Also the ways in reaching the goal and the way or formula in solving the problems with or without compromising other factors. Re: Chapter 4: Informed Search Methods

What is Heuristic?

Heuristic is something that pertains to person own understanding of how he or she will treat a certain problem and comes up with a solution.

http://en.wikipedia.org/wiki/Heuristic

Differentiate best-fit search, greedy search, A* search.

When we say "Best-fit search", the best place is considered since this is where the new data will be inserted. the given algorithm pertains to be best since it minimizes the wasted space at the end of the block being allocated. In other words, when space is minimized, more data can be allocated.

Greedy algorithm, on the other hand, is closely related to heuristic method in which making an optimal choice with hope of finding the global optimum. If ever global optimum yield for a given problem, it typically became the method of choice because it is faster than other optimization. Example of such greedy algorithms are Kruskal's algorithm, Prim's algorithm, Dijkstra's algorithm etc.

Lastly is the A* search algorithm to which is used in path finding and graph traversal. This type of algorithm achieves better performance when heuristic approach is used.

http://dictionary.reference.com/browse/Best+Fit
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/A*_search_algorithm Re: Chapter 4: Informed Search Methods

• Heuristic relates to or uses a problem-solving technique in which the most appropriate solution of several found by alternative methods is selected at successive stages of a program for use in the next step of the program.

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

On the other hand, greedy search algorithm might also be called a "single-minded" algorithm or an algorithm that gobbles up all of its favorites first. The idea behind a greedy algorithm is to perform a single procedure in the recipe over and over again until it can't be done any more and see what kind of results it will produce. It may not completely solve the problem, or, if it produces a solution, it may not be the very best one, but it is one way of approaching the problem and sometimes yields very good (or even the best possible) results.

Finally, A* search algorithm differs from the other since follows a path of the lowest known cost, keeping a sorted priority queue of alternate path segments along the way. If, at any point, a segment of the path being traversed has a higher cost than another encountered path segment, it abandons the higher-cost path segment and traverses the lower-cost path segment instead. This process continues until the goal is reached. Heuristics and Search Algorithms

The word "heuristic" is derived from the Greek verb heuriskein, meaning "to find"
or "to discover." Archimedes is said to have run naked down the street shouting
"Heureka" (I have found it) after discovering the principle of flotation in his bath.
Later generations converted this to Eureka.

Heuristics refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a good enough solution, where an exhaustive search is impractical. Examples of this method include using a "rule of thumb", an educated guess, an intuitive judgment, or common sense. In more precise terms, heuristics are strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines.

Greedy Search
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.
For example, applying the greedy strategy to the traveling salesman problem yields the following algorithm: "At each stage visit the unvisited city nearest to the current city". In general, greedy algorithms are used for optimization problems.

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

A* Search
In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. A* achieves better performance (with respect to time) by using heuristics.

Basically Best Fit Search uses Greedy Algorithm. A* Search are uses Best Fit Search Algorithm.

References
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/Heuristic Heuristic

heuristic define in wikipedia.com is a technique designed to solve a problem that ignores whether the solution can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem. It is intended to gain computational performance or conceptual simplicity, potentially at the cost of accuracy or precision.

Best fit search on my own opinion, is an algorithm that search the most precise node chosen according to a specific rule.

while Greedy Search is an algorithm that can be characterized as being 'short sighted', and as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure.

the last one, A*(pronounce as "A star") search uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

Last edited by lizyl123 on Thu Mar 24, 2011 10:31 pm; edited 1 time in total (Reason for editing : no title) Re: Chapter 4: Informed Search Methods 