Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Heuristics

Heuristics

Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...

The Availability Heuristic

The Availability Heuristic

A heuristic is a general problem-solving framework (Tversky & Kahneman, 1974). You can think of these as mental shortcuts that are used to solve problems. Different types of heuristics are used in different types of situations, and the impulse to use a heuristic occurs when one of five conditions is met (Pratkanis, 1989):

Statically Indeterminate Problem Solving

Statically Indeterminate Problem Solving

Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...

Theorems of Pappus and Guldinus: Problem Solving

Theorems of Pappus and Guldinus: Problem Solving

Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a cylinder...

Trial and Error and Algorithm

Trial and Error and Algorithm

A problem-solving strategy is a plan of action used to find a solution. Different strategies have distinct action plans. Trial and error involves trying different solutions until one works. For instance, to fix a broken printer, you might check ink levels, ensure the paper tray isn't jammed, and verify the printer's connection to your laptop. This method can be time-consuming but is commonly used. Thomas Edison, for example, used trial and error to find a suitable filament for the light bulb,...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by

Same author

[Association of KIR2DS4 and its variant KIR1D with the outcome after HLA- identical sibling hematopoietic stem cell transplantation].

Zhonghua xue ye xue za zhi = Zhonghua xueyexue zazhi·2015

Same author

Effects of Aspergillus niger fermented rapeseed meal on nutrient digestibility, growth performance and serum parameters in growing pigs.

Animal science journal = Nihon chikusan Gakkaiho·2015

Same author

Designing the shape evolution of SnSe2 nanosheets and their optoelectronic properties.

Nanoscale·2015

Same author

Donor Killer Immunoglobulin-Like Receptor Profile Bx1 Imparts a Negative Effect and Centromeric B-Specific Gene Motifs Render a Positive Effect on Standard-Risk Acute Myeloid Leukemia/Myelodysplastic Syndrome Patient Survival after Unrelated Donor Hematopoietic Stem Cell Transplantation.

Biology of blood and marrow transplantation : journal of the American Society for Blood and Marrow Transplantation·2015

Same author

Cardioprotective function of mitochondrial-targeted and transcriptionally inactive STAT3 against ischemia and reperfusion injury.

Basic research in cardiology·2015

Same author

Sulfur vacancy activated field effect transistors based on ReS2 nanosheets.

Nanoscale·2015

Same journal

Assessing the communication gap between AI models and healthcare professionals: Explainability, utility and trust in AI-driven clinical decision-making.

Artificial intelligence·2026

Same journal

Hierarchical clustering optimizes the tradeoff between compositionality and expressivity of task structures for flexible reinforcement learning.

Artificial intelligence·2023

Same journal

Rule-Enhanced Active Learning for Semi-Automated Weak Supervision.

Artificial intelligence·2022

Same journal

Learning in the Machine: Random Backpropagation and the Deep Learning Channel.

Artificial intelligence·2018

Same journal

Methods for solving reasoning problems in abstract argumentation - A survey.

Artificial intelligence·2015

Same journal

Modeling the Complex Dynamics and Changing Correlations of Epileptic Events.

Artificial intelligence·2014

See all related articles

Search research articles

Related Experiment Video

Updated: Jun 16, 2026

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

A comparative runtime analysis of heuristic algorithms for satisfiability problems.

Yuren Zhou¹, Jun He, Qing Nie

¹School of Computer Science and Engineering, South China University of Technology, Guangzhou 510640, China.

Artificial Intelligence

|February 4, 2010

Summary

This summary is machine-generated.

This study provides a rare theoretical comparison of heuristic algorithms for the satisfiability problem (SAT). It reveals that algorithms like RandomWalk can have exponential or polynomial expected runtime, depending on the SAT instance.

More Related Videos

A Quantitative Fitness Analysis Workflow

A Quantitative Fitness Analysis Workflow

Published on: August 13, 2012

Related Experiment Videos

Last Updated: Jun 16, 2026

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

A Quantitative Fitness Analysis Workflow

A Quantitative Fitness Analysis Workflow

Published on: August 13, 2012

Area of Science:

Computer Science
Theoretical Computer Science
Artificial Intelligence

Background:

The satisfiability problem (SAT) is a fundamental NP-complete problem.
Heuristic algorithms are widely used for SAT, but rigorous theoretical comparisons are scarce.
Existing research often focuses on experimental performance rather than theoretical runtime analysis.

Purpose of the Study:

To theoretically analyze and compare the expected runtime of three basic heuristic algorithms for SAT: RandomWalk, (1+1) EA, and a hybrid algorithm.
To investigate the theoretical performance bounds of these algorithms on different types of SAT instances.
To address the lack of rigorous theoretical analysis in the field of SAT heuristic algorithm comparison.

Main Methods:

Runtime analysis of RandomWalk, (1+1) EA, and hybrid algorithms.
Theoretical examination of algorithm performance on specific 2-SAT instances.
Derivation of expected runtime upper bounds for RandomWalk on k-SAT (k >= 3).

Main Results:

The expected runtime for these heuristic algorithms can vary between exponential and polynomial time.
The performance of each algorithm differs based on the specific SAT instance.
An expected runtime upper bound of O((k-1)n) for RandomWalk on k-SAT (k >= 3) was demonstrated.
A k-SAT instance with a Theta((k-1)n) expected runtime bound was presented.

Conclusions:

Heuristic algorithms for SAT exhibit diverse theoretical runtimes, ranging from polynomial to exponential.
Algorithm choice and its theoretical efficiency are highly dependent on the characteristics of the SAT instance.
The theoretical analysis provides crucial insights into the scalability and limitations of common SAT heuristics.