Chapter 4: Informed Search Methods
Page 1 of 1 • Share •
Chapter 4: Informed Search Methods
Chapter 4
1. What is heuristics
2. Differentiate bestfit search, greedy search, A* search.
1. What is heuristics
2. Differentiate bestfit 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)
blacksnake Posts : 18
Join date : 20101120
Age : 29
Location : Davao
What is Heuristic
Heuristic is any advice tha is often effective, but isnt guaranteed to work in every case.
http://www.springerlink.com/content/q0v51v7j311um169/
http://www.springerlink.com/content/q0v51v7j311um169/
fjsanico Posts : 6
Join date : 20110210
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
Bestfirst 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/Bestfirst_search
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/A*_search_algorithm
www2.cs.uh.edu/~ceick/ai/search6.ppt
Bestfirst search’s idea: use an evaluation function f (n) for each node. Order the nodes in fringe in decreasing order of desirability while Greedy bestfirst search expands the node that appears to be closest to goal and lastly, A* search’s idea: avoid expanding paths that are already expensive.
References:
http://en.wikipedia.org/wiki/Heuristic_%28computer_science%29
http://searchsoftwarequality.techtarget.com/definition/heuristics
Bestfirst 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/Bestfirst_search
http://en.wikipedia.org/wiki/Greedy_algorithm
http://en.wikipedia.org/wiki/A*_search_algorithm
www2.cs.uh.edu/~ceick/ai/search6.ppt
Bestfirst search’s idea: use an evaluation function f (n) for each node. Order the nodes in fringe in decreasing order of desirability while Greedy bestfirst search expands the node that appears to be closest to goal and lastly, A* search’s idea: avoid expanding paths that are already expensive.
aqua_pepper214 Posts : 7
Join date : 20110124
Age : 31
Location : Davao City
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 averagecase performance on a problemsolving task, but does not necessarily improve the worstcase performance[1]. In the specific area of search algorithms, it refers to a function that provides an estimate of solution cost.
Bestfit 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 bestfirst 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 bestfit, 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.
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 averagecase performance on a problemsolving task, but does not necessarily improve the worstcase performance[1]. In the specific area of search algorithms, it refers to a function that provides an estimate of solution cost.
Bestfit 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 bestfirst 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 bestfit, 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.
blacksnake Posts : 18
Join date : 20101120
Age : 29
Location : Davao
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 bestfit search, greedy search, A* search.
When we say "Bestfit 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
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 bestfit search, greedy search, A* search.
When we say "Bestfit 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
Honey Lynne Accion Posts : 8
Join date : 20101130
Re: Chapter 4: Informed Search Methods
 Heuristic relates to or uses a problemsolving 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.
 Bestfirst 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 "singleminded" 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 highercost path segment and traverses the lowercost path segment instead. This process continues until the goal is reached.
deyong Posts : 7
Join date : 20110124
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 experiencebased 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
Bestfirst 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
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 experiencebased 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
Bestfirst 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
blueacid Posts : 10
Join date : 20110314
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 'nonrecoverable'. They are ideal only for problems which have 'optimal substructure.
the last one, A*(pronounce as "A star") search uses a bestfirst search and finds the leastcost path from a given initial node to one goal node (out of one or more possible goals).
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 'nonrecoverable'. They are ideal only for problems which have 'optimal substructure.
the last one, A*(pronounce as "A star") search uses a bestfirst search and finds the leastcost 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)
lizyl123 Posts : 7
Join date : 20110324
Similar topics
» Te Papa search
» Propagation of cuttings by hydroponic methods
» No new Fairy Tail chapter this week.
» December Sailor Moon Word Search!
» Naruto chapter 667 discussion 668 predictions.
» Propagation of cuttings by hydroponic methods
» No new Fairy Tail chapter this week.
» December Sailor Moon Word Search!
» Naruto chapter 667 discussion 668 predictions.
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum

