Greedy algorithms: introduction

Июль 21, 2022

Главная
Информатика
Greedy algorithms: introduction

Содержание

2. STRUCTURE OF THE CLASS Maximize Your Salary Queue of Patients Implementation and Analysis Main Ingredients
3. WHAT’S COMING Solve salary maximization problem Come up with a greedy algorithm yourself Solve optimal queue
4. MAXIMIZE SALARY
5. MAXIMIZE SALARY
6. MAXIMIZE SALARY
7. LARGEST NUMBER
8. LARGEST NUMBER
9. LARGEST NUMBER
10. GREEDY STRATEGY {9, 8, 9, 6, 1} → ? ? ? ? ?
11. GREEDY STRATEGY {9, 8, 9, 6, 1} Find max Find max digit
12. GREEDY STRATEGY {9, 8, 9, 6, 1} Find max Find max digit
13. GREEDY STRATEGY {9, 8, 9, 6, 1} → Find max Find max digit Append it to
14. GREEDY STRATEGY {9, 8, 9, 6, 1} → 9 Find max Find max digit Append it
15. GREEDY STRATEGY {9, 8, 9, 6, 1} → 9 Find max Find max digit Append it
16. GREEDY STRATEGY {9, 8, 9, 6, 1} → 9 Find max Find max digit Append it
17. GREEDY STRATEGY {8, 9, 6, 1} → 9 Find max Find max digit Append it to
18. GREEDY STRATEGY {8, 9, 6, 1} → 9 Find max Find max digit Append it to
19. GREEDY STRATEGY {8, 9, 6, 1} → 99 Find max Find max digit Append it to
20. GREEDY STRATEGY {8, 9, 6, 1} → 99 Find max Find max digit Append it to
21. GREEDY STRATEGY {8, 6, 1} → 99 Find max Find max digit Append it to the
22. GREEDY STRATEGY {8, 6, 1} → 99 Find max Find max digit Append it to the
23. GREEDY STRATEGY {8, 6, 1} → 998 Find max Find max digit Append it to the
24. GREEDY STRATEGY {8, 6, 1} → 998 Find max Find max digit Append it to the
25. GREEDY STRATEGY {6, 1} → 998 Find max Find max digit Append it to the number
26. GREEDY STRATEGY {6, 1} → 998 Find max Find max digit Append it to the number
27. GREEDY STRATEGY {6, 1} → 9986 Find max Find max digit Append it to the number
28. GREEDY STRATEGY {6, 1} → 9986 Find max Find max digit Append it to the number
29. GREEDY STRATEGY {1} → 9986 Find max Find max digit Append it to the number Remove
30. GREEDY STRATEGY {1} → 9986 Find max Find max digit Append it to the number Remove
31. GREEDY STRATEGY {1} → 99861 Find max Find max digit Append it to the number Remove
32. GREEDY STRATEGY {1} → 99861 Find max Find max digit Append it to the number Remove
33. GREEDY STRATEGY {} → 99861 Find max Find max digit Append it to the number Remove
34. GREEDY STRATEGY {9, 8, 9, 6, 1} → 99861 Find max Find max digit Append it
35. QUEUE OF PATIENTS
36. QUEUE OF PATIENTS
37. QUEUE OF PATIENTS
38. QUEUE OF PATIENTS
39. QUEUE OF PATIENTS
40. QUEUE OF PATIENTS
41. QUEUE OF PATIENTS
42. QUEUE OF PATIENTS
43. QUEUE OF PATIENTS
44. QUEUE OF PATIENTS
45. GREEDY STRATEGY Make some greedy choice Reduce to a smaller problem Iterate
46. GREEDY CHOICE First treat the patient with the maximum treatment time First treat the patient with
47. GREEDY ALGORITHM First treat the patient with the minimum treatment time
48. GREEDY ALGORITHM First treat the patient with the minimum treatment time Remove this patient from the
49. GREEDY ALGORITHM First treat the patient with the minimum treatment time Remove this patient from the
50. SUBPROBLEM
51. SUBPROBLEM
52. SUBPROBLEM
53. SUBPROBLEM
54. SUBPROBLEM
55. SAFE CHOICE
56. SAFE CHOICE
57. PROOF IDEA Is it possible for an optimal arrangement to have two consecutive patients in order
58. PROOF IDEA Is it possible for an optimal arrangement to have two consecutive patients in order
59. PROOF IDEA Is it possible for an optimal arrangement to have two consecutive patients in order
60. PROOF IDEA Is it possible for an optimal arrangement to have two consecutive patients in order
61. PROOF IDEA Is it possible for an optimal arrangement to have two consecutive patients in order
62. PROOF IDEA We have just proved:
63. SAFE CHOICE PROOF Assume the patient with treatment time tmin is not the first
64. SAFE CHOICE PROOF Assume the patient with treatment time tmin is not the first Let i
65. SAFE CHOICE PROOF Assume the patient with treatment time tmin is not the first Let i
66. Conclusion Now we know that the following greedy algorithm works correctly: First treat the patient with
67. Conclusion Now we know that the following greedy algorithm works correctly: First treat the patient with
68. Conclusion Now we know that the following greedy algorithm works correctly: First treat the patient with
85. Actually, this problem can be solved in time O(n log n)
86. Actually, this problem can be solved in time O(n log n) Instead of choosing the patient
87. Actually, this problem can be solved in time O(n log n) Instead of choosing the patient
88. Actually, this problem can be solved in time O(n log n) Instead of choosing the patient
89. Make some first choice Then solve a problem of the same kind Smaller: fewer digits, fewer
90. A choice is called safe if there is an optimal solution consistent with this first choice
91. A choice is called safe if there is an optimal solution consistent with this first choice
92. A choice is called safe if there is an optimal solution consistent with this first choice
93. GENERAL STRATEGY Problem
94. GENERAL STRATEGY Problem greedy choice Make a greedy choice
95. GENERAL STRATEGY Problem Safe choice greedy choice Make a greedy choice Prove that it is a
96. GENERAL STRATEGY Problem Safe choice greedy choice Subproblem Make a greedy choice Prove that it is
98. Скачать презентацию

