The idea is that smaller abstract state space sizes should be preferred but usually lead to larger branching factors. If there are different abstractions to choose from, a suggestion is to take those that have the smallest ratio of maximum node branching factor b max and abstract state space size | ϕ ( S ) |. In difference to the locality for delayed duplicate detection the locality for structured duplicate detection is defined as the maximum node branching factor b max = max v ∈ ϕ ( S ) | S u c c ( v ) | in the abstract state space ϕ ( S ). This gives rise to a different definition of locality, which determines a handle for the duplicate detection scope. Before expanding a bucket, not only the bucket itself, but all buckets that are potentially affected by successor generation have to be loaded and, consequently, fit into main memory. In difference to delayed duplicate detection, structured duplicate detection detects duplicates early, as soon as they are generated. A bucket now corresponds to the set of original states, which all map to the same abstract state.
4), such that for each pair of consecutive abstract nodes the pair of original nodes are also connected. Such hash projections are state space homomorphisms (as introduced in Ch. Structured duplicate detection incorporates a hash function that maps nodes into an abstract problem graph this reduces the successor scope of nodes that have to be kept in main memory.
Stefan Edelkamp, Stefan Schrödl, in Heuristic Search, 2012 8.7.2 Structured Duplicate Detection
0 kommentar(er)
