PHÁT TRIỂN NĂNG LỰC HỌC SINH THÔNG QUA THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS) VÀ TÌM KIẾM THEO CHIỀU RỘNG (BFS)
A. MỞ ĐẦU
1. Lý do chọn đề tài.
Đổi mới phương pháp dạy học là một nhiệm vụ quan trọng của ngành giáo dục nhằm nâng cao chất lượng đào tạo, góp phần thực hiện công nghiệp hoá hiện đại hóa đất nước.
Lý thuyết đồ thị (trong Tin học) là một chuyên ngành quan trọng đã được ứng dụng vào nhiều ngành khoa học, kỹ thuật khác nhau vì lý thuyết đồ thị là phương pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa các mối quan hệ của các đối tượng được nghiên cứu.
Vận dụng lý thuyết đồ thị trong dạy học sinh để mô hình hóa các mối quan hệ chuyển thành phương pháp dạy học đặc thù sẽ nâng cao được hiệu quả dạy học thúc đẩy quá trình tự học tự nghiên cứu của học sinh theo hướng tối ưu hóa đặc biệt nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng tạo của học sinh. Việc cung cấp thêm một phương pháp giải bài tập cho học sinh Tin học 11 tham gia học lập trình là một nhu cầu cần thiết. Xuất phát từ những lý do trên tôi lựa chọn đề tài: “Phát triển năng lực học sinh thông qua thuật toán tìm kiếm theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)”.
2. Mục tiêu, nhiệm vụ của đề tài.
- Mục tiêu của đề tài: Chỉ ra hướng vận dụng DFS và BFS trong lý thuyết đồ thị
vào giải các bài toán và tìm ra các biện pháp để giúp học sinh trung học phổ thông
hình thành và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập lập
trình.
- Nhiệm vụ của đề tài:
- Tìm hiểu những nội dung cơ bản của lý thuyết đồ thị được trang bị cho học
sinh Tin học.
- Chỉ ra hệ thống bài tập có thể vận dụng lý thuyết đồ thị để giải.
- Chỉ ra được những dấu hiệu cụ thể để nhận dạng “Bài toán” có thể khai thác lý
thuyết đồ thị trong quá trình giải bài toán.
1
- Chỉ ra các phương án vận dụng lý thuyết đồ thị vào giải toán.
+ Tiếp cận chương trình mới môn Tin học 2018 phần đồ thị có trong mạch kiến
thức CS
3. Giả thuyết khoa học.
Nếu ta có các phương pháp giúp học sinh Tin học 11 vận dụng kiến thức về lý
thuyết đồ thị vào giải các bài toán thì sẽ giúp học sinh giải quyết được một số lớp
bài toán góp phần nâng cao chất lượng dạy học cũng như phát triển được năng lực
của học sinh.
4. Phương pháp nghiên cứu.
a. Nghiên cứu lý luận.
- Nghiên cứu các văn bản, tài liệu chỉ đạo của Bộ GD & ĐT liên quan đến đổi mới
phương pháp dạy học, đổi mới ra đề kiểm tra, danh mục thiết bị dạy học Tin học.
- SGK, phân phối chương trình, sách giáo viên, chuẩn của bộ môn Tin ở trung học
phổ thông, sách nâng cao, sách chuyên đề.
- Các tài liệu về lý thuyết đồ thị và những ứng dụng của nó trong thực tiễn cuộc
sống và trong dạy học.
- Các công trình nghiên cứu các vấn đề liên quan trực tiếp đến phương pháp đồ thị.
b. Thực nghiệm sư phạm.
- Chỉ ra cho học sinh các dấu hiệu "nhận dạng" và cách thức vận dụng lý thuyết đồ
thị vào giải bài tập.
- Biên soạn hệ thống bài tập luyện tập cho học sinh và một số đề bài kiểm tra để
đánh giá khả năng vận dụng lý thuyết đồ thị vào giải các bài toán.
2
- Tiến hành thực nghiệm và đánh giá kết quả thực nghiệm.
B. NỘI DUNG
I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ.
1. Đồ thị và tầm quan trọng.
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng
hiện đại. Các bài toán đặt ra nếu được đưa về lý thuyết đồ thị để giải sẽ tiết kiệm
được rất nhiều thời gian, ý tưởng thuật toán sẽ rõ ràng, chương trình ngắn gọn và
dễ hiểu. Nếu hiểu và biết vận dụng tốt lý thuyết đồ thị sẽ giúp chúng ta giải quyết
được rất nhiều bài toán đặt ra trong thực tế (xem ở phần giải quyết vấn đề). Khoa
học và kỹ thuật phát triển làm xuất hiện hàng loạt bài toán trong thực tiển được quy
về mô hình đồ thị.
1.1. Định nghĩa đồ thị: Cho tập hợp X khác rỗng, E là tập hợp các cặp phần tử
của X được sắp xếp thứ tự hoặc không sắp thứ tự. Cặp (X, E) được gọi là một đồ
thị. Kí hiệu đồ thị là G = (X, E) hoặc đôi khi nếu không gây nhầm lẫn kí hiệu tắt là
G.
1.2. Một số khái nhiệm.
- Các phần tử thuộc tập X gọi là đỉnh của đồ thị G.
- Cho 2 đỉnh x1, x2X, nếu e = (x1,x2)E là cặp sắp thứ tự thì e được gọi là một
cung của đồ thị, hoặc nếu e là cặp không sắp thứ tự thì e được gọi là một cạnh của
đồ thị.
- e = (x1,x2) là cung thì x1 là đỉnh đầu của cung, x2 là đỉnh cuối của cung e.
- e = (x1,x2) là cạnh thì x1 và x2 là 2 đỉnh kề của cạnh e hoặc 2 đỉnh thuộc cạnh e.
- Hai đỉnh x1 và x2 (x1 ≠ x2) của đồ thị được gọi là 2 đỉnh kề nhau nếu chúng là 2
đầu của một cạnh hoặc một cung.
- Hai cạnh a, b (hoặc 2 cung a, b) gọi là 2 cạnh kề nhau (hoặc 2 cung kề nhau)
nếu chúng có một đỉnh chung.
- Khuyên là cạnh (hoặc cung) có 2 đầu trùng nhau.
- Đỉnh treo là đỉnh thuộc duy nhất một cạnh hoặc cung.
3
- Đỉnh cô lập là đỉnh không thuộc cạnh hoặc cung nào.
1.3. Phân loại đồ thị.
Cho đồ thị G = (X, E), nếu E chỉ gồm các cạnh thì G là đồ thị vô hương. Nếu E
chỉ gồm các cung thì đồ thị G là đồ thị có hướng. Nếu E gồm cả cạnh và cung thì
G là đồ thị hỗn hợp.
Đa đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đa đồ thị khi và chỉ khi
nó là đồ thị không khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng ít
nhất 2 cạnh (hoặc 2 cung nối theo thứ tự của cặp đỉnh).
Đơn đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đơn đồ thị khi và chỉ
khi nó là đồ thị không khuyên và mỗi cặp đỉnh được nối với nhau không quá một
cạnh (hoặc cung).
2. Biểu diễn đồ thị.
Biểu diễn đồ thị trên máy tính theo cấu trúc nào thì sẽ có giải thuật theo cấu trúc
đó. Với học sinh Tin học 11, biểu diễn bằng ma trận (mảng 2 chiều) là dễ hiểu và
phù hợp nhất. Cách khai thác trên mảng 2 chiều đã được học sinh làm nhiều ở
SGK Tin học 11.
Các cách biểu diễn đồ thị:
2.1. Biểu diễn bằng hình học.
Minh họa cách biểu diễn
Đ.Nai
Thanh Hoá
An Giang
Hà Tây
TP. HCM
Long An
Hà Nội
Khánh Hoà
Nam Định
Huế
`
Hình 1: Đơn đồ thị, vô hướng
4
`
2
2
4
1
4
1
6
3
5
3
5
Hình 3: Đa đồ thị, có hướng
Hình 2: Đa đồ thị, vô hướng
2.2. Biểu diễn đồ thị bằng ma trận liên thuộc (Ma trận kề).
Giả sử đồ thị G = (X, E) có tập đỉnh X = (x1,x2, x3,…,xn), tập cạnh (hoặc cung)
1
2
3
là E. Ta xây dựng ma trận vuông A cấp n sao cho i,j, 1i,jn có:
5
4
Ma trận A là ma trận liên thuộc (ma trận kề)
Hình 4: Đồ thị và ma trận kề
Nhận xét : Nếu G là độ thị vô hướng thì
Ma trận A sẽ đối xứng qua đường chéo chính,
Aij = Aji i,j, 1i,jn.
2.3. Biểu diễn bằng ma trận trọng số.
Trong nhiều bài toán về đồ thị, mỗi cạnh (hoặc cung) e = (xi, xj) của đồ thị
thường được gắn với một số c (e) gọi là trọng số của cạnh (hoặc cung) e. Khi đó
thường xây dựng ma trận vuông cấp n là ma trận C có mỗi phần tử C[i,j] = c(e) nếu
tồn tại cạnh (hoặc cung) e = (xi, xj), ngược lại khi không có cạnh nối xi với xj thì
C[i,j] = (kí hiệu là giá trị không xác định). Trong nhiều trường hợp, ngậm
định C[i,i] = 0 với mọi đỉnh i trong đồ thị không khuyên.
3. Tìm kiếm trên đồ thị và tìm thành phần liên thông trên đồ thị.
Hiểu được bản chất của các phép tìm kiếm và tìm thành phần liên thông trên đồ
5
thị chúng ta có thể giải quyết được rất nhiều các dạng bài toán đặt ra (thể hiện ở
phần áp dụng). Qua tìm kiếm trên đồ thị chúng ta có thể kết hợp tính toán, thống
kê, sắp xếp và tổng hợp được các kết quả.
3.1. Một số khái niệm.
Định nghĩa 1: Đường đi có độ dài k (k nguyên dương) từ đỉnh u tới đỉnh v trên
đồ thị vô hướng G = (V, E) là dãy các đỉnh u = x0, x1, x2, x3,…, xk = v mà các cạnh
(xi, xi+1)E, i=0,1,2,…,k-1. Đường đi này còn có thể biểu diễn dưới dạng dãy các
cạnh: (x0,x1), (x1,x2),….,(xk-1,xk). Đỉnh u gọi là đỉnh đầu (xuất phát), đỉnh v gọi là
đỉnh cuối (đỉnh đích) của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi
là một chu trình.
Đường đi hay chu trình được gọi là đơn nếu không có cạnh nào bị lặp lại.
Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ
trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại)
Định nghĩa 2: Đường đi có độ dài k (k nguyên dương) từ đỉnh u tới đỉnh v trên
đồ thị có hướng G = (V, E) là dãy các đỉnh u = x0, x1, x2, x3,…, xk = v mà các cung
(xi, xi+1)E, i = 0,1,2,…,k-1. Đường đi này còn có thể biểu diễn dưới dạng dãy các
cung: (x0,x1), (x1,x2),….,(xk-1,xk). Đỉnh u gọi là đỉnh đầu (xuất phát), đỉnh v gọi là
đỉnh cuối (đỉnh đích) của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi
là một chu trình (mạch vòng).
Đường đi hay chu trình được gọi là đơn nếu không có cung nào bị lặp lại.
Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ
trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại)
Định nghĩa 3: Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm
được đường đi giữa 2 đỉnh bất kỳ của nó.
Định nghĩa 4: Cho đồ thị vô hướng G = (V, E) và đồ thị con của G là đồ thị G‟
= (V‟, E‟). Đồ thị G‟ được gọi là một vùng liên thông (hoặc thành phần liên
thông) của G nếu:
+ G‟ liên thông;
+ Không tồn tại đường đi nào từ một đỉnh thuộc G‟ tới 1 đỉnh không thuộc G‟
6
(nói cách khác là bảo đảm tính tối đại của liên thông trong G‟).
Ví dụ: Trong hình 5 xét 2 đồ thị G và H: G chỉ có 1 vùng liên thông duy nhất,
H2
H có 3 vùng liên thông là H1, H2, H3.
G
H1
H
H3
Hình 5: G liên thông, H gồm 3 vùng liên thông
Định nghĩa 5: Đỉnh v được gọi là đỉnh khớp (đỉnh rẻ nhánh) của đồ thị vô
hướng G = (V, E) nếu khi loại bỏ đỉnh v và các cạnh liên thuộc với nó thì số thành
phần liên thông của G tăng thêm.
Cạnh e E được gọi là cầu nếu loại bỏ nó khỏi đồ thị G thì số thành phần liên
thông của G tăng thêm 1 đơn vị.
3.2. Tìm kiếm trên đồ thị.
Tìm kiếm trên đồ thị là duyệt (thăm) tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1
lần.
Rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt tất cả các đỉnh của đồ
thị sao cho mỗi đỉnh của nó được viếng thăm đúng 1 lần. Vì vậy, việc xây dựng
những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là
một vấn đề quan trọng. Các thuật toán này giữ một vai trò quan trọng trong việc
thiết kế các thuật toán trên đồ thị.
Trên đồ thị có 2 thuật toán tìm kiếm cơ bản:
- Thuật toán tìm kiếm theo chiều sâu (DFS.)
- Thuật toán tìm kiếm theo chiều rộng (BFS).
3.3. Tìm đường đi và kiểm tra tính liên thông.
Tìm đường đi và kiểm tra tính liên thông là một hình thức ứng dụng các thuật
toán tìm kiếm trên đồ thị. Đường đi tìm được theo thuật toán tìm kiếm theo chiều
7
rộng là đường đi ngắn nhất (theo số cạnh) từ đỉnh s đến đỉnh t.
4. Đường đi ngắn nhất trên đồ thị.
Trong các ứng dụng thực tế. Bài toán tìm đường đi ngắn nhất giữa 2 đỉnh của
một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều
bài toán thực tế quan trọng. Ví dụ, Bài toán chọn một hành trình tiết kiệm nhất
(theo tiêu chuẩn khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao
thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp
tiết kiệm để đưa một hệ động lực từ trạng thái xuất phát đến trạng thái đích, bài
toán lập lịch thi công các công đoạn trong một công trình thi công lớn,…
II. THỰC TRẠNG CỦA VẤN ĐỀ.
1. Thuận lợi.
Lý thuyết đồ thị có thể giải quyết được nhiều bài toán đặt ra trong thực tế
phù hợp với đối tượng học sinh giỏi Tin học 11, đặc biệt là những bài toán thể hiện
quan hệ nhị phân giữa các đối tượng rời rạc.
Vận dụng lý thuyết đồ thị giúp học sinh có thêm một luồng kiến thức mới để làm
giàu hơn tư duy thuật toán của mình.
Có khá nhiều tài liệu giới thiệu về các vấn đề liên quan đến lý thuyết đồ thị
như: sách cấu trúc dữ liệu và giải thuật, Sách Toán rời rạc,…và các tài liệu trên
mạng Internet.
Giáo viên và học sinh phát huy được tính năng động trong quá trình dạy -
học đạt kết quả cao hơn.
Một số kiến thức dễ sử dụng và hiệu quả cao. Ví dụ: phép tìm kiếm và kiểm
tra vùng liên thông trên đồ thị.
2. Khó khăn.
- Trong việc nắm bắt và hiểu được các khái niệm cơ bản liên quan đến lý thuyết đồ
thị.
- Lý thuyết đồ thị rất rộng và nhiều phần kiến thức khó nên không thể truyền tải
hết tới học sinh và khó để đưa vào hết trong đề tài.
- Đưa ra các giải thuật bằng ngôn ngữ Pascal và C++ để minh hoạ các kiến thức
8
đưa ra ở phần cơ sở lý luận.
- Đưa ra hệ thống các dạng bài tập có thể giải quyết hiệu quả bằng lý thuyết đồ thị
và cách giải các bài tập đó.
- Để khắc phục được một phần khó khăn nêu trên, trong đề tài tôi chỉ đề cập đến
những phần quan trọng của lý thuyết đồ thị có ứng dụng nhiều trong thực tế và phù
9
hợp với học sinh THPT, đặc biệt là học sinh Tin học 11.
III. HAI THUẬT TOÁN VÀ MỘT SỐ BÀI TẬP ÁP DỤNG
1. Tìm kiếm theo chiều rộng.
Ý tưởng: Đỉnh xuất phát v ở đây cũng được thăm đầu tiên nhưng có khác với DFS ở chổ là: Sau đó các đỉnh chưa được thăm mà là lân cận của v sẽ được thăm kế tiếp theo nhau, rồi mới đến các đỉnh chưa được thăm là lân cận lần lượt của các đỉnh này và cứ tương tự như vậy.
Ví dụ: Thứ tự đi trong hình 6:
Bắt đầu từ 1 => 2 => 7 => 8 => hết node ngang.
Tiếp tục 2 => 3 => 6 hết node ngang.
Bắt đầu 7 => không có node ngang.
Tiếp tục 8=>9 => 12 hết node ngang
Bắt đầu 3 => 4 => 5 => hết node
ngang
Tiếp tục 6 => không có node ngang
Bắt đầu 9 => 10=> 11 hết node ngang
Tiếp tục 12 => không có node ngang
Bắt đầu 4 => hết node
Tiếp tục 5 => hết node
Hình 6
Bắt đầu 10 => hết node
Tiếp tục 11 => hết node
Mô hình thuật toán tìm kiếm theo chiều rộng
+) Ngôn ngữ Pascal
Procedure BFS(v); {Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v}
Begin
Queue:=;
Queue <= v; {nạp đỉnh v vào Queue}
Chuaxet[v] :=false ;
10
While Queue <> do
Begin
u<= Queue; {Lấy đỉnh p từ Queue ra}
Thăm_đỉnh(u);
For y Ke(u) do
If chuaxet[y] then
Begin
Queue <= y; {nạp đỉnh v vào Queue}
Chuaxet[y]:=false;
End;
End;
End;
BEGIN
For v V do Chuaxet[v]:=true; {Khởi tạo}
For v V do
If Chuaxet[v] then BFS(v);
END.
+) Ngôn ngữ C++
Free[u]=true; //với mọi u=1...n
Queue ban đầu rỗng.
Push(s); // Đẩy đỉnh đầu tiên vào queue
Free[s]=false; // đánh dấu đỉnh s
while (not empty())
{
u = pop(); // lấy từ queue đỉnh u
for (v=1; v<=n; v++)
if ((tồn tại cạnh u,v) và Free[v]==true)
11
{
Free[v]=false; // đánh dấu đỉnh v
Push(v); // đẩy đỉnh v vào queue
}
}
Bài tập cơ sở số 1: Viết chương trình ghi ra thứ tự duyệt DFS xuất phát từ đỉnh s.
Đồ thị gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau.
Dữ liệu vào:
Dòng đầu: gồm 3 số nguyên n, m, s (1<=n, m<=100, 1<=s<=n)
M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị
Dữ liệu ra:
Gồm nhiều dòng, là thứ tự duyệt DFS
Ví dụ:
Input 7 7 1 1 2 1 3 1 5 2 6 2 4 3 7 5 6
Output 1 2 3 5 4 6 7
+) Ngôn ngữ Pascal
12
Const maxn = 101; Var a : array [1..maxn,1..maxn] of boolean; free : array [1..maxn] of boolean; Q : array [1..maxn] of integer; n, m, s: integer; dau, cuoi : integer; Procedure init; Begin fillchar(a,sizeof(a),false); fillchar(Free,sizeof(Free),true); dau:=1; cuoi:=0; end; Procedure readf; Var i, u, v : integer;
13
Begin readln(n,m,s); for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure Push(u:integer); begin inc(cuoi); Q[cuoi] := u; end; Function Pop : integer; Begin Pop := Q[dau]; inc(dau); end; Procedure BFS(i : integer); Var u, v : integer; Begin Push(i); Free[i] := false; While dau<=cuoi do begin u := Pop; writeln(u); For v := 1 to n do If A[u,v] and Free[v] then begin Push(v); Free[v] := false; end; end; end; Procedure main; Var i : integer; Begin
init; readf; BFS(s); end; BEGIN main; END. +) Ngôn ngữ C++
14
#include
15
for (int i=1; i<=m; i++) { cin >> u>> v; a[u][v]=1; a[v][u]=1; } for (int i=1; i<=n; i++) Free[i]=1; BFS(s); return 0; }
2. Tìm kiếm theo chiều sâu
Ý tưởng: Đỉnh xuất phát v được thăm. Tiếp theo đó, một đỉnh y chưa được
thăm, mà là lân cận của v, sẽ được chọn và một phép tìm kiếm theo chiều sâu xuất
phát từ y lại được thực hiện. Khi một đỉnh u đã được “với tới” mà mọi đỉnh lân cận
của nó đều đã được thăm rồi, thì ta sẽ quay ngược lên đỉnh cuối cùng vừa được
thăm, (mà còn có đỉnh y lân cận với nó chưa được thăm), và một phép tìm kiếm
theo chiều sâu xuất phát từ y lại được thực hiện. Phép tìm kiếm sẽ kết thúc khi
không còn một nút nào chưa được thăm mà vẫn có thể với tới được từ một nút đã
Hình 7
được thăm.
Ví dụ thứ tự đi trong hình7.
Bắt đầu từ 1 => 2 => 3 => 4 => hết đường đi
Quay lại 3 => 5 => hết đường đi
Tiếp tục từ 3 quay lại 2 => 6 => hết đường đi
Quay lại 2 => quay lại 1 => 7 => hết đường đi
Tiếp tục từ 1 => 8 => 9=> 10 => hết đường đi
Quay lại 9 => 11 => hết đường đi
Tiếp tục 9=> quay lại 8 => 12 => hết đường đi
16
Quay lại 8 => quay lại 1 => hết đường => KẾT THÚC.
Mô hình thuật toán tìm kiếm theo chiều sâu:
+) Ngôn ngữ Pascal
Procedure DFS(v); {tìm theo chiều sâu bắt đầu từ đỉnh v, các biến Chuaxet,
ke là cục bộ}
Begin
Thăm đỉnh (v);
Chuaxet[v]:=false;
For mỗi đỉnh y Ke( v) do
If chuaxet[y] then DFS();
End;
Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán
sau:
BEGIN
For vV do Chuaxet[v]:=true;
For vV do if Chuaxet[v] then DFS(v);
END.
+) Ngôn ngữ C++
void dfs(int u)
{
free[u] = false; // đánh dấu đỉnh u đã được thăm
for (int v=1; v<=n; v++)
if ((tồn tại cạnh u, v) và (free[u][v] == true)) // tồn tại đỉnh kề với u, chưa
được thăm
dfs(v); //duyệt đỉnh v
17
}
Bài tập cơ sở số 2: Viết chương trình ghi ra thứ tự duyệt DFS xuất phát từ đỉnh s.
Đồ thị gồm n đỉnh, m cạnh 2 chiều, các thành phần trên đồ thị liên thông với nhau.
Dòng đầu: gồm 3 số nguyên n, m, s (1<= n, m <=100, 1<= s <=n)
M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị
Dữ liệu vào:
Gồm nhiều dòng, là thứ tự duyệt DFS
Dữ liệu ra:
Ví dụ:
Input
Output
7 7 1
1 2
1
1 3
2
1 5
4
2 6
6
2 4
5
3 7
3
5 6
7
+) Ngôn ngữ Pascal
18
Const maxn = 101; Var a : array [1..maxn,1..maxn] of boolean; free : array [1..maxn] of boolean; Q : array [1..maxn] of integer; n, m, s: integer; dau, cuoi : integer; Procedure init; Begin fillchar(a,sizeof(a),false); fillchar(Free,sizeof(Free),true); end; Procedure readf; Var i, u, v : integer; Begin readln(n,m,s);
for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure DFS(u : integer); Var v : integer; Begin writeln(u); Free[u] := false; For v := 1 to n do If A[u,v] and Free[v] then dfs(v); end; Procedure main; Var i : integer; Begin init; readf; DFS(s); end; BEGIN main; END. +) Ngôn ngữ C++
19
Const maxn = 101; Var a : array [1..maxn,1..maxn] of boolean; free : array [1..maxn] of boolean; Q : array [1..maxn] of integer; n, m, s: integer; dau, cuoi : integer; Procedure init; Begin fillchar(a,sizeof(a),false); fillchar(Free,sizeof(Free),true); end;
Procedure readf; Var i, u, v : integer; Begin readln(n,m,s); for i := 1 to m do begin readln(u,v); A[u,v] := true; A[v,u] := true; end; end; Procedure DFS(u : integer); Var v : integer; Begin writeln(u); Free[u] := false; For v := 1 to n do If A[u,v] and Free[v] then dfs(v); end; Procedure main; Var i : integer; Begin init; readf; DFS(s); end; BEGIN main; END. Bài tập cơ sở số 3: Tìm thành phần liên thông của đồ thị
Cho một đồ thị G = (V,E). Hãy cho biết số thành phần liên thông của đồ thị
và mỗi thành phần liên thông gồm những đỉnh nào.
Gợi ý làm bài: Điều kiện liên thông của đồ thị thường là một yêu cầu tất
yếu trong nhiều ứng dụng, chẳng hạn một mạng giao thông hay mạng thông tin nếu
không liên thông thì xem như bị hỏng, cần sửa chữa. Vì thế, việc kiểm tra một đồ
20
thị có liên thông hay không là một thao tác cần thiết trong nhiều ứng dụng khác
nhau của đồ thị. Dưới đây ta xét một tình huống đơn giản (nhưng cũng là cơ bản)
là xác định tính liên thông của một đồ thị vô hướng với nội dung cụ thể như sau:
“cho trước một đồ thị vô hướng, hỏi rằng nó có liên thông hay không?”.
Để trả lời bài toán, xuất phát từ một đỉnh tùy ý, ta bắt đầu thao tác tìm kiếm
từ đỉnh này (có thể chọn một trong hai thuật toán tìm kiếm đã nêu). Khi kết thúc
tìm kiếm, xảy ra hai tình huống: nếu tất cả các đỉnh của đồ thị đều được thăm thì
đồ thị đã cho là liên thông, nếu có một đỉnh nào đó không được thăm thì đồ thị đã
cho là không liên thông. Như vậy, câu trả lời của bài toán xem như một hệ quả trực
tiếp của thao tác tìm kiếm. Để kiểm tra xem có phải tất cả các đỉnh của đồ thị có
được thăm hay không, ta chỉ cần thêm một thao tác nhỏ trong quá trình tìm kiếm,
đó là dùng một biến đếm để đếm số đỉnh được thăm. Khi kết thúc tìm kiếm, câu trả
lời của bài toán sẽ phụ thuộc vào việc so sánh giá trị của biến đếm này với số đỉnh
của đồ thị: nếu giá trị biến đếm bằng số đỉnh thì đồ thị là liên thông, nếu trái lại thì
đồ thị là không liên thông. Trong trường hợp đồ thị là không liên thông, kết quả
tìm kiếm sẽ xác định một thành phần liên thông chứa đỉnh xuất phát. Bằng cách lặp
lại thao tác tìm kiếm với đỉnh xuất phát khác, không thuộc thành phần liên thông
vừa tìm, ta nhận được thành phần liên thông thứ hai, ..., cứ như vậy ta giải quyết
được bài toán tổng quát hơn là xác định các thành phần liên thông của một đồ thị
vô hướng bất kỳ.
Như ta đã biết, các thủ tục DFS(u) và BFS(u) cho phép viếng thăm tất cả các
đỉnh có cùng thành phần liên thông với u nên số thành phần liên thông của đồ thị
chính là số lần gọi thủ tục trên. Ta sẽ dùng thêm biến đếm “dem” để đếm số thành
phần liên thông.
Và vòng lặp chính trong các thủ tục tìm kiếm theo chiều sâu hay chiều rộng
chỉ cần sửa lại như sau:
Procedure Inkq;
Begin
Fillchar(cx,sizeof(cx),false);
21
dem:=0;
For u thuộc V do
If not cx[u] then
Begin
Inc(dem); DFS(u); (*BFS(u)*)
End;
End;
Thủ tục DFS(u) hoặc BFS(u) sẽ làm công việc đánh số thành phần liên thông của
đỉnh u:
Bài toán: Viết chương trình tìm các thành phần liên thông của đồ thị. Đồ thị gồm n
đỉnh, m cạnh.
Dữ liệu vào:
Cho tệp LIENTHONG.INP dòng đầu: gồm 2 số nguyên n, m(1 <= n, m<= 1000 )
M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị
Dữ liệu ra:
Ghi ra tệp LIENTHONG.OUT gồm:
Thứ tự các đỉnh của mỗi thành phần liên thông trên mỗi dòng
Đếm số thành phần liên thông của đồ thị. Ví dụ:
Input
Output
Thanh phan lien thong thu 1: 1 2 3 4 5 6 7
7 9
Thanh phan lien thong thu 2: 8 9
1 2
So luong thanh phan lien thong: 2
2 3
2 4
4 5
1 6
6 7
8 9
+) Ngôn ngữ Pascal
22
const fi = 'LIENTHONG.INP'; fo = 'LIENTHONG.OUT'; MAXN = 10000;
23
var f: text; n: integer; a: array [1..MAXN, 1..MAXN] of integer; cx: array [1..MAXN] of boolean; procedure Nhap; var i, u,v: integer; begin assign(f, fi); reset(f); readln(f, n); for i:= 1 to n do begin readln(f,u,v); a[u,v]=1; a[v,u]=1; end; close(f); end; procedure Init; var i: integer; begin for i := 1 to n do cx[i]:= true; end; procedure DFS(u: integer); var v: integer; begin for v:= 1 to n do if a[u, v] = 1 then if cx[v] = true then begin cx[v]:= false; write(f, ' ', v); DFS(v); end; end; procedure InKQ; var u, dem: integer; begin assign(f, fo); rewrite(f); dem := 0; for u:= 1 to n do
24
if cx[u] = true then
begin
inc(dem);
cx[u]:= false;
write(f, 'Thanh phan lien thong thu ', dem, ': ');
write(f, u);
DFS(u);
writeln(f);
end;
writeln(f, 'So luong thanh phan lien thong la: ', dem);
close(f);
end;
BEGIN
Nhap;
Init;
InKQ;
END.
+) Ngôn ngữ C++
#include
25
{ int i; for (i=1; i<=n; i++) cx[i] = true; } void DFS(int u) { int v; for (v=1; v<=n; v++) if (a[u][v] == 1) if (cx[v] == true) { cx[v] = false; f << " " << v; DFS(v); } } void InKQ() { int u, dem; f.open(fo, ios::out); dem = 0; for (u=1; u<=n; u++) if (cx[u] == true) { dem++; cx[u] = false; f << "Thanh phan lien thong thu " << dem << ": " << u; DFS(u); f << endl; } f << "So luong thanh phan lien thong la: " << dem; f.close(); } int main() { Nhap(); Init(); InKQ(); }
Bài tập cơ sở số 4: Tìm đường đi giữa hai đỉnh của đồ thị
Cho đồ thị G = (V,E). Với hai đỉnh s và t là hai đỉnh nào đó của đồ thị. Hãy
tìm đường đi từ s đến t.
Gợi ý làm bài:
Do thủ tục DFS(s) và BFS(s) sẽ thăm lần lượt các đỉnh liên thông với u nên
sau khi thực hiện xong thủ tục thì có hai khả năng:
- Nếu Daxet[t] = True thì có nghĩa: tồn tại một đường đi từ đỉnh s tới đỉnh t.
- Ngược lại, thì không có đường đi nối giữa s và t.
Vấn đề còn lại của bài toán là: Nếu tồn tại đường đi nối đỉnh s và đỉnh t thì làm
cách nào để viết được hành trình (gồm thứ tự các đỉnh) từ s đến t. Về kỹ thuật lấy
đường đi là: Dùng một mảng Truoc với: Truoc[v] là đỉnh trước của v trong đường
đi. Khi đó, câu lệnh If trong thủ tục DFS(u) được sửa lại như sau:
If not cx[v] then
Begin
DFS(v);
Truoc[v]:=u;
End;
Còn với thủ tục BFS ta cũng sửa lại trong lệnh If như sau:
If not cx[w] then
Begin
Kết nạp w vào Queue;
cx[w]:=True;
Truoc[w]:=v;
End;
Việc viết đường đi lên màn hình (hoặc ra file) có thể có 3 cách:
- Viết trực tiếp dựa trên mảng Truoc: Hiển nhiên đường đi hiển thị sẽ ngược từ
26
đỉnh t trờ về s như sau:
- Dùng thêm một mảng phụ P: cách này dùng để đảo đường đi từ mảng Truoc để
có đường đi thuận từ đỉnh s đến đỉnh t.
- Cách thứ 3: là dùng chương trình đệ quy để viết đường đi.
Procedure TruyVet(i:Byte);
If i<>s then
Begin
TruyVet(Truoc[i]);
Write('=>',i);
End;
Các bạn có thể tuỳ chọn cách mà mình thích nhưng thiết nghĩ đó chưa phải
là vấn đề quan trọng nhất. Nếu tinh ý dựa vào thứ tự thăm đỉnh của thuật toán tìm
kiếm theo chiều rộng BFS ta sẽ có một nhận xét rất quan trọng, đó là: Nếu có
đường đi từ s đến t, thì đường đi tìm được do thuật toán tìm kiếm theo chiều rộng
cho chúng ta một hành trình cực tiểu về số cạnh.
Ví dụ: Viết chương trình tìm đường đi giữa 2 đỉnh của đồ thị. Đồ thị gồm n đỉnh,
m cạnh.
Dữ liệu vào:
Cho tệp DOTHI.INP dòng đầu: gồm 4 số nguyên n, m, s, t là các đỉnh, cạnh và 2
đỉnh bất kì của đồ thị(1<=n, m<=1000 )
M dòng tiếp theo: mỗi dòng gồm 2 số u, v, mô tả 1 cạnh trong đồ thị
Dữ liệu ra:
Ghi ra tệp LIENTHONG.OUT gồm:
Thứ tự các đỉnh của là đường đi từ đỉnh s đến đỉnh t nếu không tồn tại đường đi thì
27
ghi ra tệp là: không có đường đi từ s đến t.
Ví dụ:
Output
Input
4 -> 2 -> 1 -> 6 - 7
9 8 4 7
1 2
1 6
2 3
2 4
4 5
6 7
6 8
8 9
+) Ngôn ngữ Pascal
28
const fi = 'DOTHI.INP'; fo = 'DOTHI.OUT'; MAXN = 10000; var f: text; n, s, t: integer; a: array [1..MAXN, 1..MAXN] of integer; cx: array [1..MAXN] of boolean; Truoc: array [1..MAXN] of integer; procedure Nhap; var i, j: integer; begin assign(f, fi); reset(f); readln(f, n, s, t); for i:= 1 to n do for j := 1 to n do read(f, a[i, j]); close(f); end; procedure Init; var i: integer; begin for i := 1 to n do cx[i]:= true; cx[s]:= false; Truoc[s]:= -1;
29
end; procedure DFS(u: integer); var v: integer; begin for v:= 1 to n do if a[u, v] = 1 then if cx[v] = true then begin cx[v]:= false; Truoc[v]:= u; DFS(v); end; end; procedure TruyVet(v: integer); begin if Truoc[v] = -1 then write(f, v) else begin TruyVet(Truoc[v]); write(f, ' -> ', v); end; end; procedure InKQ; begin assign(f, fo); rewrite(f); if cx[t] = true then writeln(f, 'Khong co duong di tu ', s, ' toi ', t) else TruyVet(t); close(f); end; BEGIN Nhap; Init; DFS(s); InKQ; END.
30
+) Ngôn ngữ C++
#include
31
void TruyVet(int v) { if (Truoc[v] == -1) f << v; else { TruyVet(Truoc[v]); f << " -> " << v; } } void InKQ() { f.open(fo, ios::out); if (cx[t] == true) f << "Khong co duong di tu " << s << " toi " << t << endl; else TruyVet(t); f.close(); } int main() { Nhap(); Init(); DFS(s); InKQ(); }
MỘT SỐ BÀI TẬP ÁP DỤNG
Có rất nhiều bài toán vận dụng thuật toán tìm kiếm trên đồ thị và thuật toán
tìm số vùng liên thông để giải mà chương trình ngắn gọn, hiệu quả. Đặc biệt là các
bài toán liên quan đến duyệt, tìm kiếm mà cách lưu trữ dữ liệu được đưa về dưới
dạng ma trận kề (mảng 2 chiều). Dưới đây tôi xin trích ra một số ví dụ để minh họa
cho điều này:
Bài tập 5: Đồng cỏ
Bessie dự định cả ngày sẽ nhai cỏ xuân và ngắm nhìn cảnh xuân trên cánh
đồng của nông dân John, cánh đồng này được chia thành các ô vuông nhỏ với R (1
<= R <= 100) hàng và C (1 <= C <= 100) cột. Bessie ước gì có thể đếm được số
khóm cỏ trên cánh đồng.
Mỗi khóm cỏ trên bản đồ được đánh dấu bằng một ký tự „#„ hoặc là 2 ký tự
„#‟ nằm kề nhau (trên đường chéo thì không phải). Cho bản đồ của cánh đồng, hãy
nói cho Bessie biết có bao nhiêu khóm cỏ trên cánh đồng.
Ví dụ như cánh đồng dưới dây với R = 5 và C = 6:
#.... ..#... ..#..# ...##. .#...
Cánh đồng này có 5 khóm cỏ: một khóm ở hàng đầu tiên, một khóm tạo bởi
hàng thứ 2 và thứ 3 ở cột thứ 2, một khóm là 1 ký tự nằm riêng rẽ ở hàng 3, một
khóm tạo bởi cột thứ 4 và thứ 5 ở hàng 4, và một khóm cuối cùng ở hàng 5.
Dữ liệu: dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C
Dòng 2..R+1: Dòng i+1 mô tả hàng i của cánh đồng với C ký tự, các ký tự là „#‟
hoặc „.‟ .
Kết quả dòng 1: Một số nguyên cho biết số lượng khóm cỏ trên cánh đồng.
32
Ví dụ .#.... ..#... ..#..# ...##. .#....
Kết quả: 5
Gợi ý làm bài: ở đây ta áp dụng bài tập cơ bản số 3, chính là tìm thành phần
liên thông, mỗi thành phần liên thông chính là một khóm cỏ.
33
+) Ngôn ngữ Pascal program VBGRASS; const fi=''; nmax=101; cld:array[1..4] of shortint=(0,0,-1,1); clc:array[1..4] of shortint=(-1,1,0,0); type matran=array[0..nmax,0..nmax] of char; var m,n:byte; a:matran; f:text; visit:array[1..nmax,1..nmax] of boolean; s:word; procedure docfile; var i,j:byte; begin assign(f,fi); reset(f); readln(f,m,n); for i:=1 to m do begin for j:=1 to n do read(f,a[i,j]); if eoln(f) then readln(f); end; close(f); end; procedure DFS(u,v:byte); var i:byte; u1,v1:shortint; begin visit[u,v]:=true; for i:=1 to 4 do begin u1:=u+cld[i]; v1:=v+clc[i]; if (a[u1,v1]='#') and (not visit[u1,v1]) then DFS(u1,v1); end;
34
end;
procedure init;
begin
fillchar(visit,sizeof(visit),false);
s:=0;
end;
procedure xuli;
var i,j:byte;
begin
init;
for i:=1 to m do
for j:=1 to n do
if (a[i,j]='#') and (not visit[i,j]) then
begin
DFS(i,j);
inc(s);
end;
writeln(s);
end;
begin
docfile;
xuli;
end.
+) Ngôn ngữ C++
#include
int u1,v1; visit[u][v]=true; for(int i=0; i<4; i++) // code c++ thi phai la 0 den 3 {
}
init(); for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) if(a[i][j]=='#' && !visit[i][j])
cout< void init()
{
memset(visit,false,sizeof(visit));
s=0;
}
void DFS(int u,int v)
{
u1=u+cld[i];
v1=v+clc[i];
if(a[u1][v1]=='#'&& !visit[u1][v1]) DFS(u1,v1);
}
int main()
{
{
DFS(i,j);
s++;
}
} Trong các ví dụ dưới đây, tôi chỉ đưa ra cách giải từng ví dụ mà không đưa chương trình kèm theo vì đưa vào làm cho đề tài quá dài Bài tập 6: Truyền tin Một lớp gồm N học viên, mỗi học viên cho biết những bạn mà học viên đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều, ví dụ : Bạn An có thể gửi tin tới Bạn Vinh nhưng Bạn Vinh thì chưa chắc đã có thể gửi tin tới Bạn An). Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các học viên của lớp (tin này phải được truyền trực tiếp). Để tiết kiệm thời gian, thầy chỉ nhắn tin tới 1 số học viên rồi sau đó nhờ các học viên này nhắn lại cho tất cả các bạn mà các học viên đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho 35 tất cả các học viên trong lớp đều nhận được tin . Câu hỏi : có phương án nào giúp thầy chủ nhiệm với một số ít nhất các học viên mà thầy chủ nhiệm cần nhắn? Gợi ý làm bài: Có thể nhận thấy bài toán này chính là bài toán 1 đã phát biểu phía trên. Có thể coi mỗi học sinh là một đỉnh của đồ thị. Hai học sinh có thể liên lạc được với nhau là một cạnh. Từ đó suy ra bài toán này là . Bài toán tìm thành phần liên thông của đồ thị. Bài tập 7: XÂY KÈ (Đề thi học sinh giỏi tỉnh Nghệ an năm học 2007 – 2008) Một bản đồ hình chữ nhật mô tả một số diện tích hồ nước thiên nhiên được chia lưới ô vuông sao cho mỗi ô của lưới chỉ được xem như có 2 trạng thái: hoặc là diện tích hồ, hoặc không phải. Người ta muốn xây kè đá xung quanh các hồ này. Mỗi cạnh của lưới được xây kè nếu nó là cạnh chung của 2 ô khác trạng thái (các cạnh thuộc biên bản đồ không được tính). Lập trình tính tổng chiều dài của kè (theo đơn vị cạnh ô lưới). Dữ liệu : Vào từ file văn bản KE.INP gồm: Dòng đầu ghi M (số dòng của lưới) và N (số cột của lưới). Mỗi dòng trong số M dòng tiếp mô tả trạng thái của N ô lưới tương ứng của dòng gồm N số 0 (là đất) hoặc 1 (là hồ) theo đúng thứ tự các ô trong lưới. Kết quả: Ghi ra file văn bản KE.OUT gồm một số ghi giá trị chiều dài kè. Ví dụ: Bản đồ (các ô có mầu xám là diện tích hồ, các cạnh đậm là kè) có các file vào, ra tương ứng như sau: KE.INP KE.OUT 43 6 11
0 0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 0 1 0 0 0
0 0 0 1 0 0 1 1 1 1 0
0 1 0 0 0 1 1 0 1 1 0
0 1 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 1 1 1 36 Giới hạn: M, N không quá 200.
Gợi ý làm bài: - Có thể nhận thấy bài toán này chính là bài toán 1 đã phát biểu phía trên. Có thể coi mỗi cạnh của ô vuông là một đỉnh của đồ thị. . Từ đó suy ra bài toán này là bài toán đếm các đỉnh của các thành phần liên thông đồ thị. Bài tập 8: Đường đi đến số 0 (Đề thi Giáo viên giỏi tỉnh Nghệ an chu kì 2008 – 2011) Mỗi một số nguyên dương đều có thể biểu diễn dưới dạng tích của 2 số nguyên dương X,Y sao cho X<=Y. Nếu như trong phân tích này ta thay X bởi X-1 còn Y bởi Y+1 thì sau khi tính tích của chúng ta thu được hoặc là một số nguyên dương mới hoặc là số 0. Ví dụ: Số 12 có 3 cách phân tích 1*12,3*4, 2*6 . Cách phân tích thứ nhất cho ta tích mới là 0 : (1-1)*(12+1) = 0, cách phân tích thứ hai cho ta tích mới 10 : (3- 1)*(4+1) = 10, còn cách phân tích thứ ba cho ta 7 : (2-1)*(6+1)=7. Nếu như kết quả là khác không ta lại lặp lại thủ tục này đối với số thu được. Rõ ràng áp dụng liên tiếp thủ tục trên, cuối cùng ta sẽ đến được số 0, không phụ thuộc vào việc ta chọn cách phân tích nào để tiếp tục Yêu cầu: Cho trước số nguyên dương N (1<=N<=10000), hãy đưa ra tất cả các số nguyên dương khác nhau có thể gặp trong việc áp dụng thủ tục đã mô tả đối với N. Dữ liệu: Vào từ file Zeropath.Inp chứa số nguyên dương N. Kết quả: Ghi ra file văn bản Zeropath.Out : Dòng đầu tiên ghi K là số lượng số tìm được Dòng tiếp theo chứa K số tìm được theo thứ tự tăng dần bắt đầu từ số 0. Lưu ý: Có thể có số xuất hiện trên nhiều đường biến đổi khác nhau, nhưng nó chỉ được tính một lần trong kết quả. Ví dụ: ZEROPATH.INP ZEROPATH.OUT 12 6 0 3 4 6 7 10 Gợi ý làm bài: Đơn giản là sau mỗi lần phân tích thì chắc chắn kết quả mới luôn nhỏ hơn số 37 đó. Vì vậy ta chỉ cần Lưu trữ dưới mảng A: [0..10000] of boolean, trong đó A[i] = true nếu nó xuất hiện trên đường đi đó, ngược lại thì A[i] =false. Bằng cách loang theo chiều sâu, chúng ta sẽ đánh dấu các số nếu nó được dùng đến, cho đến khi không thể nào loang được nữa thì dừng. Bài tập 9. Con ngựa Một bàn cờ hình chữ nhật kích thước M x N, M,N nguyên dương không lớn hơn 100. Bàn cờ chia thành các ô vuông đơn vị bằng các đường song song với các cạnh. Các dòng ô vuông đánh số từ 1 đến M từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái sang phải. Cho trước một số nguyên dương K<=1000. Một con ngựa đứng ở ô [u,v] và nhảy không quá k bước. Yêu cầu: Hãy cho biết con ngựa có thể nhảy đến bao nhiêu ô khác ô[u,v] trên bàn cờ và đó là những ô nào (khi đứng tại một ô, con ngựa có thể nhảy tới ô đối đỉnh của hình chữ nhật kích thước 2 x 3). Dữ liệu: Vào từ file MA.INP trong đó : Dòng đầu tiên ghi hai số M,N Dòng thứ hai ghi số K Dòng thứ ba ghi hai số U,V Kết quả: Ghi ra file MA.OUT : Dòng đầu tiên ghi S là số ô con ngựa có thể nhảy đến Tiếp theo là S dòng, mỗi dòng ghi chỉ số dòng và chỉ số cột của một ô mà con ngựa có thể nhảy đến. MA.INP MA.OUT 6 5 5 1 1 1 5 3 1 3 5 4 2 4 4 1 2 3 Gợi ý làm bài Chúng ta sẽ loang theo chiều sâu, tìm kiếm xem những ô nào con mã có thể 38 đặt chân đến trong vòng K bước nhảy. Bài tập 10: Đường đi trên lưới ô vuông Cho một lưới ô vuông kích thước N x N. Các dòng của lưới được đánh số từ 1 đến N từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến N từ trái qua phải. Ô nằm trên giao của dòng i, cột j sẽ được gọi là ô (i, j) của lưới. Trên mỗi ô (i, j) của lưới người ta ghi một số nguyên dương ai, i, j = 1,2,..., N. Từ một ô bất kỳ của lưới được phép di chuyển sang ô có chung cạnh với nó. Thời gian để di chuyển từ một ô này sang một ô khác là 1 phút. Cho trước thời gian thực hiện di chuyển là K (phút), hãy xác định cách di chuyển bắt đầu từ ô (1, 1) sao cho tổng các số trên các ô di chuyển qua là lớn nhất (Mỗi ô của lưới có thể di chuyển qua bao nhiêu lần cũng được). Dữ liệu: Vào từ file văn bản NETSUM.INP: N 100, 1 Dòng đầu tiên chứa các số nguyên dương N, K (2 K 10000). Dòng thứ i trong số N dòng tiếp theo chứa các số nguyên ai1, ai2..., ain, 0 < ai < 10000 (Các số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách). Kết quả: Ghi ra file văn bản NETSUM.OUT: Dòng đầu tiên ghi tổng số các số trên đường di chuyển tìm được. K dòng tiếp theo mỗi dòng ghi toạ độ của một ô trên đường di chuyển (bắt đầu từ ô (1, 1)). Ví dụ: NETSUM.INP 5 7
1 1 1 1 1
1 1 3 1 9
1 1 6 1 1
1 1 3 1 1
1 1 1 1 1 NETSUM.OUT
2 1
1 1
1 2
1 3
2 3
2 4
2 3
2 4 Gợi ý làm bài: Loang các ô có thể đến của các đường đi trên lưới. Tìm cách đi nào có 39 đường đi mà tổng lớn nhất thì sẽ lấy. Bài tập 11: Miền liên thông. Cho bảng chữ nhật chia thành M xN ô vuông đơn vị (M dòng đánh số từ 1 đến M theo chiều từ trên xuống dưới, N cột đánh số từ 1 đến N theo chiều từ trái qua phải. Mỗi ô vuông ghi 1 số 0 hoặc 1. Một miền 0 của bảng là tập hợp các ô chung cạnh và chứa số 0). Địa chỉ của một miền là toạ độ [dòng, cột] của ô đầu tiên thuộc miền theo thứ tự duyệt từ trái qua phải, từ trên xuống dưới. Hãy tìm số miền 0 của bảng và tìm miền 0 có diện tích lớn nhất. Dữ liệu vào : File Mien.INP có cấu trúc : Dòng đầu ghi 2 số nguyên dương M và N (0 M dòng tiếp theo thể hiện bảng số theo thứ tự từ trên xuống dưới, mỗi dòng N số theo thứ tự từ trái sang phải. Dữ liệu ra : File Mien.Out có cấu trúc : Dòng thứ nhất ghi số lượng miền 0. Dòng thứ 2 ghi diện tích của miền 0 có diện tích lớn nhất. Các dòng tiếp theo, mỗi dòng ghi địa chỉ một miền 0 có diện tích lớn nhất. Cách giải : Chúng ta có thể giải theo cách thông thường không vận dụng lý thuyết đồ thị. Nhưng rõ ràng, giải theo cách tìm kiếm trên đồ thị sẽ ngắn gọn, hiệu quả và nhanh hơn nhiều. Thuật toán thể hiện rõ ràng, dễ hiểu. Cụ thể như sau : Thực hiện vòng lặp. Tìm một ô chứa số 0 chưa thăm là ô x có toạ độ dòng và cột là (i,j). Thực hiện thuật toán BDF (tìm kiếm theo chiều rộng) để tìm được miền 0 chứa ô x. Trong quá trình duyệt cũng tính diện tích của miền (mỗi lần đến một ô mới thì tăng diện tích lên một đơn vị). Mỗi lần thực hiện xong thủ tục BDF thì tìm được một miền 0 chứa ô (i,j), lưu kết quả (toạ độ i, j và diện tích của miền vào mảng KQ) đồng thời tăng biến đếm số miền 0. Hiện số lượng miền 0. Duyệt mảng KQ để tìm miền 0 có diện tích lớn nhất. Hiện diện tích miền 0 lớn 40 nhất Duyệt mảng KQ lần thứ 2 để hiện toạ độ từng ô đại diện cho mỗi miền 0 có diện tích bằng diện tích của miền lớn nhất. Bài tập 12: Hệ thống đảo cung cấp xăng. Vùng Hạ Long có N hòn đảo được đánh số từ 1 đến N. Toạ độ hòn đảo thứ i trên mặt phẳng toạ độ được cho bởi cặp số nguyên xi, yi. Trên mỗi đảo có bể chứa xăng có khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết bị chứa xăng của ca nô không thể chứa đủ số xăng đi hết M km. Hãy tìm hành trình cho ca nô đi từ đảo U đến đảo V (0 xăng là nhỏ nhất. Dữ liệu vào : File văn bản DAO.INP có cấu trúc Dòng đầu ghi 4 số nguyên dương N, M, U, V Các dòng tiếp theo, dòng thứ i trong các dòng này ghi 2 số nguyên dương xi, yi. Kết quả : Ghi ra file văn bản DAO.OUT Nếu có đường đi thì dòng đầu tiên ghi số đảo ghé vào lấy xăng (trừ U và V) Dòng thứ 2 ghi số hiệu các đảo đó theo thứ tự hành trình. Nếu không có đường đi thì ghi „KHONG CO DUONG DI‟ Ví dụ : 41 Cách giải : Áp dụng thuật toán tìm kiếm theo chiều rộng để được đường đi qua ít đảo nhất. Điều kiện để đi được từ đảo A sang đảo B là khoảng cách AB M km. Trong quá trình tìm kiếm theo chiều rộng tổ chức thêm mảng Truoc(N) với 42 Truoc[i] = j có nghĩa là đảo j ngay trước đảo i trên hành trình đi từ U đến V. IV. KẾT QUẢ VÀ KIẾN NGHỊ ĐỀ XUẤT 1. Kết quả nghiên cứu : Sau nhiều năm áp dụng dạy học sinh khối 11 áp dụng cách làm này tôi nhận thấy: - Vận dụng kiến thức về lý thuyết đồ thị vào giải các bài toán thì sẽ giúp học sinh giải quyết được một số lớp bài toán góp phần nâng cao chất lượng dạy học cũng như phát triển được năng lực của học sinh. - Tiếp cận chương trình mới môn Tin học 2018 phần đồ thị có trong mạch kiến thức CS - Trong các năm học 2018 – 2019 tôi đã ứng dụng đề tài nghiên cứu của mình đối với một số lớp khối 11 ở trường THPT Lê Viết Thuật và đã tổng hợp số liệu về kết quả đạt được của học sinh như sau: Không đạt yêu STT Lớp Sĩ số Giỏi Khá Trung bình cầu 1 11A1 40 17% 54% 29% 2 11T1 42 25% 50% 25% 3 11A4 38 2% 39% 47% 11% - Kết quả học sinh giỏi cấp tỉnh các năm gần đây đạt kết quả cao - Ứng dụng lý thuyết đồ thị vào dạy học và bồi dưỡng học sinh giỏi Tin học tại các trường THPT có ý nghĩa rất quan trọng trong việc nâng cao chất lượng, hiệu quả dạy học, qua đó giúp học sinh nhận thức đúng đắn vai trò, vị trí của môn học. Hơn nữa việc ứng dụng lý thuyết đồ thị tạo được hứng thú học tập cho học sinh, phát huy tính tích cực, chủ động, nhằm phát triển tư duy sáng tạo và năng lực giải quyết vấn đề trong thực tiển cuộc sống. Đề tài này đã giúp bản thân tôi tìm hiểu sâu hơn kiến thức về lý thuyết đồ thị và giúp học sinh tìm hiểu thêm một luồng kiến thức mới để làm phong phú ý tưởng thuật toán của mình, tạo nền tảng cơ bản 43 và bàn đạp để tiến xa hơn về con đường lập trình. Xã hội càng phát triển càng đặt ra nhiều yêu cầu mới, do đó các bài toán đặt ra hiện nay ngày càng thiên về khuynh hướng giải bằng lý thuyết đồ thị. - Từ hai thuật toán cơ bản chúng ta chỉ cần thay đổi các tham số hoặc thêm vào các tham số khác nhau thì được các bài toán khác nhau qua đó các em hiểu rõ hơn về hai thuật toán cơ bản trong đồ thị. 2. Kiến nghị, đề xuất : Sau khi thực hiện đề tài này tôi xin mạnh dạn đưa ra một số đề xuất như sau : - Để học sinh thực sự hiểu rõ trong lập trình về phần đồ thị đối với học sinh lớp 11 thì cần tăng cường hơn nữa lượng thời gian trong phân phối chương trình để học sinh rèn luyện các dạng bài tập. - Giáo viên cần khai thác các bài toán cơ bản từ hai thuật toán cơ bản (DFS và BFS) từ đó mở rộng ra các bài toán tương tự khác. - Với đối tượng học sinh khá giỏi thì có thể khai thác sâu hơn một số bài toán 44 khó và các mô hình khác trong đồ thị. C. KẾT LUẬN Với cách làm này thì phát triển được năng lực, kỹ năng lập trình của học sinh, từ đó giúp các em hứng thú để tiếp tục tìm hiểu và giải quyết các bài toán khác, các thầy, cô có thể áp dụng cách làm này với nhiều dạng bài tập khác nhau để thấy được hiệu quả. Tôi hy vọng các thầy cô có thể tạo được niềm đam mê cho học sinh và tạo ra những học sinh có tư duy kỹ năng lập trình đó cũng là mong muốn của tôi khi viết SKKN này. Trên đây là sáng kiến nghiệm của bản thân trong quá trình giảng dạy cũng như bồi dưỡng học sinh khá giỏi. Mặc dù đã rất cố gắng nhưng không thể tránh khỏi những sai sót, rất mong được sự góp ý kiến, phê bình, phản hồi của các đồng nghiệp (ĐT: 0976124889). Tôi xin chân thành cảm ơn! Vinh, ngày 05 tháng 03 năm 2020 Người viết 45 Hoàng Xuân Thắng TÀI LIỆU THAM KHẢO [1] – Hồ Sỹ Đàm, Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Tùng – Tài liệu chuyên Tin học, quyển 1, quyển 2, NXB Giáo dục, 2011. [2]. Một số tài liệu về quy hoạch động của thầy Lê Minh Hoàng [3]. Bài tập trên http://codepascal.blogspot.com/ 46 https://www.spoj.com/PTIT/problems http://ntucoder.net/ MỤC LỤC NỘI DUNG Trang Phần A: Phần mở đầu 1 1. Lý do chọn đề tài 1 2. Mục tiêu nhiện vụ của đề tài 1 3. Giả thiết khoa học 2 4. Phương pháp nghiên cứu 2 Phần B: Nội dung 3 I. Cơ sở lý luận của vấn đề 3 1. Đồ thị và tầm quan trọng 3 2. Biểu điễn đồ thị 4 3. Tìm kiếm trên đồ thị và tìm thành phần liên thông của đồ thị 5 4. Đường đi ngắn nhất trên đồ thị 8 II. Thực trạng của vấn đề 8 1. Thuần lợi 8 2. Khó khăn 8 III. Hai thuật toán và một số bài tập áp dụng 10 1. Tìm kiếm theo chiều rộng 10 2. Tìm kiếm theo chiều sâu 16 IV. Kết quả và kiến nghị đề xuất 43 1. Kết quả nghiên cứu 43 2. Kiến nghị đề xuất 44 Phần C. Kết luận 45 47 Tài liệu tham khảo 46DAO.INP
DAO.OUT
12 10 1 12
4
2 6 7 9
0 0
8 0
8 6
0 8
10 4
15 4
20 8
20 0
25 8
25 4
25 0
30 4
