"GREEDY METHOD"
A. Understanding the Greedy Method
The Greedy method is an algorithm that forms a step-by-step solution by looking for a temporary maximum value at each step. This temporary maximum value is known as local maximum. In most cases, this method will not produce the most optimal solution, but usually this method provides a solution that approaches the optimum value in a fairly fast time.
B. Main Principles of the Greedy Method
The main principle of this method is "take what you can get now!". The purpose of the principle is that at each step in the greedy method, we take the most optimal decision for that step without regard to the consequences in the next step.
C. General Scheme of the Greedy Method
The greedy method is composed by the following elements:
1. Association of candidates
Contains the elements forming the solution.
2. Set of solutions
Contains selected candidates as a solution to the problem
3. Selection function (selection function)
Choosing the most likely candidate to reach the optimal solution. Candidates who have been selected in a step are never considered again in the next step.
4. Feasible function
Checking whether a candidate has been chosen can provide a feasible solution, namely the candidate Together with the set of solutions that have been formed do not violate the solution, while the candidate who is not worth throwing away and never considered again.
5. Objective function
A function that maximizes or minimizes the value of a solution (eg Length of path, profit, etc.).
D. Problems that can be solved with the Greedy Method
The greedy method can be used to resolve the following problems:
1. Optimal Storage on Tapes Problems
How to optimize storage, so that the data stored can be optimally loaded.
Example problem:
There are 3 programs that will be stored in the storage media with a length of 5, 10, and 3. What is the optimal storage process with the greedy method.
Settlement:
1. Determine the value of length, time, and average time
There are 3 programs, for example the lengths L1, L2, and L3 with the value L1 = 5, L2 = 10, and L3 = 3
Time, here is not known, means that time does not affect the storage process, meaning there is no average time.
This means that in this case the effect is only the length of each data.
2. Sort storage by using factorial techniques according to the amount of data.
From the case it is known that the number of data (n) is 3, meaning that the combination required is n !, that is 3! = 3 * 2 * 1 = 6. So it takes 6 steps in the process of compiling it.
No
|
Order
|
D(L)
|
Total
|
1
|
1,2,3
|
5+(5+10)+(5+10+3)
|
38
|
2
|
1,3,2
|
5+(5+3)+(5+3+10)
|
31
|
3
|
2,1,3
|
10+(10+5)+(10+5+3)
|
43
|
4
|
2,3,1
|
10+(10+3)+(10+3+5)
|
41
|
5
|
3,1,2
|
3+(3+5)+(3+5+10)
|
29
|
6
|
3,2,1
|
3+(3+10)+(3+10+5)
|
34
|
Info. No:1 : Order 1 = 5
Order 1, 2 =5+10
Order 1,2,3 = 5+10+3
So, Total Order 1,2,3 = 5+(5+10)+(5+10+3)
3. From the above values, the minimum value is obtained
a. The first smallest value is 29, which is for the 3rd position in the first position
b. The second smallest value is 31, i.e. for the 1st position in the first position
c. The third smallest value is not 34 and 38, because the storage sequence in the 3rd and 1st positions has been represented by 29 and 31, so that for the third order is 41.
2. Knapsack Problem
How to determine the selection of goods from a set of goods where each item has its own weight and profit, so that from the selection of these items the maximum profit is obtained.
Example problem:
It is known that 3 items will be stored in a place that has a maximum capacity of 20 kg. the weight of each item is 18 kg, 15 kg and 20 kg where each item has a profit of 25, 24 and 15 respectively.
Solution: M-W
n = 3 -> objects (1,2,3) O 1 2 3 20-15 = 5
M = 20 kg P 25 24 15 5- 5 = 0
W = 18, 15, 10 W 18 15 10
P = 25, 24, 15 P / W 1.39 1.6 1.5
Probability 0 ≤ Xi ≤ 1 X 0 1 1/2
(X1 X2 X3)
Limiting function:
∑Xi.Wi = 1.15 + 1 / 2.10 = 15 + 5 = 20
Purpose function:
∑ Pi. Xi = 24.1 + 15.1 / 2 = 24 + 7.5 = 31.5
3. Minimum Spanning Tree Problem
A common problem with a minimum spanning tree is to look for the minimum cost of a spanning tree from each edge of a graph that forms a tree.
4. Shortest Path Problem
Is the search for the shortest distance from one location to another.
