| 000 | 02187nam a22001697a 4500 | ||
|---|---|---|---|
| 003 | OSt | ||
| 005 | 20220107122808.0 | ||
| 008 | 160301b xxu||||| |||| 00| 0 eng d | ||
| 040 | _c | ||
| 100 |
_aKarthik Manogaran (92213006) _98303 |
||
| 245 | _aHeuristically guided bi-directional search in real-time for solving problems of discrete optimization | ||
| 502 |
_bMaster of Science in Computational Science _c2013-2015 _dEXT _eT.K Manoj Kumar _fAmbuj Mahanti (MIS Group) _g"Indian Institute Of Management, Calcutta" |
||
| 520 | _aFor very long time, searching techniques such as A* and IDA* have been used extensively. Search algorithms are widely used in real world problems like Combinatorial Auctions, Flow Shop Scheduling, Robot Navigation, etc. All these applications of heuristic search require optimal solutions. As such, the search technique should be very efficient. The Sliding Tiles Problem of 15-Puzzle has been used as a test-bed for a long time. These algorithms work fine for problems like 15-puzzle problem. However, the standard heuristic that is used for these algorithms the Manhatan heuristic is not the best possible heuristic as it does not account for interaction of tiles. While it would be impossible to account for all tile interactions the Disjoint Additive Pattern Database Heuristic provides us with a better heuristic than Manhattan thereby reducing the number of nodes explored for finding solution.This could be of particular effect on larger instances of the n-puzzle, such as 24-puzzle problem where standard algorithms have proved to be unsuccessful. A*requires huge amount of memory, while IDA* requires huge amount of time. In this project, a modified version of Bidirectional search has been taken into consid-eration which gives near optimal solution using less time and space. The performance of this search has been compared with the performance of IDA* search. We have taken 15-puzzle into consideration along with Additive Pattern Database heuristic. We have also used a Block depth first search method to find near optimal results for 24-puzzle problems. | ||
| 650 |
_aTHEORY OF COMPUTATION _98304 |
||
| 650 |
_aLOGIC _98305 |
||
| 942 |
_2ddc _cPR |
||
| 999 |
_c4936 _d4936 |
||