dmeoli / PBeFS / 40418248576

push

github

The pattern databases of the sliding-tile puzzles (PatternDatabase.h): TilePattern ranks the placements of a pattern in lexicographic order, PatternTable holds the distances of its abstraction with the blank ignored or minimized, built by a breadth-first search by layers on the workers of any runtime (two bits per state with the blank minimized), AdditivePDB sums the tables of a partition (7-8, 5-5-5 and 6-6-3 of the 15-puzzle, 6-6-6-6 of the 24-puzzle) and takes the maximum with the reflection about the main diagonal, and SlidingTilePDB is SlidingTile with that heuristic; the entries in bytes, in 4 bits as the excess over the Manhattan distance, modulo 3 in 1.6 bits and in 1 bit (the heuristic of a successor from that of its parent, the initial one from the residues alone), compressed by the least excess of groups of ranks, and, with the structures of ADS, by rank and select over the nonzero excesses; the tables saved to files with a versioned header and a checksum, and kept in a cache directory; the tests pdb and pdb-search check the tables against a search of the abstraction written apart, the admissibility and the consistency on all the states of the 8-puzzle, the encodings, the reflection, the files and A*, HDA* and SPA* on the instances of Korf; tools/PDBBench and tools/bench/pdb.sh measure the tables and the expansions; the theory in docs/theory/pattern-databases.md

612 of 650 new or added lines in 1 file covered. (94.15%)

4179 of 4398 relevant lines covered (95.02%)

23183007.61 hits per line