PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 16496727

Solving combinatorial problems: the 15-puzzle.

Zygmunt Pizlo·Zheng Li
View original source ↗Export metadata ↓

Abstract

We present a series of experiments in which human subjects were tested with a well-known combinatorial problem called the 15-puzzle and in different-sized variants of this puzzle. Subjects can solve these puzzles reliably by systematically building a solution path, without performing much search and without using distances among the states of the problem. The computational complexity of the underlying mental mechanisms is very low. We formulated a computational model of the underlying cognitive processes on the basis of our results. This model applied a pyramid algorithm to individual stages of each problem. The model's performance proved to be quite similar to the subjects' performance.

Explore related subjects

HumansJudgmentProblem SolvingJournal ArticleResearch Support, U.S. Gov't, Non-P.H.S.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Zygmunt Pizlo, Zheng Li. 2005. Solving combinatorial problems: the 15-puzzle.. https://doi.org/10.3758/bf03193214

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2027

Global Genomic Surveillance.

Global genomic surveillance has emerged as a foundational pillar of public health in the twenty-first century, enabling real-time tracking of pathogen evolution and informing outbreak response. This chapter examines the strategic architecture of global genomic surveillance, focusing on its application to arboviruses such as chikungunya virus (CHIKV). It explores the integration of genomic data with epidemiological, clinical, and environmental information within a One Health framework, while addressing critical challenges in governance, equity, and interoperability. The discussion covers the entire genomic surveillance workflow, from sample collection and sequencing to bioinformatic analysis and phylogenetic inference, and highlights the transformative role of artificial intelligence (AI) in predictive surveillance. By analyzing global initiatives, operational barriers, and emerging technologies, this chapter underscores the necessity of sustainable, equitable, and interoperable genomic systems to proactively address current and future infectious disease threats.

Humans↗
PubMed2027

Systematic Dissection of Key Driver Perturbation Signatures in Single Cells via ECCITE-seq.

CRISPR screens, such as expanded CRISPR-compatible cellular indexing of transcriptomes and epitopes by sequencing (ECCITE-seq), enable the simultaneous measurement of transcriptomes, gRNA identity, and cell-surface protein expression at single-cell resolution to systematically interrogate gene function. This platform provides a powerful and scalable experimental approach for validating disease-associated regulators identified by large-scale association studies and other computational methods, including network-based analyses of multi-omics data. Here, as an example application, we describe an ECCITE-seq framework to characterize the transcriptomic consequences of perturbing multiple neuronal key driver genes associated with Alzheimer's disease (AD) in human-induced pluripotent stem cell (hiPSC)-derived neurons. More broadly, by integrating customized pooled gRNA libraries with different CRISPR effectors across multiple cell types, this approach allows for the assessment of the regulatory impact of candidate genes implicated in development and disease processes.

Humans↗
PubMed2027

Identification of Genome-Wide Chromatin Structural Aberration in Cancer by Hi-C Analysis.

Aberrant three-dimensional genome organization is a hallmark of cancer, often driving oncogene activation through mechanisms such as enhancer hijacking. High-throughput chromosome conformation capture (Hi-C) maps these interactions on a genome-wide scale. Unlike earlier dilution-based methods, in situ Hi-C performs proximity ligation within intact nuclei, minimizing random ligation noise and enabling fine-scale structure detection. This chapter describes an optimized in situ Hi-C protocol tailored for cancer cell lines using MboI digestion and biotin-mediated pull-down to generate high-complexity libraries. We further outline a computational workflow that extends beyond standard topological mapping of compartments and topologically associating domains to identify cancer-specific aberrations. Specifically, we focus on detecting chromosomal rearrangements (structural variants) and characterizing the distinct circular topology of extrachromosomal DNA. This integrated experimental and analytical framework provides the necessary tools to dissect the spatial dysregulation underlying tumor evolution.

Humans↗