Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search
Authors: Richard Valenzano, Nathan Sturtevant, Jonathan Schaeffer
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the heuristic is admissible or inadmissible, though if the heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A . We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. |
| Researcher Affiliation | Academia | Richard Valenzano University of Alberta valenzan@ualberta.ca; Nathan R. Sturtevant University of Denver sturtevant@cs.du.edu; Jonathan Schaeffer University of Alberta jonathan@ualberta.ca |
| Pseudocode | Yes | Pseudocode for this framework is shown in Algorithm 1 |
| Open Source Code | No | The paper does not provide any information about open-source code for the described methodology. |
| Open Datasets | Yes | consider the use of WA on the 35, 360 pathfinding problems from the 10 8-connected, 512 512 maps with 40% random obstacles given by Sturtevant (2012). |
| Dataset Splits | No | The paper describes using a set of pathfinding problems from Sturtevant (2012) for evaluation but does not specify any training, validation, or test splits for these problems. |
| Hardware Specification | No | The paper does not provide any details regarding the hardware specifications used for the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies used in the experiments. |
| Experiment Setup | No | The paper mentions characteristics of the problems (e.g., 'weight 10 WA', 'octile heuristic') but does not provide specific experimental setup details such as hyperparameters, learning rates, or batch sizes. |