patternMinor
Optimal algorithm for signaling for help?
Viewed 0 times
optimalhelpalgorithmforsignaling
Problem
I was thinking about the following problem the other day:
You are stuck on a desert island with a battery-powered emergency radio. You know that if you feed enough power into the radio that you should be able to alert someone to your position. In fact, as soon as you provide the radio enough power to reach someone else, they'll respond back to you and send help.
The problem is that you don't know where anyone else is, so you have no idea how much power to feed into the radio. You can assume that the radio can transmit at power levels that are natural numbers.
What is the most power-efficient way to signal for help?
One inefficient solution to this would be to transmit at power $1, 2, 3, ...$ until you reach the necessary power $n$. This works, but it requires power usage $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$.
The algorithm I currently think is optimal is to instead transmit at power $1, 2, 4, 8, 16, ... $ until the necessary power $n$ is reached or exceeded. This requires power
$$1 + 2 + 4 + 8 + ... + 2^{\lceil \log_2 n \rceil} = 2^{\lceil \log_2 n \rceil + 1} - 1$$
which is somewhere between $2^{\log_2 n + 1} - 1 = 2n - 1$ and $2^{\log_2 n + 2} - 1 = 4n - 1$
My question is whether or not this is the optimal algorithm for solving this problem, given that $n$ is completely unknown. I can't seem to find a more efficient algorithm, nor can I find a proof that this is optimal.
Is there a better way to solve this problem? Or is this the optimal solution?
You are stuck on a desert island with a battery-powered emergency radio. You know that if you feed enough power into the radio that you should be able to alert someone to your position. In fact, as soon as you provide the radio enough power to reach someone else, they'll respond back to you and send help.
The problem is that you don't know where anyone else is, so you have no idea how much power to feed into the radio. You can assume that the radio can transmit at power levels that are natural numbers.
What is the most power-efficient way to signal for help?
One inefficient solution to this would be to transmit at power $1, 2, 3, ...$ until you reach the necessary power $n$. This works, but it requires power usage $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$.
The algorithm I currently think is optimal is to instead transmit at power $1, 2, 4, 8, 16, ... $ until the necessary power $n$ is reached or exceeded. This requires power
$$1 + 2 + 4 + 8 + ... + 2^{\lceil \log_2 n \rceil} = 2^{\lceil \log_2 n \rceil + 1} - 1$$
which is somewhere between $2^{\log_2 n + 1} - 1 = 2n - 1$ and $2^{\log_2 n + 2} - 1 = 4n - 1$
My question is whether or not this is the optimal algorithm for solving this problem, given that $n$ is completely unknown. I can't seem to find a more efficient algorithm, nor can I find a proof that this is optimal.
Is there a better way to solve this problem? Or is this the optimal solution?
Solution
Your problem is very similar to the well-known cow-path problem, though the details are a bit different. When talking about optimal algorithms, we are usually concerned with minimizing the competitive ratio (a concept from the field of online algorithms), which is the worst ratio between the solution produced by your algorithm and the one produced by the optimal algorithm (in this case, $n$). If your algorithm searches the sequence $a_1 < a_2 < \ldots$ then the competitive ratio is
$$ \sup_n \frac{\sum_{i\colon a_{i-1} < n} a_i}{n}. $$
(Here $a_0 = 0$.)
Suppose we're aiming for a competitive ratio of $C$ (your algorithm gives $C = 4$). Considering $n=1,a_1+1,a_2+1,\ldots$, we must have
$$
\begin{align*}
a_1 &\leq C, \\
a_1 + a_2 &\leq C(a_1 + 1), \\
a_1 + a_2 + a_3 &\leq C(a_2 + 1), \\
&\ldots
\end{align*}
$$
The classical solution to the cow-path problem (Searching in the plane) shows that $C \geq 4$, and so your algorithm achieves the optimal competitive ratio.
$$ \sup_n \frac{\sum_{i\colon a_{i-1} < n} a_i}{n}. $$
(Here $a_0 = 0$.)
Suppose we're aiming for a competitive ratio of $C$ (your algorithm gives $C = 4$). Considering $n=1,a_1+1,a_2+1,\ldots$, we must have
$$
\begin{align*}
a_1 &\leq C, \\
a_1 + a_2 &\leq C(a_1 + 1), \\
a_1 + a_2 + a_3 &\leq C(a_2 + 1), \\
&\ldots
\end{align*}
$$
The classical solution to the cow-path problem (Searching in the plane) shows that $C \geq 4$, and so your algorithm achieves the optimal competitive ratio.
Context
StackExchange Computer Science Q#12578, answer score: 3
Revisions (0)
No revisions yet.