Heuristic algorithm - Revision history

Jlwoodwa: +rcat

2024-05-04T00:17:02Z

+rcat

← Previous revision		Revision as of 00:17, 4 May 2024
Line 1:		Line 1:
	#REDIRECT [[Heuristic (computer science)]]		#REDIRECT [[Heuristic (computer science)]]

			{{rcatsh\|
			{{r hist}}
			}}

Ruud Koot: ←Redirected page to Heuristic (computer science)

2012-11-22T18:48:54Z

←Redirected page to Heuristic (computer science)

← Previous revision		Revision as of 18:48, 22 November 2012
Line 1:		Line 1:
	#REDIRECT [[~~Metaheuristic~~]]		#REDIRECT [[Heuristic (computer science)]]

Optimering: Redirected to metaheuristic. Please see discussion-page for details.

2010-05-16T13:40:11Z

Redirected to metaheuristic. Please see discussion-page for details.

← Previous revision		Revision as of 13:40, 16 May 2010
Line 1:		Line 1:
			#REDIRECT [[Metaheuristic]]
	{{inline\|date=March 2010}}
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. It may find acceptably good solutions to a problem yet lack proof that the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

	Several heuristic methods are used by [[antivirus software]] to detect viruses and other malware. Different heuristic methods are used in [[Video game\|computer games]] etc.

	[[Judea Pearl]] states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches<ref>{{cite book
	\|first=Judea
	\|last=Pearl
	\|authorlink=Judea Pearl
	\|publisher=Addison-Wesley Pub
	\|date=April 1984
	\|title=Heuristics
	\|isbn=0201055945
	}}</ref>.

	Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, such [[pathological (mathematics)\|pathological]] instances might never occur in practice because of their special structure. Therefore, the use of heuristics is very common in real world implementations. For many practical problems, a heuristic algorithm may be the only way to get good solutions in a reasonable amount of time.
	There is a class of general heuristic strategies called [[metaheuristic]]s, which often use randomized search for example. They can be applied to a wide range of problems, but good performance is never guaranteed.

	==See also==
	*[[Heuristic function]]
	*[[Artificial Intelligence]]
	*[[Expert System]]
	*[[Logic Programming]]
	*[[Heuristic routing]]

	==References==
	<references/>

	* S. E. Goodman, S. T. Hedetniemi, ''Introduction to the Design and Analysis of Algorithms'', McGraw-Hill, 1977.
	* [[Alfred V. Aho]], [[John E. Hopcroft]], [[Jeffrey D. Ullman]], ''Data Structures and Algorithms'', Addison-Wesley.


	[[Category:Algorithms]]
	[[Category:Heuristics]]

	[[ar:خوارزمية الكشف عن مجريات الأمور]]
	[[ca:Algorisme heurístic]]
	[[cs:Heuristické algoritmy]]
	[[de:Heuristik#Informatik]]
	[[es:Heurística (informática)]]
	[[fa:الگوریتم جستجوی کاشف]]
	[[it:Algoritmo euristico]]
	[[pt:Heurística (computação)]]
	[[ru:Эвристический алгоритм]]
	[[sr:Хеуристички алгоритам]]
	[[th:ศึกษาสำนึก]]
	[[tr:Sezgisel algoritma]]
	[[uk:Евристичний алгоритм]]
	[[zh:启发式搜索]]

Luckas-bot: robot Adding: ca:Algorisme heurístic

2010-04-05T23:44:52Z

robot Adding: ca:Algorisme heurístic

← Previous revision		Revision as of 23:44, 5 April 2010
Line 39:		Line 39:

	[[ar:خوارزمية الكشف عن مجريات الأمور]]		[[ar:خوارزمية الكشف عن مجريات الأمور]]
			[[ca:Algorisme heurístic]]
	[[cs:Heuristické algoritmy]]		[[cs:Heuristické algoritmy]]
	[[de:Heuristik#Informatik]]		[[de:Heuristik#Informatik]]

Tim32: Video game usage

2010-03-25T10:43:53Z

Video game usage

← Previous revision		Revision as of 10:43, 25 March 2010
Line 6:		Line 6:
	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.		For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

	Several heuristic methods are used by [[antivirus software]] to detect viruses and other malware.		Several heuristic methods are used by [[antivirus software]] to detect viruses and other malware. Different heuristic methods are used in [[Video game\|computer games]] etc.

	[[Judea Pearl]] states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches<ref>{{cite book		[[Judea Pearl]] states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches<ref>{{cite book

Rankiri: tag

2010-03-25T01:35:20Z

tag

← Previous revision		Revision as of 01:35, 25 March 2010
Line 1:		Line 1:
			{{inline\|date=March 2010}}
	{{refimprove}}
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

Rankiri: tag

2010-03-25T01:27:05Z

tag

← Previous revision		Revision as of 01:27, 25 March 2010
Line 1:		Line 1:
			{{refimprove}}
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

Brainfeeder at 00:54, 18 March 2010

2010-03-18T00:54:22Z

← Previous revision		Revision as of 00:54, 18 March 2010
Line 1:		Line 1:
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. It may find acceptably good solutions to a problem yet lack proof that the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.		Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. It may find acceptably good solutions to a problem yet lack proof that the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

72.164.148.45 at 16:27, 9 March 2010

2010-03-09T16:27:28Z

← Previous revision		Revision as of 16:27, 9 March 2010
Line 1:		Line 1:
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and ~~algorithms~~ with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. ~~Typically, it~~ may find acceptably good solutions ~~for~~ ~~which,~~ ~~however,~~ ~~there~~ ~~is no~~ proof the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.		Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. It may find acceptably good solutions to a problem yet lack proof that the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.		For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

72.164.148.45 at 15:25, 9 March 2010

2010-03-09T15:25:19Z

← Previous revision		Revision as of 15:25, 9 March 2010
Line 1:		Line 1:
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are ~~finding~~ [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals~~; for~~ ~~example~~, it ~~usually~~ ~~finds~~ ~~pretty~~ good solutions, ~~but~~ there is no proof the solutions could not ~~get~~ arbitrarily bad; or it ~~usually~~ ~~runs~~ reasonably quickly, but ~~there is~~ no argument that this ~~will~~ always be the case.		Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and algorithms with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. Typically, it may find acceptably good solutions for which, however, there is no proof the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.		For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

← Previous revision		Revision as of 16:27, 9 March 2010
Line 1:		Line 1:
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and ~~algorithms~~ with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. ~~Typically, it~~ may find acceptably good solutions ~~for~~ ~~which,~~ ~~however,~~ ~~there~~ ~~is no~~ proof the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.		Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. It may find acceptably good solutions to a problem yet lack proof that the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.		For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

← Previous revision		Revision as of 15:25, 9 March 2010
Line 1:		Line 1:
	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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.		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. Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources. Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of [[Computational complexity theory\|time, space]] ''etc.'') or at all.

	Two fundamental goals in computer science are ~~finding~~ [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals~~; for~~ ~~example~~, it ~~usually~~ ~~finds~~ ~~pretty~~ good solutions, ~~but~~ there is no proof the solutions could not ~~get~~ arbitrarily bad; or it ~~usually~~ ~~runs~~ reasonably quickly, but ~~there is~~ no argument that this ~~will~~ always be the case.		Two fundamental goals in computer science are to find [[algorithm]]s with [[mathematical proof\|provably]] <!-- *NOTE*: this REALLY means "provably". DO NOT change this to "probably". --> good [[Run time (computing)\|run time]]s and algorithms with provably good or <!--optimally-->[[Optimization (computer science)\|optimal]] solution quality. A heuristic is an algorithm that abandons one or both of these goals. Typically, it may find acceptably good solutions for which, however, there is no proof the solutions could not become arbitrarily bad; or it can run reasonably quickly, but with no foundational argument that this would always be the case.

	For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.		For instance, say you are [[Knapsack problem\|packing odd-shaped items]] into a box. Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.