Which search algorithm will use a limited amount of memory in online search mention its name?

  • 1
    $\begingroup$ This question does not give enough detail to figure out what you are asking. Could you give some details of your search problem, and any other constraints. What do you mean by "limited"? Random search will give you very good memory properties O(1), but has very high time cost and is not suitable for fully optimising large combinatorial problems (O(N!) in time for combinatorial problems). $\endgroup$ – Neil Slater Nov 25 '18 at 9:44

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.