This repository contains a comprehensive implementation and analysis of the Iterative Deepening A* (IDA*) search algorithm. IDA* is a memory-optimized version of the A* algorithm that combines depth-first search with iterative deepening and heuristic cost bounding, making it ideal for problems with large state spaces or memory constraints.
- Complete IDA* Implementation with Manhattan distance heuristic
- Memory-Efficient Design - O(d) space complexity vs A*'s O(b^d)
- Optimal Pathfinding for grid-based environments with obstacles
- Comprehensive Examples including IDA* vs A* comparison
- Performance Visualization with ready-to-use graphs
- Educational Documentation with algorithm explanations
IDA demonstrates significantly lower memory consumption due to its depth-first search nature, storing only the current path rather than all visited nodes.*
This visualization shows the trade-off between computation time and search efficiency across different problem complexities.
Illustrates how IDA progressively increases cost bounds across different maze configurations until a solution is found.*
1. Set initial threshold = heuristic(start, goal)
2. Perform depth-first search with f-cost ≤ threshold
3. If goal not found, increase threshold to min exceeded f-cost
4. Repeat until solution found or proven impossibleCourse: CoSc4011 – Introduction to Artificial Intelligence
Project: IDA* Pathfinding Algorithm – Implementation & Analysis
| No. | Student Name | ID Number |
|---|---|---|
| 1 | Yordanos Zewge | UGR/5072/15 |
| 2 | Samuel Ayine | UGR/6563/13 |
| 3 | Iyasu Walelign | UGR/6553/15 |
| 4 | Halid Zeyne | UGR/0755/15 |