ERA

Download the full-sized PDF of Efficiently Searching the 15-PuzzleDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3KR2G

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Efficiently Searching the 15-Puzzle Open Access

Descriptions

Author or creator
Culberson, Joseph
Schaeffer, Jonathan
Additional contributors
Subject/Keyword
A* algorithm
iterative deepening improvement
algorithm efficiency
Type of item
Computing Science Technical Report
Computing science technical report ID
TR94-08
Language
English
Place
Time
Description
Technical report TR94-08. The A* algorithm for single-agent search has attracted considerable attention in recent years due to Korf's iterative deepening improvement (IDA*). The algorithm's efficiency depends on the quality of the lower bound estimates of the solution cost. For sliding tile puzzles, reduction databases are introduced as a means of improving the lower bound. The database contains all solutions to the subproblem of correctly placing N tiles. For the 15-Puzzle, IDA* with reduction databases (N=8) are shown to reduce the total number of nodes searched on a standard problem set of 100 positions by over 1000-fold. With the addition of transposition tables and endgame databases, an improvement of over 1700-fold is seen.
Date created
1994
DOI
doi:10.7939/R3KR2G
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-29T15:44:26.278+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 402197
Last modified: 2015:10:12 13:51:57-06:00
Filename: TR94-08.pdf
Original checksum: 17393c8225d3749a87a640be67a26f09
Well formed: true
Valid: true
Page count: 19
Activity of users you follow
User Activity Date