3
$\begingroup$

I have extensively researched now for three days straight trying to find which algorithm is better in terms of which algorithm uses up more memory. I know uninformed algorithms, like depth-first search and breadth-first search, do not store or maintain a list of unsearched nodes like how informed search algorithms do. But the main problem with uninformed algorithms is they might keep going deeper, theoretically to infinity if an end state is not found but they exist ways to limit the search like depth-limited search.

So, am I right in saying that uninformed search is better than informed search in terms of memory with respect to what I said above?

Can anyone provide me with any references that show why one algorithm is better than the other in terms of memory?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Uninformed Search Techniques

Breadth-First Search needs to store a frontier of nodes to visit next (where "visit" basically means: see if it's the goal, generate its children and add to frontier otherwise). You can visualize the memory requirements of this as a pyramid; initially, you just have the root node in there. As the search process continues and you keep going further down, it will become wider and wider (more memory required). The amount of memory required in the worst case to find a node at depth $d$ can be expressed as $O(b^d)$, where $b$ is the branching factor (see details here). Intuitively, whenever you go one level deeper, your memory requirements multiply by a factor of $b$ (your pyramid becomes $b$ times wider; actually this means pyramid is not quite the right shape, it should rapidly curve outwards and become wider much faster than a triangle/pyramid would).

Depth-First Search also stores a frontier (or stack in the case of DFS) of nodes to visit next. However, in the case of DFS, this generally grows less quickly. Whenever you visit a node (pop it off of the stack), you generate all of its children and push them on top of the stack. However, whereas BFS would then continue "to the right" by visiting a relatively "old" node and generating all of its children again, DFS continues by going "down" and visiting one of the children that only just got pushed onto the stack. Once DFS has finished a part of the search tree (you can visualize this in your head as DFS having completed searched for example the left half of the pyramid), that entire section no longer needs to be stored in memory. Assuming you have a search tree of finite depth $d$, the worst-case space complexity is $O(bd)$ (you have to search one path all the way down to a level of $d$, and for each of those levels have $b$ nodes in the stack).


Note that, based on the above, it is not sufficient to characterize your comparison as "uninformed" vs "informed" search. We've only just looked at uninformed search techniques, and already have two different memory requirements.

In the above, I also did not consider subtleties such as the question of whether or not you're additionally memorizing which nodes of a graph you have already previously visited so that you can avoid visiting them again. This is not necessary in a tree, but may be necessary in a graph with cycles.


Informed Search Techniques

A* is probably one of the most canonical examples of informed search algorithms. In terms of worst-case memory requirements, it's really similar to BFS; it also stores a frontier of nodes to visit next, but prioritizes those based on some estimate of "goodness" rather than Breadth-First order. In cases where the information you're using (typically a combination of known/incurred costs + heuristic estimate of future costs) is of extremely poor quality, this can regress to the level of Breadth-First Search, so the worst-case space complexity is the same as that for BFS (see details). In practice, if you have high-quality information (good heuristics), the memory requirements will be much better though; in the case of an ideal/perfect heuristic, your search algorithm will pretty much go directly to the goal and hardly require any memory.

There is also an algorithm called Iterative Deepening A* which has a much better space complexity, at the cost of often being slower. It is still an informed search algorithm using exactly the same kind of information as A* though.


So, really, memory requirements cannot be characterized in terms of informed vs. uninformed search; in both cases, there are algorithms that require a lot of memory, and algorithms that require less memory.

$\endgroup$
7
  • $\begingroup$ so if I get this correctly, might sound really dumb to you but I am trying to wrap my head around this. Lets say for eg. a simple game like chess or checkers. In order to use informed search algorithms you would need to acquire information, such has have players play the game. Then use this data to help you formulate your heuristic search algorithm/ informed search algorithm. So basically store the data you acquired from previous games.On the other hand uninformed algorithms like,Minimax is a dept-first algorithm,hence it has no prior knowledge of the game.Is this right or crap? $\endgroup$
    – JoeyB
    Commented Jul 17, 2018 at 17:56
  • $\begingroup$ @Joey The kinds of algorithms discussed here are not really directly applicable to something like playing chess or checkers. BFS/DFS/A*/etc. are generally used to search for a well-defined goal in some search space. For example, you can use them for path-finding, or puzzle-solving, that kind of thing. You could say that Minimax traverses nodes in a tree in the same order that Depth-First Search would, but it's still quite a bit different; Minimax is trying to learn values of all nodes it searches, it's not just searching for a particular goal and stopping when it's found the goal. $\endgroup$
    – Dennis Soemers
    Commented Jul 17, 2018 at 18:00
  • $\begingroup$ I suppose you could, very informally, say Minimax is uninformed since the order in which it traverses the search space is completely fixed ahead of time, and you could say it becomes informed once you add Move Ordering or replace it with something like Monte-Carlo Tree Search (where early iterations in some sense inform where later iterations will go). The uninformed/informed terminology really isn't often used in the context of these algorithms though. $\endgroup$
    – Dennis Soemers
    Commented Jul 17, 2018 at 18:10
  • $\begingroup$ the reason why I asked which was better uninformed or informed was because I thought Minimax and alpha beta pruning were related to BFS/DFS/IDDFS etc. I am getting even more confused because when one looks at Minimax and DFS you would say they that Minimax is based on DFS. In that DFS is the theoritcal background behind Minimax but no I see it is not,DFS is a totally different algorithm on its on. I am really sorry for this. Can you please point me in the right direction in terms of what algorithms I could use like Minimax to play checkers. I will delete this question. $\endgroup$
    – JoeyB
    Commented Jul 17, 2018 at 18:12
  • $\begingroup$ @Joey Like I mentioned in the previous comment, there is indeed some sort of relationship between DFS and Minimax in that they both would traverse a tree of nodes in the same order. As for game-playing, there really aren't many more options than Minimax (+ hundreds or thousands of variations on it), or MCTS, as discussed in your other question here: ai.stackexchange.com/q/7159/1641. I don't see the point in deleting this question by the way, the question itself still makes sense and may be valuable for future visitors to the site. $\endgroup$
    – Dennis Soemers
    Commented Jul 17, 2018 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .