We often find computers very handy tool when we need to solve mathematical global maximum and minimum searching problems.
Problem:
Given a machine with M memory, there are N commands need to be run on it. Running the ith command need R[i] memory, the result need O[i] memory to store and O[i] < R[i]. Design an algorithm to tell if the N commands can be successfully run on this machine. When it can, give the running sequence of the N commands.
Hypotheses:
if we sort R[i] - O[i] in descending order, then run the commands with the same sequence, then we can process the N commands, otherwise, we can't.
Proof:
The total space needed to run the ith command is:
A = (O[0] + O[1] + ... + O[i - 1] + R[i])
if A <= M, we can run the ith command, otherwise we can't.
After that, the total space needed to store the ith command's result is:
(O[0] + O[1] + ... + O[i - 1] + O[i])
Since R[i] > O[i], we have:
(O[0] + O[1] + ... + O[i - 1] + O[i]) < (O[0] + O[1] + ... + O[i - 1] + R[i]) < M
So we can definitely store it.
Now let's assume the theorem is true, and we have successfully run the kth command following descending order.
The space needed to run the (k + 1)th command is:
A = (O[0] + O[1] + ... + O[i - 1] + O[i] + O(i + 1)+ ... + O[k - 1] + O[k] + R[k + 1])
If A <=M, we are able to run the k + 1 command, otherwise A > M, we can't.
Next, let's prove that when we follow other sequences other than the descending order, the space needed to run the (k+1) command is larger than A. In other words, descending order is the global optimized sequence, if this don't work, no other sequence will do better.
In order to calculate the space needed for a random sequence, lets swap the (k + 1)th command with the ith command. The space needed for run them is:
B = (O[0] + O[1] + ... +O[i - 1] + O[k + 1] + O(i + 1) + ... + O[k - 1] + O[k] + R[i])
A - B = O[i] - O[k + 1] + (R[k + 1] - R[i]) = O[i] + R[k + 1] - (O[k + 1] + R[i])
because R[k + 1] - O[k + 1] < R[i] - O[i] according to the descending order, therefore
A - B = O[i] + R[k + 1] - (O[k + 1] + R[i]) < 0
A < B, A always have small memory consumption, so the descending order is the best sequence.
Proof done.
After the analysis, we handle the computer 2 arrays and a sorting problem to solve.
Hypotheses:
if we sort R[i] - O[i] in descending order, then run the commands with the same sequence, then we can process the N commands, otherwise, we can't.
Proof:
The total space needed to run the ith command is:
A = (O[0] + O[1] + ... + O[i - 1] + R[i])
if A <= M, we can run the ith command, otherwise we can't.
After that, the total space needed to store the ith command's result is:
(O[0] + O[1] + ... + O[i - 1] + O[i])
Since R[i] > O[i], we have:
(O[0] + O[1] + ... + O[i - 1] + O[i]) < (O[0] + O[1] + ... + O[i - 1] + R[i]) < M
So we can definitely store it.
Now let's assume the theorem is true, and we have successfully run the kth command following descending order.
The space needed to run the (k + 1)th command is:
A = (O[0] + O[1] + ... + O[i - 1] + O[i] + O(i + 1)+ ... + O[k - 1] + O[k] + R[k + 1])
If A <=M, we are able to run the k + 1 command, otherwise A > M, we can't.
Next, let's prove that when we follow other sequences other than the descending order, the space needed to run the (k+1) command is larger than A. In other words, descending order is the global optimized sequence, if this don't work, no other sequence will do better.
In order to calculate the space needed for a random sequence, lets swap the (k + 1)th command with the ith command. The space needed for run them is:
B = (O[0] + O[1] + ... +O[i - 1] + O[k + 1] + O(i + 1) + ... + O[k - 1] + O[k] + R[i])
A - B = O[i] - O[k + 1] + (R[k + 1] - R[i]) = O[i] + R[k + 1] - (O[k + 1] + R[i])
because R[k + 1] - O[k + 1] < R[i] - O[i] according to the descending order, therefore
A - B = O[i] + R[k + 1] - (O[k + 1] + R[i]) < 0
A < B, A always have small memory consumption, so the descending order is the best sequence.
Proof done.
After the analysis, we handle the computer 2 arrays and a sorting problem to solve.
Problem:
There are N repeating commands need to be run on M machines. Running a command on the ith machine need t[i] time. Design an algorithm to load-balancing the N commands to the M machines, so that the response time spent on finishing all the N commands is shortest.
Analyze:
We want the fast machines to handle more requests and the slower machines to handle fewer requests. The decision function changes after each request is taken. For example, after the fastest machine takes a request, it became the least favorite one for the next command, we then want to give the next request to any other machines to achieve global win. So the decision depends on the path.
Similar mathematical problems include:
Actually, algorithm text book try to solve this kind of problems all the time. Whenever such kind of problem is solved, the book gives us a new handy tool.
Analyze:
We want the fast machines to handle more requests and the slower machines to handle fewer requests. The decision function changes after each request is taken. For example, after the fastest machine takes a request, it became the least favorite one for the next command, we then want to give the next request to any other machines to achieve global win. So the decision depends on the path.
Similar mathematical problems include:
- calculate the surface energy after N atoms are deposited onto a material surface. The surface contour is irregular, so you can't even formulate the initial surface energy.
- calculate the money distribution after N dollars are put into an industry.
- calculate the population of sheep in a grass island after N years.
Theorem:
Assuming we can give the N commands to the M machines one at a time. At each step, we give the command to the machine that can achieves the shortest global finish time. After all the N commands are distributed, we then achieved the distribution that achieved the best global finish time.
Equivalent Theorem:
Assuming we can deposit N atoms to the M locations on the surface one at a time. At each step, the atom is deposit to the location that can achieve the global lowest surface energy. After all the N atoms are deposited onto the M locations on the surface, we then achieved the distribution that achieved the lowest global surface energy.
The second Theorem has been proved to be true. It is the same as the first Theorem.
Actually, algorithm text book try to solve this kind of problems all the time. Whenever such kind of problem is solved, the book gives us a new handy tool.
