If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.
You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

Pattern Databases

Page history last edited by Dmitry Sokolov 5 years, 10 months ago

Go:

Visual Taxonomy

Links

Hide/Show:

Taxonomy Path

List of Pattern Databases

Group Works Patterns

LIM Pattern Database

Gallery of Archetypes

Mental Models The Best Way to Make Intelligent Decisions 113 Models Explained

Wise Democracy Project Patterns

PSP Pattern Database

Mental Models I Find Repeatedly Useful

http://www.tomeri.org/InteractionPatterns.html

https://heuristicswiki.wikispaces.com/pattern+database

pattern database

Related Problems: Rubik's cube , N-Puzzle and Misspelling Type: Utility

`Description: A Pattern Database stores a collection of solutions to sub-problems that must be achieved to solve the problem.

While we normally think of a heuristic as a function computed by an algorithm, any function can also be computed by a table lookup, given sufficient memory. In fact, for reasons of efficiency, heuristic functions are commonly precomputed and stored in memory.

`Some Definitions:

A pattern: a partial specification of a permutation (or a state). In the case of the N-Puzzle, the tiles occupying certain locations are unspecified (blank).

A Target pattern: a partial specification of the goal state.

A pattern database (PDB): is the set of all patterns which can be obtained by permutations of a target pattern. For each pattern in the database we compute the distance (minimum number of moves) to the target pattern using retrograde analysis. This distance is the cost of the pattern. Note that the distance includes the cost of moving the unspecified tiles when required to place the specified ones, but does not require them to be in any particular order.

`Example: The Fringe database uses the Fringe target pattern (picture a). For a given arbitrary 15-Puzzle state (picture b), we map the current locations of tiles 3, 7, 11, 12, 13, 14, 15 and the empty tile into an index into the fringe database. The database will tell us the minimum number of moves required to correctly locate these 8 tiles. This is a lower bound on the remaining search effort. Once the fringe pattern has been achieved, all that is left to solve is an 8-Puzzle. Given more memory we can compute additional pattern databases from the remaining tiles.

(b) ---------------------------------------------------- (a)

31 moves needed to solve red tiles. 22 moves needed to solve blue tiles

Overall heuristic is maximum of 31 moves.

Note that the red pattern and the blue pattern are disjoint patterns, i.e. have no tiles in common. The maximum of the heuristic values of the disjoint patterns remains admissible and close to the actual optimal cost.

` This approach mimics the human strategy of "divide and conquer" – solving problems non-optimally by moving some of the elements into their correct locations thereby reducing the complexity of the remaining problem.

` A trivial example of the disjoint pattern database heuristic is Manhattan Distance , which view every tile as a single pattern database.

` On 15-puzzle, IDA* with a heuristic based on the disjoint pattern databases can optimally solve random 15 puzzle instances in less than 29 milliseconds on average. This is about 1700 times faster than with Manhattan Distance on the same machine.

Links