Слайд 2

STRUCTURE OF THE CLASS
Maximize Your Salary
Queue of Patients
Implementation and

Analysis
Main Ingredients

Слайд 3

WHAT’S COMING
Solve salary maximization problem
Come up with a greedy

algorithm yourself
Solve optimal queue arrangement problem
Generalize solutions using the concepts of greedy choice, subproblem and safe choice

Слайд 4

MAXIMIZE SALARY

Слайд 5

MAXIMIZE SALARY

Слайд 6

MAXIMIZE SALARY

Слайд 7

LARGEST NUMBER

Слайд 8

LARGEST NUMBER

Слайд 9

LARGEST NUMBER

Слайд 10

GREEDY STRATEGY
{9, 8, 9, 6, 1} → ? ? ?

? ?

Слайд 11

GREEDY STRATEGY
{9, 8, 9, 6, 1}
Find max
Find max

digit

Слайд 12

GREEDY STRATEGY
{9, 8, 9, 6, 1}
Find max
Find max

digit

Слайд 13

GREEDY STRATEGY
{9, 8, 9, 6, 1} →
Find max
Find

max digit
Append it to the number

Append

Слайд 14

GREEDY STRATEGY
{9, 8, 9, 6, 1} → 9
Find max
Find

max digit
Append it to the number

Append

Слайд 15

GREEDY STRATEGY
{9, 8, 9, 6, 1} → 9
Find max
Find

max digit
Append it to the number
Remove it from the list of digits

Append

Remove

Слайд 16

GREEDY STRATEGY
{9, 8, 9, 6, 1} → 9
Find max
Find

max digit
Append it to the number
Remove it from the list of digits

Append

Remove

Слайд 17

GREEDY STRATEGY
{8, 9, 6, 1} → 9
Find max
Find max

digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 18

GREEDY STRATEGY
{8, 9, 6, 1} → 9
Find max
Find max

digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 19

GREEDY STRATEGY
{8, 9, 6, 1} → 99
Find max
Find max

digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 20

GREEDY STRATEGY
{8, 9, 6, 1} → 99
Find max
Find max

digit
Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 21

GREEDY STRATEGY
{8, 6, 1} → 99
Find max
Find max digit

Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 22

GREEDY STRATEGY
{8, 6, 1} → 99
Find max
Find max digit

Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 23

GREEDY STRATEGY
{8, 6, 1} → 998
Find max
Find max digit

Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 24

GREEDY STRATEGY
{8, 6, 1} → 998
Find max
Find max digit

Append it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 25

GREEDY STRATEGY
{6, 1} → 998
Find max
Find max digit
Append

it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 26

GREEDY STRATEGY
{6, 1} → 998
Find max
Find max digit
Append

it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 27

GREEDY STRATEGY
{6, 1} → 9986
Find max
Find max digit
Append

it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 28

GREEDY STRATEGY
{6, 1} → 9986
Find max
Find max digit
Append

it to the number
Remove it from the list of digits
Repeat while there are digits in the list

Append

Remove

Слайд 29