written 8.2 years ago by |
Optimal storage problem:
Input: We are given ‘n’ problem that are to be stored on computer tape of length L and the length of program i is Li
Such that 1 ≤i≤ n and Σ 1≤k≤j Li≤ 1
Output: A permutation from all n! For the n programs so that when they are stored on tape in the order the MRT is minimized.
Example:
Let n = 3, (l1, l2, l3) = (8, 12, 2). As n = 3, there are 3! =6 possible ordering.
All these orderings and their respective d value are given below:
Ordering | d (i) | Value |
---|---|---|
1, 2, 3 | 8 + (8+12) + (8+12+2) | 50 |
1, 3, 2 | 8 + 8 + 2 + 8 + 2 + 12 | 40 |
2, 1, 3 | 12 + 12 + 8 +12 + 8 + 2 | 54 |
2, 3, 1 | 12 + 12 +2 +12 + 2 + 8 | 48 |
3, 1, 2 | 2 + 2 + 8 + 2 + 8+ 12 | 34 |
3, 2, 1 | 2 + 2 +12 + 2 + 12 + 8 | 38 |
The optimal ordering is 3, 1, 2.
The greedy method is now applied to solve this problem. It requires that the programs are stored in non-decreasing order which can be done in O (nlogn) time.
Greedy solution:
i. Make tape empty
ii. Fori = 1 to n do;
iii. Grab the next shortest path
iv. Put it on next tape.
The algorithm takes the best shortest term choice without checking to see whether it is a big long term decision.
Algorithm:
For example, find an optimal placement for 13 programs on 3 tapes T0, T1 & T2 where the program are of lengths 12, 5, 8, 32, 7, 5, 18, 26, 4, 3, 11, 10 and 6.
Given problem:
Length | 12 | 5 | 8 | 32 | 7 | 5 | 18 | 26 | 4 | 3 | 11 | 10 | 6 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Program | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
We organize the program as:
Length | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 18 | 26 | 32 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Program | [8] | [9] | [1] | [5] | [12] | [4] | [2] | [11] | [10] | [0] | [6] | [7] | [3] |