On the Optimal Efficiency of A* with Dominance Pruning
Authors: Álvaro Torralba12007-12014
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We extend this analysis for A with dominance pruning, which exploits a dominance relation to eliminate some nodes during the search. We show that the expansion order of A is not necessarily optimally efficient when considering dominance pruning with arbitrary dominance relations, but it remains optimally efficient under certain restrictions for the heuristic and dominance relation. Our theoretical analysis concludes that, in terms of node expansions using dominance pruning is strictly better than not using dominance. |
| Researcher Affiliation | Academia | Alvaro Torralba Department of Computer Science, Aalborg University, Denmark alto@cs.aau.dk. Alvaro Torralba was employed by Saarland University and the CISPA Helmholtz Center for Information Security during part of the development of this paper. |
| Pseudocode | Yes | Algorithm 1: Replace |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not describe experiments performed on a specific dataset, thus no dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits, thus no specific dataset split information is provided. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for any experiments mentioned. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers needed to replicate the work. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |