Meida*

From Wikipedia, the free encyclopedia

This page is a candidate to be copied to Wikibooks using the Import process. If the page can be re-written into an encyclopedic article, please do so and remove this message. Before you move this content to Wikibooks, verify that it conforms to Wikibooks policies of acceptable content at What is Wikibooks? Often content unacceptable to Wikipedia may not be acceptable on Wikibooks either; facilitate the copying of this article by listing it on Wikibooks:Requests for Import.

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style.

[edit] Memory extended IDA*

In situations where the main memory is too small to hold all the nodes reached by IDA* MEIDA* can be used.

This algorithm runs in two steps:

First step:

Fill priority queue D with at most m nodes running IDA*

Second step:

 expand the minimum from D and insert its successors  into D if
   - D is not full
   - and f value of successor ≤ maximal f value in d
 continue until D becomes empty or goal found

The last expanded nodes f value is the threshold for the next IDA* run.

Complexity: Expands at most O(n+m+n²/m) nodes