Which search algorithm will use a limited amount of memory in online search mention its name?
closed as unclear what you're asking by DuttaA, nbro, Neil Slater, Guilherme IA, DukeZhou♦ Nov 26 '18 at 2:02
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
The general relationship is that more state maintained by the search algorithm, the more memory it will. Of course, state is helpful in optimizing search strategy, so the minimizing of memory utilization may negatively impact the speed of the search.
The term online could mean several different things in this context, so this answer will not venture a guess.
Strictly speaking, no algorithm can limit the amount of memory to use for any practical search if the number of vertices in the search space can be arbitrarily large, particularly if cycles exist in the graph representing the search space. The memory requirement can be bounded as a function of search space metrics, however. This is one of the purposes of big-O notation and other techniques related to quantification of computing resources as a function of search space metrics.
The question included the request to mention the name of the algorithm. There is rarely one algorithm name to encapsulate all of the algorithms that fit such a broad requirement, and a name does not entirely describe an algorithm, since the best ones have several variants.
Only this general set of principles can be offered as an answer. More specificity would be as likely to lead the question author astray as to be helpful. There may be some tables posted that compare memory, CPU, and time resource utilization for particular data sets, but a different data set would produce a different set of table values.
With more details about the requirements of the search, some narrowing of algorithm choices could be possible. However, in the end, a run of some of the options may produce some unexpected results that would need investigation. For instance, it is not clear when the term online is used as to whether the state of the search space changes during the search, whether the value of particular findings change during the search, or whether the paths to the results are significant to the overall search objective.
With regard to the balance between memory utilization and search speed, look for algorithms that assess the likelihood of the paths during traversal efficiently and only store stronger indicators of likelihoods for paths not yet traversed.