| Article ID: | iaor1995938 |
| Country: | United States |
| Volume: | 42 |
| Issue: | 1 |
| Start Page Number: | 47 |
| End Page Number: | 52 |
| Publication Date: | Jan 1992 |
| Journal: | Information Processing Letters |
| Authors: | Sarkar U.K., Chakrabarti P.P., Ghose S., Desarkar S.C. |
| Keywords: | programming: branch and bound |
The Iterative Deepening A* (IDA*) algorithm often reexpands too many nodes while solving certain combinatorial problems. Algorithm IDA*-CR attempted to remedy this drawback. These algorithms require very little memory although much more is available in practice. This paper introduces an algorithm IDA*-CRM which shows how the available memory can be advantageously utilized in IDA*-CR in order to reduce the number of expanded nodes. IDA*-CRAM, an approximation scheme derived from IDA*-CRM, is also presented. Computational results are shown for the Flow-Shop Scheduling Problem.