SKKN Phát triển tư duy của học sinh thông qua việc tối ưu hóa các bài toán trên đồ thị môn Tin học
BÁO CÁO SÁNG KIẾN
I. Điều kiện hoàn cảnh tạo ra sáng kiến
Lý thuyết đồ thị có rất nhiều thuật toán ứng dụng vào các bài toán thực tế của cuộc sống
như tìm đường đi ngắn nhất, tìm cây khung có trọng số nhỏ nhất,…Việc tìm ra mối liên hệ giữa
các bài toán thực tế trong cuộc sống với các thuật toán trên đồ thị, khiến cho học sinh cảm thấy
hứng thú rất lớn với lý thuyết về đồ thị. Tuy nhiên, có một khó khăn khi dạy học về lý thuyết đồ
thị, đó là số lượng thuật toán liên quan đến đồ thị không hề nhỏ. Do vậy, học sinh khi làm các bài
tập liên quan đến đồ thị, các em thường có nhiều thuật toán khác nhau để giải quyết vấn đề. Đôi
khi, các em cảm thấy chưa biết phải vận dụng thuật toán nào để giải quyết các bài toán trên đồ thị.
Việc dạy cho các em nhiều thuật toán trên đồ thị trong một thời gian ngắn, khiến cho các em cảm
thấy đồ thị thật là khó. Do đó, tôi muốn tiếp cận cách giải quyết những bài toán trên đồ thị, dựa
trên việc phát triển từ những thuật toán, phương pháp cơ bản các em cảm thấy quen thuộc như số
học, quy hoạch động, tổ hợp,…
Vì thế tôi chọn đề tài: “Phát triển tư duy học sinh thông qua việc tối ưu hóa các
bài toán trên đồ thị”, nhằm mục đích xây dựng một hệ thống bài tập liên quan đến đồ thị,
đồng thời rèn luyện kỹ năng tối ưu hóa bài toán trên đồ thị
II. Mô tả giải pháp
1. Mô tả giải pháp trước khi tạo ra sáng kiến
Trước khi dạy bài tập về đồ thị, phương pháp dạy học của tôi được tiến hành
như sau:
• Tôi thường tìm kiếm bài tập về đồ thị với nguồn từ sách giáo khoa, sách bài
tập, các nguồn bài tập trên Internet, và các sách tham khảo
Tuy nhiên, sau thời gian dạy cho đội tuyển Tin, tôi nhận thấy các vấn đề sau:
• Một là, bài tập tôi xây dựng vẫn chưa đi theo mạch logic từ dễ đến khó.
Khiến cho một số đơn vị bài tập quá dễ, một số đơn vị bài tập lại quá khó.
Điều đó khiến cho bài dễ thì học sinh nảy sinh tâm lý chủ quan, bài khó quá
thì nhiều học sinh sẽ nảy sinh tâm lý sợ sệt và nản khi học lập trình
4
• Hai là, cần thiết phải có một hệ thống bài tập không quá dễ cũng không quá
khó, và nằm trong khả năng có thể làm được của nhiều đối tượng học sinh.
Hệ thống bài tập như vậy sẽ khiến cho học sinh cảm thấy thích thú tìm hiểu
lập trình, và khai thác sâu được nhiều đơn vị kiến thức qua mỗi bài toán
trong Tin học
Do vậy, tôi viết chuyên đề này với mục đích sau:
• Xây dựng được một hệ thống bài tập có vận dụng đồ thị trong việc tối ưu
hóa thuật toán; chỉ ra được thuật toán tối ưu và thuật toán chưa tối ưu trong
việc giải quyết bài toán, và cài đặt chương trình bằng ngôn ngữ lập trình
C++
2. Mô tả giải pháp sau khi có sáng kiến
Đề tài tôi xây dựng hướng tới mục đích sau:
• Xây dựng và phân tích được những bài tập đồ thị có nhiều cách giải, sử dụng những
thuật toán cơ bản trên đồ thị như dfs, bfs, tìm đường đi ngắn nhất,…. sau đó tối ưu
hóa chúng bằng các phương pháp cơ bản của lớp 10 như số học, quy hoạch động, tổ
hợp,…
• Hệ thống hóa các bài tập cơ bản trên đồ thị, nhằm giúp cho việc phát triển tư duy của
học sinh theo mạch logic.
• Rút ra được kinh nghiệm cài đặt các bài tập liên quan đến đồ thị
• Hình thành kỹ năng tối ưu hóa các bài toán về đồ thị
Nội dung sáng kiến kinh nghiệm của tôi gồm có 2 phần: Phần I là Lý thuyết, nêu
một số lý thuyết học sinh cần nắm vững trước khi bắt đầu với các bài toán trên đồ
thị. Phần 2 là bài tập vận dụng:
I. Một số khái niệm cơ bản
1. Ma trận kề
5
Trong lý thuyết đồ thị, một ma trận kề là một ma trận được sử dụng để biểu
diễn đồ thị. Các phần tử của ma trận biểu thị liệu có cạnh nối giữa hai đỉnh trong
đồ thị hay không. Hình minh họa dưới đây mô phỏng cách biểu diễn một đồ thị
bằng ma trận kề:
| Đồ thị | Ma trận kề biểu diễn đồ thị |
| Ma trận trên gồm có 5 hàng, 5 cột, phần tử có giá trị 1 biểu thị có cạnh nối giữa 1 và 2, 2 và 3, 4 và 5, phần tử có giá trị 0 biểu thị không có cạnh nối giữa chúng | 1 2 3 4 5 |
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
2. Danh sách kề
Một danh sách kề là một mảng các danh sách, nghĩa là, mỗi phần tử của
mảng ai là một danh sách, danh sách đó chứa tất cả các đỉnh liền kề với đỉnh i
Với đồ thị có trọng số, trọng số của cạnh được lưu cùng với đỉnh trong
danh sách bằng cách sử dụng cấu trúc pair trong C++.
Với đồ thị vô hướng, nếu đỉnh j trong danh sách của ai, thì đỉnh i cũng sẽ
được lưu trong danh sách của aj
Chúng ta cùng nhau quan sát đồ thị sau:
Đỉnh số 1 được nối với đỉnh số 2 và đỉnh số 4, ta sẽ biểu diễn:1->2->4
Đỉnh số 2 được nối với đỉnh số 1 và 3, ta sẽ biểu diễn: 2->1->3
Đỉnh số 3 được nối với đỉnh số 2 và 4, ta sẽ biểu diễn: 3->2->4
Đỉnh số 4 được nối với đỉnh số 1 và 3, ta sẽ biểu diễn 4->1->3
Ta xét đồ thị có hướng sau đây:
1 2
4 3
6
Đỉnh số 1 được nối với đỉnh số 2, ta sẽ biểu diễn: 1->2
Đỉnh số 2 được nối với đỉnh số 4, ta sẽ biểu diễn: 2->4
Đỉnh 3 nối với đỉnh số 1 và 4, ta sẽ biểu diễn: 3->1->4
Đỉnh số 4 được nối với đỉnh số 2, ta sẽ biểu diễn: 4->2
Ví dụ sau đây biểu diễn một đồ thị vô hướng gồm có N đỉnh và M cạnh
(trong đó 1<=n<=105, 1<=m<=n*(n-1)/2). Input của dòng đầu tiên là số đỉnh,
dòng thứ hai là số cạnh, m dòng tiếp theo mỗi dòng gồm hai đỉnh a và b, mô tả
cạnh nối giữa đỉnh a và đỉnh b. Output: Đưa ra danh sách kề của các đỉnh
| Danhsachke.inp | Danhsachke.out |
| 4 5 1 2 2 4 3 1 3 4 4 2 | Danh sach ke cua nut 1: 2 Danh sach ke cua nut 2: 4 Danh sach ke cua nut 3: 1 –> 4 Danh sach ke cua nut 4: 2 |
| #include<bits/stdc++.h> using namespace std; vector <int> adj[10]; int main() {int x, y, nodes, edges; freopen(“danhsachke.inp”,”r”,stdin); freopen(“danhsachke.out”,”w”,stdout); cin >> nodes; //So nut cin >> edges; //So canh for(int i = 0;i < edges;++i) { cin >> x >> y; adj[x].push_back(y); //Chen nut y vao danh sach ke cua x } for(int i = 1;i <= nodes;++i) |
1 2
3 4
7
| { cout << “Danh sach ke cua nut ” << i << “: “; for(int j = 0;j < adj[i].size();++j) { if(j == adj[i].size() – 1) cout << adj[i][j] << endl; else cout << adj[i][j] << ” –> “; } } return 0; } |
Độ phức tạp về mặt không gian của danh sách kề là O(V+E), phụ thuộc vào
số đỉnh và số cạnh. Trong nhiều trường hợp, một ma trận kề không thực sự hữu
ích bằng danh sách kề. Bởi vì sử dụng ma trận liền kề sẽ mất nhiều không gian bộ
nhớ để lưu các phần tử là số 0.
3. Thuật toán tìm kiếm đồ thị theo chiều rộng (BFS)
Trong lý thuyết đồ thị, tìm kiếm theo chiều rộng (BFS) là một thuật toán tìm
kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) cho trước
một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể
hướng tới tiếp theo. Có thể sử dụng thuật toán tìm kiếm theo chiều rộng cho hai
mục đích: tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và
tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có
trọng số, thuật toán tìm kiếm theo chiều rộng luôn tìm ra đường đi ngắn nhất có
thể. Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh
gốc. Sau đó, với mỗi đỉnh trong số đó, thuật toán lại lần lượt nhìn trước các đỉnh
kề với nó mà chưa được quan sát trước đó và lặp lại. Cấu trúc dữ liệu được sử
dụng là hàng đợi (queue). (Theo Wikipedia)
Hình minh hoạt sau đây mô phỏng qua trình tìm kiếm đồ thị theo chiều rộng
8
s
1 2
3 4
5
s
1 2
3 4
5
s
1 2
3 4
5
A B C
9
s
1 2
3 4
5
s
1 2
3 4
5
s
1 2
3 4
5
D E F
10
Giải thích: Mũi tên có hướng trong các hình vẽ trên mô phỏng quá trình tìm kiếm
theo chiều rộng, đỉnh được bôi đen nghĩa là đỉnh đó đã được đánh dấu trong quá
trình tìm kiếm. Tại hình C, đỉnh s đã được đánh dấu, vì vậy ta bỏ qua đỉnh s
Tại hình D, đỉnh s và đỉnh số 3 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình E, đỉnh 1 và 2 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình F, đỉnh 2 đã được đánh dấu, vì vậy ta bỏ qua
Tại hình G, đỉnh 3 đã được đánh dấu, vì vậy ta bỏ qua
Mô phỏng giai đoạn thực hiện của thuật toán:
Thao tác lặp thứ nhất
S sẽ được lấy từ hàng đợi
Đỉnh liền kề của s chính là đỉnh 1 và đỉnh 2 sẽ được duyệt qua
Đỉnh 1 và đỉnh 2, chúng sẽ được đẩy vào hàng đợi, và đỉnh 1 và đỉnh 2 sẽ được
đánh dấu là đã thăm
| s | 1 | 2 |
Thao tác lặp thứ hai
1 sẽ được lấy từ hàng đợi
Đỉnh liền kề của 1 là s và 3 sẽ được duyệt qua
S bỏ qua vì s đã được đánh dấu là đã thăm
3 chưa được đánh dấu, do vậy, sẽ đẩy 3 vào hàng đợi và đánh dấu là đã thăm 3
| 1 | 2 | 3 |
s
1 2
3 4
5
G
11
Giai đoạn lặp thứ 3
2 được lấy từ hàng đợi
Đỉnh liền kề của 2 là 3 và 4 được duyệt qua
3 và s bỏ qua vì chúng đã được đánh dấu
4 không được đánh dấu, nên 4 sẽ được đẩy vào hàng đợi
Đánh dấu 4 đã viếng thăm
| 2 | 3 | 4 |
Giai đoạn 4
3 được lấy từ hàng đợi
Đỉnh liền kề của 3 là 1,2, và 5 được duyệt qua
1 và 2 bỏ qua vì chúng đã được đánh dấu
5 chưa được đánh dấu, vì thế sẽ đẩy 5 vào hàng đợi và đánh dấu 5 đã thăm
| 3 | 4 | 5 |
Giai đoạn sáu
4 được lấy từ hàng đợi
Đỉnh liền kề của 4 là 2 được duyệt qua
2 bị bỏ qua vì đã được đánh dấu
| 4 | 5 |
Giai đoạn 6
5 được lấy từ hàng đợi
Đỉnh liền kề của 5 là 3 được duyệt qua
3 bỏ qua vì được đánh dấu là đã thăm
Hàng đợi lúc này sẽ trống rỗng và thoát khỏi vòng lặp. Tất cả các đỉnh được duyệt
qua.
Độ phức tạp của thuật toán BFS là O(V+E) trong đó V là số đỉnh của đồ thị và E
là số cạnh của đồ thị
Ví dụ sau minh họa cách cài đặt đồ thị bằng thuật toán bfs:
Input: File văn bản path.inp. Trong đó: Dòng 1 chứa số đỉnh n(<=100), số cạnh m
của đồ thị, đỉnh xuất phát s, đỉnh kết thúc f cách nhau một dấu cách. M dòng tiếp
theo, mỗi dòng có dạng hai số nguyên dương u, v cách nhau một dấu cách, thể
hiện có cạnh nối đỉnh u và đỉnh v trong đồ thị
Ouput file văn bản path.out, danh sách các đỉnh có thể đến được từ s
| Path.inp | Path.out |
| 8 7 1 5 1 2 1 3 2 3 2 4 3 5 4 6 7 8 | Tu dinh1ban co the toi cac dinh 1 2 3 4 5 6 Duong di tu 1toi5la 5<-3<-1 |
Đây là đoạn chương trình cài đặt có sử dụng queue
12
| #include <bits/stdc++.h> using namespace std; bool a[101][101]={}; long trace[101]={},n,m,s,f; void enter()//nhap du lieu { long u,v; //n la so dinh,m la so canh, s la dinh xuat phat // dinh ket thuc la f cin>>n>>m>>s>>f; for(long i=1;i<=m;i++) {cin>>u>>v; a[u][v]=a[v][u]=true; } } void bfs() { queue<int> ql; ql.push(s); //neu hang doi khong rong while(!ql.empty()) { //lay gia tri phan tu dau tien trong hang doi int u=ql.front(); //loai phan tu dau tien ra khoi hang doi ql.pop(); //tim dinh ke chua di qua lan nao for(int v=0;v<n;v++) if(a[u][v]!=0 &&trace[v]==0 ) { //luu lai nut cha cua dinh v trace[v]=u; //them dinh v vao hang doi ql.push(v); } } } void result()//in ket qua { cout<<“Tu dinh”<<s<<“ban co the toi cac dinh”<<‘\n’; for(long v=1;v<=n;v++) //in ra nhung dinh den duoc tu s if (trace[v]!=0) cout<<v<<” “; |
13
| cout<<‘\n’; cout<<“Duong di tu “<<s<<“toi”<<f<<“la”<<‘\n’; if (trace[f]==0) cout<<“khong tim thay”; // khong co duong di tu s toi f else { while (f!=s) { cout<<f<<“<-“; f=trace[f]; } cout<<s; } } int main() { freopen(“path.inp”,”r”,stdin); freopen(“path.out”,”w”,stdout); enter();//nhap du lieu trace[s]=-1;//ngoai tru s da tham bfs(); result();//in ket qua } |
4. Thuật toán tìm kiếm đồ thị theo chiều sâu
Tìm kiếm ưu tiên chiều sâu hay tìm kiếm theo chiều sâu (tiếng Anh: Depth-first
search – DFS) là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển
xa nhất có thể theo mỗi nhánh. Thông thường, DFS là một dạng tìm kiếm thông tin
không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của đỉnh
đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một đỉnh không có con.
Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước (Theo wikipedia)
Hình minh họa sau đây mô phỏng quá trình tìm kiếm đồ thị của thuật toán
DFS
14
Ví dụ sau minh họa cách cài đặt thuật toán DFS:
Cho đồ thị vô hướng gồm có N đỉnh và M cạnh (1<=N<=105, 1<=M<=N*(n-
1)/2)). Đếm số thành phần liên thông trong đồ thị. Trong lý thuyết đồ thị, một thành
phần liên thông của một đồ thị vô hướng là một đồ thị con trong đó giữa bất kì hai
đỉnh nào đều có đường đi đến nhau, và không thể nhận thêm bất kì một đỉnh nào mà
vẫn duy trì tính chất trên. Một đồ thị liên thông có đúng một thành phần liên thông,
chính là toàn bộ đồ thị
Xem bản đầy đủ trên google drive: TẠI ĐÂY
Các thầy cô cần file liên hệ với chúng tôi tại fanpage facebook O2 Education
Hoặc xem nhiều SKKN hơn tại: Tổng hợp SKKN luận văn luận án O2 Education
