Are pattern database values learned predictions?

In the classical approach, they are precomputed exact costs for abstract subproblems, used as bounds for the concrete problem.

Can disjoint variable groups always be added safely?

No. The action-cost treatment must justify additivity.

Does an admissible heuristic guarantee a solver returns an optimum by itself?

No. The search algorithm and its conditions must also support the required optimality guarantee.

AI Glossary / Data engineering and architecture / Intermediate

Disjoint pattern databases

Definition

Disjoint pattern databases are precomputed heuristic tables used in search problems, where suitable nonoverlapping subproblems provide lower-bound costs that can be added without overestimating the full solution cost. They are associated with optimal heuristic search, including sliding-tile puzzles. Here “database” means a lookup table of abstract problem costs, not a conventional business database or a collection of unrelated customer records.

What it means

Searching every possible sequence of moves can be expensive. A pattern database stores exact solution costs for a simplified version of the problem. During search, the current state is mapped to that abstraction and its stored cost is retrieved. Several carefully designed patterns can provide a stronger estimate together. The essential condition is justified cost accounting: simply choosing disjoint-looking variables does not automatically make the sum admissible.

How it works

Choose abstractions that retain selected parts of a problem and define how action costs are allocated. Precompute optimal costs in each abstract state space, often by working backward from abstract goals. For a concrete state, look up the relevant pattern costs and combine them using a proven rule. In the disjoint additive setting, action costs must not be counted more than the original action permits. A search algorithm then uses the combined lower bound. Table size, construction time, and lookup cost are important tradeoffs.

Three practical examples

Puzzle solving: an optimal solver divides selected tiles into groups and uses properly cost-accounted abstract distances to guide the search.
Planning research: a researcher evaluates whether a problem admits useful abstractions whose costs can safely be combined.
Algorithm education: students compare a weak lower bound with a pattern-based estimate and observe how a more informative admissible heuristic changes the states explored.

Think of it this way

Think of estimating a project's minimum work by studying separate parts, while carefully ensuring that no unit of work is charged twice. The analogy is limited because admissibility is a mathematical property of the search model and cost allocation. Informally declaring tasks “separate” is not enough; an action may affect several parts simultaneously and invalidate a naive sum.

Worked example

Suppose two valid abstract pattern tables return costs 4 and 3 for a particular state. If the cost-partitioning construction guarantees that their costs do not double-count real actions, the combined lower bound is 7. If the true remaining optimum is 9, the estimate is admissible and more informative than either component alone. Now consider a different construction where one real action of cost 1 solves a requirement in both abstractions, and each table charges the full 1. Summing gives 2 even though the concrete solution costs 1. That sum overestimates. The invented numbers illustrate why the additive proof matters; they are not measured values for a particular puzzle state.

Illustrative case study

Fictional example: Cedar Search builds a teaching solver for a small puzzle. The team first checks abstract costs against exhaustive solutions on manageable states. A proposed new partition produces an overestimate, revealing that the same move cost was charged in two patterns. Engineers correct the cost accounting before comparing search effort. This invented case illustrates validation of an admissible heuristic, not a claim that random testing replaces a proof or that every partition improves performance.

Common misconceptions and mistakes

Do not assume any two admissible heuristics can be added; their sum can overestimate. Taking their maximum is a different combination rule. Do not confuse disjoint patterns with independent business datasets. Also avoid assuming that a larger table is always worthwhile: it may exceed memory or add construction and access costs. A stronger heuristic can reduce search expansion yet fail to improve total runtime if its evaluation is too expensive for the workload.

Business use

The concept is most relevant to teams building specialized planning or search systems that require strong lower bounds and possibly optimal solutions. Assess whether the domain has reusable subproblem structure and whether precomputation can be amortized across searches. Measure memory, construction time, lookup time, and end-to-end search behavior. For general business AI users, the main lesson is that precomputed knowledge can guide search effectively when its guarantees and costs are understood; this is not a generic database-tuning technique.

Check your understanding

Two separate abstractions each charge one unit for the same real move, whose cost is one. Can their values be summed without further justification?

Answer: No. The sum may double-count that move and overestimate. A valid additive construction needs an appropriate cost partition or other proof.

Related terms

Admissible heuristic
Abstraction
Pattern database
A* search
cost partitioning
lower bound
optimal planning

Learn next

build a tiny state graph whose exact distances can be computed by hand. Define two abstractions and trace how each real action is charged. Compare the sum with the exact distances and identify the condition that makes the lower-bound argument valid.

Sources

Primary sources consulted: Korf and Felner, Disjoint Pattern Database Heuristics, https://tzin.bgu.ac.il/~felner/2002-2003/naij.pdf — search excerpt on disjoint subgoals and operator effects consulted; direct PDF retrieval timed out. Felner, Hanan, and Korf, Additive Pattern Database Heuristics, https://arxiv.org/abs/1107.0050 — author abstract excerpt consulted. Examples are original; full construction and editorial review remain pending.

Previous: Disfluency Next: Disjunction