Frontiers in Computing and Intelligent Systems
ISSN: 2832-6024 | Vol. 6, No. 2, 2023
"Algorithm Analysis and Design" Python Teaching
Example of Greedy and Dynamic Programming
Ying Zhang 1, Lele Xi 1, Yixia Wu 1, Canping Li 2, Zebin Ma 1, *
1 Schoolof Mathematics and Computer, Guangdong Ocean University, 524088, China
2 Schoolof Electronics and Information Engineering, Guangdong Ocean University, 524088, China
* Corresponding author: Zebin Ma (Email: mazebin@[Link])
Abstract: The greedy algorithm and dynamic programming algorithm have always been difficult for students to understand
in the course of algorithm analysis and design. This article uses Python as a descriptive language and selects classic examples of
greedy and dynamic programming algorithms to analyze these two algorithms in detail, providing effective references for
learning the Python language.
Keywords: Algorithm Design and Analysis; Python; Experimental Teaching; Greed; Dynamic Planning.
acyclic graph DAG, and the weights of each edge, find the
1. Introduction shortest path from the origin s to each point, as shown in
Both the greedy algorithm and the dynamic programming Figure 1.
algorithm are two commonly used algorithms in algorithm
design. The greedy algorithm only considers the optimal
solution in the current state and cannot guarantee the global
optimal solution, while the dynamic programming algorithm
can guarantee the global optimal solution by decomposing the
problem into many overlapping subproblems and using the
optimal substructure algorithm. Selecting different algorithms
for different problems can optimize the efficiency of the
algorithm, improve the running speed of the program, and
make the program better serve the practical applications. And Figure 1. directed acyclic graph
Python, as a simple and easy-to-learn programming language,
provides a very convenient way for algorithm design.
Example problem analysis:
2. Greedy Algorithms (1) First, we set the shortest distance to each point as
D(X) starting at point S, where D(S)=0 and the D
A greedy algorithm is an algorithm that focuses only on the values of the remaining points are set to INF. and
local optimum and then approximates the global locally [1]. use an array to record whether the current node has
However, the solution obtained using the greedy algorithm is been visited or not.
not always the global optimal solution, it depends on the (2) Pick a node with the smallest D value from the
original problem and the greedy strategy used. Therefore, unvisited nodes, traverse all the edges starting from
when solving real-world problems, we need to make a it and update the D value at the end of the edge and
set the current node as visited.
judgment on whether the current problem can be solved using
a greedy strategy. That is, although they are both greedy (3) Repeat step (2) until all nodes have been visited or
the D values of the unvisited nodes are INF.
algorithms, their strategies may be different. When solving a
problem, the greedy strategy chosen must be free of a (4) Each time we pick one of the unvisited nodes with
the smallest D-value to use it to update the shortest
posteriori effects, i.e., each process is independent of the other path to other nodes, even if the subsequent visited
and has no influence on the previous and subsequent ones [2]. nodes have paths to reach the current point but the
Although greedy algorithms sometimes do not lead to an distance from that point to the current point must
optimal solution but to a near-optimal solution, they can not be less than the D-value of the current point.
greatly improve the efficiency of our solution within the error (5) Under the condition of satisfying (4) we can
margin [3]. The general steps for applying the greedy determine the minimum value of arriving at a point
algorithm to solve a problem are: each time, and after n layers of loops we can get the
shortest distance from point S to all the points, with
(1) Set up a model to describe the problem. a time complexity of O( ).
(2) Divide the original problem into subproblems. The program and running results are shown in Figure 2:
(3) Solve each subproblem, resulting in a locally optimal
solution to the subproblem.
(4) Combine the local optimal solutions of the subproblems
into the solution of the original problem.
Example topic: shortest path problem. Given a directed
52
(1) 400 gold/5 people
(2) 500 gold/5 people
(3) 200 gold/3 people
(4) 300 gold/4 people
(5) 350 gold/3 people
A miner can only mine one gold mine, not one and then
another, and each mine is either fully mined or not mined in
the first place. Solve: which gold mines should be dug to get
as much gold as possible?
Example Analysis:
(1) First, we start by assuming that the ith gold mine
requires w[i] people, and that it generates v[i].
(2) We first analyze the maximum gain that can be achieved
at the current number of users when some of the elements are
selected or not and let F[i][j] be the value of the maximum
Figure 2. Dijkstra's algorithm
gain that can be achieved by using no more than j people for
the first i gold mines.
Considerations for using the greedy algorithm: (3) Establish the recursive relationship equation:
(1) The greedy algorithm does not consider the overall max 1 , 1
optimality of the problem, but only chooses some sense of Fi j (1)
max 1 , 1 , 1
local optimality [4], so the results obtained by the greedy
algorithm are not necessarily correct. (4) Then iterates through all the gold mines accordingly,
(2) Any topic that requires consideration of previously taken and finally F[5][10], which is the result needed for this
steps or paths is not suitable for the use of greedy algorithms. question
(3) The use of greedy algorithms needs to be proven by Algorithmic Analysis:
reasoning at the mathematical level, otherwise the greedy (5) Time complexity analysis of the algorithm, let the
algorithm adopted is not always correct. number of miners be m and the number of mines be n, then
the time complexity of the current algorithm is O(n*m)
3. Dynamic Planning Algorithm The program and running results are shown in Figure 3:
Dynamic programming algorithm is an effective method
suitable for solving overlapping subproblems and optimal
substructure problems created by the American
mathematician Bellman in the study of optimization problems
of multi-stage decision-making process[5] , which is
commonly used for solving complex problems in
mathematics, finance and computer science, and whose basic
idea is to decompose the problem to be solved into a number
of simple and interconnected subproblems, solving the
subproblems first, and then using the solution of the
subproblems as a The basic idea is to decompose the problem
to be solved into several simple and interrelated sub-problems,
solve the sub-problems first, and then use the solution of the
sub-problems as the condition of the upper problem until the
solution of the original problem is found. It is worth noting
that the problems solved by dynamic programming are often Figure 3. Problem of miners digging
not independent of each other after the decomposition of the
subproblems[6]. Because the dynamic programming Considerations for using dynamic programming algorithms:
algorithm for recurring subproblems, only in the first (1) Definition analyzes whether the problem has the
encounter to solve it, and the solution will be saved for properties of optimal substructure and overlapping
subsequent states to be used again [7], so this algorithm to subproblems [9] and can only be solved using dynamic
solve the problem is much less time-consuming than other programming algorithms when the problem satisfies these
methods. The steps to solve the problem by applying the two properties.
dynamic programming algorithm are as follows [8]: (2) The results of each operation need to be saved so that
(1) Define sub-problem. resources are not wasted on calculating the same thing later.
(2) Guess the partial solution. (3) For the current problem if you can't represent its state
(3) Develop recursive relationships between sub-problems. using a low-dimensional array, you need to open a high-
(4) Solve the transfer of state equation since the bottom is dimensional array to represent its state.
up.
(5) Combine the solutions of all sub-problems to obtain the 4. Conclusion
solution of the original problem.
Example topic: miner mining problem. It is known that Through this article on the greedy algorithm and the
there are 5 gold mines and 10 miners, and the corresponding dynamic programming algorithm, we can see the differences
gold reserves of the 5 mines and the required miners are as and applications between the two algorithms, with the greedy
follows: method being a special case of dynamic programming. In
53
Python, the implementation of the two algorithms is very [3] Bi Longge. Greedy algorithm and linear programming[J].
similar, both need to explicitly perform state transfer and Computer Products and Distribution,2017, (11):239+251.
optimization solution. In practice, we need to choose the [4] Wang Ying. On the application of greedy algorithm in graph
suitable algorithm to solve the problem according to the theory [J]. Computer CD-ROM Software and Applications,
characteristics and requirements of the problem. Python, as a 2013, 16(16):309+311.
programming language with very high language readability [5] CHENG Zhenbo, LI Qu,WANG Chunping. Algorithm design
and ease of learning, provides us with a good convenience for and analysis[M]. Tsinghua University Press:Tsinghua
optimization algorithm design. We believe that Python and University Academic Research Building,Beijing,2018.
these two algorithms will play a more important role in the [6] Dong Junjun. Comparison and analysis of dynamic
future learning and application. programming algorithm and greedy algorithm[J]. Software
Journal, 2008, (02):129-130.
Acknowledgments [7] ZHANG Aihua, GUO Xiyue,CHEN Qianjun. Analysis and
This work was supported by Postgraduate Education research on dynamic programming algorithms[J]. Software
Innovation Project of Guangdong Ocean University (202303) Guide,2014,13(12):68-69.
and Guangdong Ocean University Innovation and [8] SHI Shaojian, ZHANG Hong,SHI Zheng. Research on
Entrepreneurship Training Program Project Grant dynamic programming algorithms[J]. Computer Knowledge
(CYXL2023005) (CXXL2023124) (CXXL2023134). and Technology,2020,16(18):48-49.
[9] Wang Junxiang. Research on the principle and application of
References dynamic programming algorithm[J]. Computer Knowledge
[1] Liu Dan. Research on automatic class scheduling method based and Technology: Academic Exchange, 2006.
on greedy algorithm [J]. Information and Computer [10] Zhang M, Zhao H, et al. Experimental tutorial on data
(Theoretical Edition),2020,32(04):36-38. structures and algorithms [M]. Beijing. Higher Education
[2] Chang Youqu, Xiao Guiyuan, Zeng Min. Exploration and Press.2011.
research on greedy algorithm[J]. Journal of Chongqing Electric
Power College, 2008, 13(3):40-42.
54