GREEDY PRINCIPLE

June 16, 2020
Hi friends mathematic.my.id..
on this occasion will be explained about the Greedy Principle.
The problem of optimization is a demanding problem optimum solution search. The optimum (best) solution is a valuable solution minimum or maximum set of alternative possible solutions. Example from Optimization issues are:
• Finding the shortest path from home to market
• Select activities to schedule the most productive activities
• Looking for a minimum step to sort the sequence of numbers
• Finding the maximum value of ...
• Finding the minimum value of ...

The greedy algorithm is the most popular method for solving optimization problem. At each step, we make local optimum choices (choices best at the moment) in the hope that the remaining steps lead to the optimum solution global (the best overall solution). Greedy algorithm always chooses the best choice of each step regardless of other choices. In other words, The greedy principle is take what you can get now.
For greedy to be used, an issue must have two things:
1. Optimal Sub-structures
The optimal solution to a problem contains the optimal solution to subproblems.
2. Greedy Property
If we choose the optimal choice at a step, and finish the rest then, we still find the optimal solution. (We don't need to reconsider the previous choice).
It should be noted that not all optimization problems can be solved by greedy algorithm. But if it can be used, the solution will be very easy. Will be explained several theories related to the greedy algorithm, along with examples of classic greedy issues.

Inequality Rearrangement
Rearrangement inequality is an inequality that is often used in make optimal permutations. For example
$a_1 \le a_2 \le ... \le a_n$ and
$b_1 \le b_2 \le ... \le b_n$ then:
$\sum \limits^{n}_{i=1} a_i.b_i \le \sum \limits^{n}_{i=1} a_i.b_{\sigma (i)} \le \sum \limits^{n}_{i=1} a_i.b_{n-i+1}$
Where $\sigma (i)$ is the $i$-number of random permutations of the number $b$.

Its use will be explained in the following example:
Suppose that in set $A$ there are $n$ numbers $A_1$, $A_2$, ..., $A_n$.
For example also in set B there are n other numbers $B_1$, $B_2$, ..., $B_n$.
We want to pair each number from set $A$ with exactly one number in set $B$, multiplying these two pairs of numbers and adding up the results.
Based on Inequality Rearrangement obtained:
* To get the maximum total, pair the largest number in $A$, with the largest number in $B$. Then, the second largest in $A$, with the second largest in $B$, and so on until the smallest number in $A$ is paired
with the smallest number in $B$.
* To get the minimum total, pair the largest number in $A$, with the smallest number in $B$. Then, the second largest in $A$, with the second smallest in $B$, and so on until the smallest number in $A$ is paired with
largest number in $B$.
Suppose set $A$ is {9, 6, 2, 5, 1}
Then, set $B$ is {8, 3, 4, 0, 7}
To get the sum of the multiplications of each pair maximum, sort both together (both up / down):
9$\quad$ 6$\quad$ 5$\quad$2 $\quad$ 1 $\quad$
8$\quad$7$\quad$4$\quad$3 $\quad$0
The result is: 9x8 + 6x7 + 5x4 + 2x3 + 1x0 = 72 + 42 + 20 + 6 + 0 = 140
This is an installation that produces a maximum total to get the sum of the multiplications of each pair maximum, sort both together (both up / down):
9$\quad$6$\quad$5$\quad$2$\quad$1
0$\quad$3$\quad$4$\quad$7$\quad$8
The result is: 9x0 + 6x3 + 5x4 + 2x7 + 1x8 = 0 + 18 + 20 + 14 + 8 = 60
This is an installation that produces a minimum total to be sure, try a different installation from the two installations on.

Example:
Coin Change (for certain nominal sets)
In a Dengklesia country there is a Gordian currency consisting of coins
100,000 gordi, 50,000 gordi, 20,000 gordi, 10,000 gordi, 5,000 gordi, 2,000 gordi,
1,000 gordi, 500 gordi, 200 gordi and 100 gordi. Mr. Dengklek is currently trading in the country. Mr. Dengklek who is known to be stingy always wants change given to buyers using as few coins as possible.
For example when Mr. Dengklek wants to give a change of 600 gordi, he prefers a combination of {1 coin 100 gordi, 1 coin 500 gordi} which is a sum of 2 coins instead of a combination of {3 fractions 200 gordi}, which is a sum of 3 coins.
If one day pack Dengklek must provide a change of 362,800 gordi, what is the minimum number of coins he must spend?
Answer:
The above problem is referred to as coin change. For certain fractions, we are can use the greedy principle to solve the problem. Strategy greedy that is used is to always choose the largest value coins maybe at every step. For this problem, by always taking coins the biggest, we are sure to use the fewest coins. That is :
Step 1) The remaining 362,900 returns. Use 3 pieces of 100,000
Step 2) The remaining 62,900 returns. Use 1 piece of 50,000 pieces
Step 3) The remaining 12,900 returns. Use 1 10,000 piece
Step 4) The remaining 2,900 returns. Use 1 2,000 pieces
Step 5) Remaining 900 returns. Use 1 piece of 500 pieces
Step 6) Remaining 400 returns. Use 2 pieces of 200 pieces
Step complete.
In this way, we only use 9 coins. This is a solution minimal.
Not all types of coins can be solved by the greedy principle, one
an example is if there are only 1,200 gordi of coins, 800 gordi, 400 gordi,
and 100 curtains. If we want to give a refund of 1,200, then with greedy principle, we will use a combination of {1$\quad$1,000 coins, 2$\quad$100 coins} i.e. 3 coin.
Even though the minimum solution is a combination of {1 800 coins, 1 400 coins}, i.e. only 2 coins.

maybe until here the discussion this time and greetings to share ..





Previous
Next Post »
0 Komentar