Loading...
Please wait, while we are loading the content...
Similar Documents
Comparison and evaluation of a class of ida* algorithms (1994).
| Content Provider | CiteSeerX |
|---|---|
| Author | Wah, Benjamin W. Shang, Yi |
| Abstract | In this paper, we study the performance of various IDA*-style searches and investigate methods to improve their performance by predicting in each stage the threshold to be used for pruning. Without loss of generality, we consider minimization problems in this paper. We first present three models to approximate the distribution of the number of search nodes by lower bounds: exponential, geometric, and linear, and illustrate these distributions based on some well-known combinatorial search problems. Based on these distributions, we show the performance of an ideal IDA* algorithm and identify reasons why existing IDA*-style algorithms perform well. In practice, we will be able to know from experience the type of distribution for a given problem instance, but will not be able to know the parameters of this distribution until the instance is solved. Hence, we develop RIDA*, a method that estimates dynamically the parameters of the distribution, and predicts the best threshold to be used in ... |
| File Format | |
| Publisher Date | 1994-01-01 |
| Access Restriction | Open |
| Subject Keyword | Ida Algorithm Well-known Combinatorial Search Problem Problem Instance Minimization Problem Search Node Ida Style Algorithm Perform Ideal Ida Algorithm Various Ida Style Search |
| Content Type | Text |
