Disjoint pattern database heuristics (Q5958199): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q126789310, #quickstatements; #temporary_batch_1719442853500 |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Depth-first iterative-deepening: An optimal admissible tree search / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Time complexity of iterative-deepening-\(A^{*}\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4739657 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126789310 / rank | |||
Normal rank |
Latest revision as of 01:18, 27 June 2024
scientific article; zbMATH DE number 1715194
Language | Label | Description | Also known as |
---|---|---|---|
English | Disjoint pattern database heuristics |
scientific article; zbMATH DE number 1715194 |
Statements
Disjoint pattern database heuristics (English)
0 references
3 March 2002
0 references
We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases [\textit{J. Culberson} and \textit{J. Schaeffer}, Comput. Intelligence 14, No. 3, 318-334 (1998)]. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.
0 references
problem solving
0 references
single-agent search
0 references
heuristic search
0 references
heuristic evaluation functions
0 references
pattern databases
0 references
sliding-tile puzzles
0 references
fifteen puzzle
0 references
twenty-four puzzle
0 references
Rubik's cube
0 references