1
$\begingroup$

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.

Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 : \sqrt{x^2+y^2+z^2} \leq r\}.$$

An obvious approach would be this: first, list all integers between $0$ and $r$; these become our $x$-values. Then, for each $x$-value, list all integers between $0$ and $\sqrt{r^2-x^2}.$ These become our $y$ values. Then, for each $(x,y)$ pair, list all integers between $0$ and $\sqrt{r^2-x^2-y^2}$. These become our $z$ values. We can visualize this process as a tree; the branches of the tree are the elements of $C(r)$.

A similar approach can be applied to solve the Knapsack problem a little quicker than brute force. Begin by forgetting the value of each item and just focusing on its weight. Now go through the items from left to right, bifurcating each node into two as you go, so that one edge corresponds to "take the item" and the other corresponds to "don't take the item." If taking the item would send you overweight, you refrain from adjoining the edge that corresponds to taking the item, but you still adjoin the one corresponding to not taking the item. In the end, we get a binary tree whose branches can be viewed as subsets of the set of items, which ultimately means fewer numbers that need comparing.

Well, I can see my computer running out of memory pretty quickly trying to do this - I'm sure there's better approaches out there - but nonetheless, if there's a name for this kind of thing, I'd like to know it.

$\endgroup$
3
$\begingroup$

Your technique is known as exhaustive search (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are several possible optimizations:

  • Tree pruning algorithms like A* avoid going through paths which are known to be suboptimal.
  • Greedy algorithms, when they apply, are able to make the correct choice at each step without going over all possibilities.
  • Dynamic programming corresponds, morally, to exploring a DAG instead of a tree, thus reducing the number of vertices explored. (The actual details are rather different.)
$\endgroup$
  • $\begingroup$ Surely this is more efficient than brute-forcing it? We did brute-force in class; for Knapsack, it was described as checking all $2^n$ possibilities, where $n$ is the number of items. The tree method would be quicker than this, right? $\endgroup$ – goblin Sep 6 '17 at 1:40
  • $\begingroup$ Yes, you are doing some pruning. $\endgroup$ – Yuval Filmus Sep 6 '17 at 5:29
  • $\begingroup$ Okay, so wouldn't that be non-exhaustive then? In class, the phrase "exhaustive search" was described as basically synonymous with "brute force." $\endgroup$ – goblin Sep 6 '17 at 6:04
  • $\begingroup$ You can call it "Goblin search" if it makes you feel better. $\endgroup$ – Yuval Filmus Sep 6 '17 at 6:38
  • $\begingroup$ Haha okay. The phrase "exhaustive search" is fine with me, so long as it doesn't suggest that we're literally considering every possible solution. If I understand you correctly, it doesn't suggest this, and therefore encompasses the kinds of algorithms described in my question. $\endgroup$ – goblin Sep 6 '17 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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