Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Divide and Conquer -- If You're Patient Enough

February 09, 2012

Last week, I posed a problem: Given 2n points, each of which might be connected to any of the others, figure out if there is a path between two given points using no more than O(n) space, measured in n-bit words.

One reader claimed that recursion could not be used to solve this problem, because that would use more than O(n) space. However, this claim is not true if the recursion depth is limited to n, and each recursive call uses no more than a constant number of n-bit integers. What is true is that the common form of recursion, in which each call reduces the size of the problem by 1, is ruled out by the space constraints.

With this in mind, let's see if we can figure out how to solve the problem of determining whether there is a path from point

p to point q. Note that we cannot even store the path if there is one, because it might be longer than n elements; so we are limited to figuring out whether a path exists.

Our first observation is that if a path exists at all, then there must be a path with no more than 2n-1 steps. The reason is that there are only 2n distinct points, so any path with 2n or more steps must visit at least one point more than once. Moreover, the maximum length of the path gives a value that we can use to control recursion.

We can therefore revise our problem slightly: Instead of determining whether there is a path from p to q, we will try to determine whether there is a path from p to q that contains no more than k steps. We will use the notation path(p, q, k) to represent a function that determines whether there is a path from p to q with no more than k steps. Our original problem then becomes a call to path(p, q, 2n-1).

We can tackle the easy cases first. path(p, q, 0) is true if and only if p and q are the same point; path(p, q, 1) is true if path(p, q, 0) is true or there is a direct connection from p to q. Now we have to consider the more general case.

The usual way to solve a problem of this sort recursively is to look for a solution with a smaller value of k. In this case, we have already determined that we cannot use k-1 as the value for the recursive call, because that will cause a recursion depth of k, which will be greater than n. The next logical value to try is k/2. What would that value mean? It would mean that we are trying to get from p to q by getting halfway there (recursively), then getting the rest of the way there (also recursively). Dividing the problem in half this way is a promising approach, because it would limit the recursion depth to log2(k), which, of course, is n.

So we can now reformulate the problem: path(p, q, k) is true if and only if there exists a point r such that

  • There exists a path with no more than k/2 steps from p to r — i.e., path(p, r, k/2) is true.
  • There exists a path with no more than k-(k/2) steps from r to q — i.e., path(r, q, k-(k/2)) is true.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video