Trang 3
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH
MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HỒ CẨM HÀ Hà Nội - 2011
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ,
động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong
suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên
cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế
và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc
chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo
của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được
hoàn thiện hơn.
Hà Nội, ngày 12 tháng 06 năm 2011
Nguyễn Thị Chinh Trang 7
MỤC LỤC
LỜI CẢM ƠN 6
LỜI NÓI ĐẦU 10
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN 12
1. Khái niệm bài toán Tin học 12
2. Khái niệm thuật toán 12
3. Các tính chất của thuật toán 13
4. Độ phức tạp và xác định độ phức tạp của thuật toán 14
5. Chi phí thực hiện thuật toán 18
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung
học Phổ thông Chuyên 18
6.1. Một số khái niệm cơ bản về đồ thị 18
6.1.1. Khái niệm đồ thị (Graph) 18
6.1.2. Các khái niệm cơ bản 19
6.2. Bài toán tìm kiếm trên đồ thị 21
6.2.1. Phát biểu bài toán 21
5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước 45
5.4. Tổng hợp mô phỏng theo các bước 47
5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng 47
6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán 48
6.1. Một số hệ thống mô phỏng thuật toán chung 49
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt 52
6.3. Xây dựng hệ thống từ đầu 53
Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ
THUẬT TOÁN TRÊN ĐỒ THỊ 54
1. Mục đích 54
2. Những yêu cầu thực tế 54
3. Đề xuất cho hệ thống mới 55
4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị 56
Trang 9
4.1. Lựa chọn công cụ lập trình 57
4.2. Chức năng mô phỏng của các thuật toán được cài đặt 59
4.2.1 Mô phỏng thuật toán tìm kiếm 59
4.2.2. Mô phỏng thuật toán Dijkstra 61
4.2.3. Mô phỏng thuật toán Ford – Bellman 63
4.2.4. Mô phỏng thuật toán Prim 63
4.2.5. Mô phỏng thuật toán Kruskal 65
4.2.6. Thuật toán tìm chu trình Hamilton 66
5. Giới thiệu chương trình 66
5.1. Tổng quan về hệ thống 66
5.1.1. Các đối tượng xây dựng cấu trúc đồ thị 67
5.1.2. Công cụ vẽ hình ảnh để mô phỏng 70
5.1.3.Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng 70
5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt 71
Chương 4 KẾT LUẬN 80
dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán,
để giáo viên có thể làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ
tiếp thu hơn.
Nội dung luận văn được chia thành 3 chương:
Trang 11
Chương I. Những kiến thức cơ bản về thuật toán.
Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán.
Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng,
chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ
được học.
Chương II. Mô phỏng thuật toán.
Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của
mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu
quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán
nói chung.
Chương III. Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên
đồ thị.
Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây
dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo
chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật
toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng
số (thuật toán Prim)…
Trang 12
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN
1. Khái niệm bài toán Tin học
Trong phạm vi tin học, người ta quan niệm bài toán là một công việc nào
đó mà con người muốn máy tính thực hiện. [xem 1]
Khi dùng máy tính để giải bài toán, ta cần quan tâm tới 2 vấn đề: Dữ liệu
mô phỏng thuật toán dạng liệt kê các bước:
Bước 1. Nhập số nguyên dương N;
Bước 2. Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc;
Bước 3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
Bước 4. i 2;
Bước 5. Nếu
(*)
][ Ni thì thông báo N là nguyên tố rồi kết thúc;
Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết
thúc;
Bước 7. i i + 1 rồi quay lại bước 5;
3. Các tính chất của thuật toán
Dựa trên khái niệm về thuật toán và ví dụ ở trên ta thấy các thao tác trong
thuật toán phải được mô tả đủ chi tiết để một đối tượng cứ tiến hành thực hiện
theo đúng thứ tự các thao tác đó là có thể cho ra output dựa trên input tương
ứng. Một thuật toán phải đảm bảo được các tính chất sau:
Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết
thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo.
Trang 14
Tính đúng đắn: Sau khi thực hiện thuật toán ta phải nhận được đúng
Output cần tìm.
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện.
Tính tổng quát: Thuật toán là đúng đắn với mọi bộ dữ liệu đầu vào của
bài toán.
Tính hiệu quả:
- Hiệu quả về thời gian: Ta quan tâm tới thời gian cần thiết để thực
hiện xong thuật toán đó. Thời gian đó phải nằm trong giới hạn cho phép.
- Hiệu quả về không gian: Dung lượng bộ nhớ cần thiết để lưu trữ
các đối tượng như bộ Input, bộ Output, kết quả trung gian và chương trình
tính dẫn đến khái niệm về Độ phức tạp của thuật toán. Thời gian thực hiện một
thuật toán bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Một yếu
tố cần chú ý nhất đó là kích thước của dữ liệu đầu vào. Dữ liệu càng lớn thì thời
gian xử lý càng chậm. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực
hiện của một thuật toán có thể biểu diễn một cách tương đối như một hàm của n:
T(n). Thực tế, T(n) không những chỉ phụ thuộc vào kích thước n mà còn phụ
thuộc vào đặc tính, tình trạng thực tế của bộ dữ liệu đầu vào.
Ví dụ, với thuật toán sắp xếp dãy số đã cho thành dãy tăng dần thì thời
gian sắp xếp còn phụ thuộc vào dãy đầu vào đã là dãy tăng dần, dãy được sinh
ngẫu nhiên hay được sắp xếp theo thứ tự ngược lại. Vì thế cần phải xem xét các
trường hợp tốt nhất, trung bình và xấu nhất. [Xem 2]
Việc xác định độ phức tạp của một thuật toán bất kỳ có thể rất phức tạp.
Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một
số quy tắc đơn giản:
4.1. Quy tắc max
Trang 16
Nếu thuật toán T có thời gian thực hiện T(n) =O(f(n)+g(n)) thì có thể coi
T có độ phức tạp là O(max(f(n), g(n)))
4.2. Quy tắc tổng
Nếu thuật toán T gồm hai đoạn thuật toán liên tiếp T1 và T2 và nếu T1 có
thời gian thực hiện T1(n) = O(f(n)), T2 có thời gian thực hiện là T2(n) = O(g(n))
thì thời gian thực hiện T sẽ là:
T(n) = T1(n) + T2(n) = O(f(n)+ g(n))
4.3. Quy tắc nhân
Nếu đoạn chương trình T có thời gian thực hiện là T(n) = O(f(n)). Khi đó,
nếu thực hiện k(n) lần đoạn chương trình T với k(n) = O(g(n)) thì độ phức tạp sẽ
là O(g(n).f(n))
4.4. Một số tính chất
Theo định nghĩa về độ phức tạp tính toán ta có một số tính chất:
N
3
2
n
1
0
0
1
1
2
2
1
2
4
8
4
4
409
65536
32
5
160
1024
32768
4292967296
Ví dụ: Tính giá trị của đa thức P(x)=a
n
x
n
+a
n-1
x
n-1
+ +a
1
x+a
0
với a
2
)1(
nn
lần câu lệnh
sau do nên thời gian tính toán tỉ lệ thuận với n
2
.
Vậy độ phức tạp tính toán của thuật toán trên là O(n
2
).
Thuật toán 2: Vì x
n
=x * x
n-1
nên có thể tận dụng kết quả của lần tính trước cho
lần tính sau:
Trang 18
1. Input n, a
0
, a
1
,a
2
,…a
n
mô tả hình thức: G = (V, E). Trong đó:
Trang 19
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể
coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.
Một số hình ảnh của đồ thị: Đồ thị vô hướng Đồ thị có hướng
6.1.2. Các khái niệm cơ bản
Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho
đồ thị G = (V, E). Ta có một số khái niệm sau [xem 3- tập 1]:
Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất
là 1 cạnh trong E nối từ u tới v.
Đa đồ thị: G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều
hơn 1 cạnh trong E nối từ u tới v.
Đồ thị vô hướng: G được gọi là đồ thị vô hướng nếu các cạnh trong E là không
định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u.
Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v) (v, u)
Đồ thị có hướng: G được gọi là đồ thị có hướng nếu các cạnh trong E là có định
hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối
từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự:
(u, v) (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô
Trang 20
hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v
bất kỳ tương đương với hai cung (u, v) và (v, u).
Ví dụ:
Trang 21
Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u = x
0
, x
1
,
, x
k
= v) thoả mãn (x
i
, x
i+1
) E (là 1 cạnh của đồ thị) với i: (0 i k). Đỉnh
u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không có
cạnh nào đi qua hơn 1 lần gọi là đường đi đơn.
Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu
trình. tương tự ta có khái niệm chu trình đơn.
6.2. Bài toán tìm kiếm trên đồ thị
6.2.1. Phát biểu bài toán
Cho đồ thị G = (V, E) và s và t là hai đỉnh của đồ thị.
Yêu cầu: Hãy chỉ ra một đường đi từ s đến t (nếu có).
Ví dụ: Xét một đồ thị vô hướng và một đồ thị có hướng dưới đây:
Trên cả hai đồ thị, (1, 2, 3, 4) là đường đi đơn độ dài 3 từ đỉnh 1 tới đỉnh
4. Bởi (1, 2) (2, 3) và (3, 4) đều là các cạnh (hay cung.
Làm sao để duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát
nào đó? Vấn đề này đưa về một bài toán liệt kê mà yêu cầu của nó là không
< 3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó >;
Begin
Trace[v] := u; {Truy vết đường đi}
DFS(v); {Gọi đệ quy duyệt bắt đầu với v}
Trang 23
End;
End;
Begin
<Input: đồ thị G, s, t >;
<Khởi tạo: Tất cả các đỉnh đều chưa bị đánh dấu >;
DFS(s);
<Output:
- Nếu t chưa bị đánh dấu thì kết luận: Không có đường từ s->t>;
- Nếu t đã bị đánh dấu thì dựa vào Trace tìm đường đi từ s->t>;
>;
End.
b. Thuật toán tìm kiếm theo chiều rộng BFS (Breadth – First – Search)
Ý tưởng của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Khi
thăm một đỉnh ta sẽ lên lịch thăm tất cả các đỉnh kề nó sao cho thứ tự duyệt là
ưu tiên chiều rộng (đỉnh nào gần s hơn sẽ được duyệt trước). Ví dụ: Bắt đầu, ta
thăm đỉnh s. Quá trình thăm S sẽ lên lịch duyệt những đỉnh (u
1
, u
2
, , u
p
) kề với
s (những đỉnh gần s nhất). Tiếp theo sẽ thăm đỉnh u
1
lên lịch sau chắc chắn xa hơn các đỉnh đã lên lịch (vào hàng) rồi. Chính vì
nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới
dạng hàng đợi (Queue).
Ta sẽ dựng giải thuật như sau:
Bước 1: Khởi tạo: free[s] = true; free[v] = false v V\{s}
First:=1; Last:=1; Queue[Last]:=s;//Queue chỉ chứa s
Trang 24
Bước 2: Lặp cho tới khi Queue rỗng:
u := pop;//lấy u khỏi hàng đợi
free[u]:= false;
Xét v V: nếu v chưa được thăm:
Free[v] = false;//đánh dấu đã thăm
Trace[v] = u;
Push(v);//đẩy v vào hàng đợi, chờ được thăm
Bước 3: Truy vết tìm đường đi hoặc thông báo không thấy đường.
6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS
Quá trình tìm kiếm trên đồ thị bắt đầu từ một đỉnh có thể thăm tất cả các
đỉnh còn lại, khi đó cách biểu diễn đồ thị [xem 3 – tập 1] có ảnh hưởng lớn tới
chi phí về thời gian thực hiện giải thuật:
Trong trường hợp ta biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán
BFS và DFS đều có độ phức tạp tính toán là O(n + m) = O(max(n, m)). Đây là
cách cài đặt tốt nhất. Nếu ta biểu diễn đồ thị bằng ma trận kề thì độ phức tạp tính
toán trong trường hợp này là O(n + n
2
) = O(n
2
). Nếu ta biểu diễn đồ thị bằng
danh sách cạnh, thao tác duyệt những đỉnh kề với đỉnh u sẽ dẫn tới việc phải
duyệt qua toàn bộ danh sách cạnh, đây là cài đặt tồi nhất, nó có độ phức tạp tính
Thuật toán Ford-Bellman có thể phát biểu rất đơn giản:
Với đỉnh xuất phát S. Gọi d(v) là khoảng cách từ S tới v.
Ban đầu d(S) được khởi gán bằng 0 còn các d(v) với v S được khởi gán
bằng +.
Sau đó ta tối ưu hoá dần các d(v) như sau: Xét mọi cặp đỉnh u, v của đồ
thị, nếu có một cặp đỉnh u, v mà d(v) > d(u) + c(u, v) thì ta đặt lại d(v) := d(u) +
c(u, v). Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ
S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có
và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v.
Chú ý rằng ta đặt c[u, v] = + nếu (u, v) không là cung. Thuật toán sẽ kết thúc
khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa.
Tính dừng của thuật toán:
Tại bước lặp 0: Bước khởi tạo d(S) = 0; d(v) := + với v S: thì dãy d(v)
chính là độ dài đường đi ngắn nhất từ S tới v đi qua không quá 0 cạnh
Trang 26
Giả sử tại bước lặp thứ i, d(v) bằng độ dài đường đi ngắn nhất từ S tới v
qua không quá i cạnh, thì do tính chất: đường đi từ S tới v qua không quá i + 1
cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó
qua không quá i cạnh, rồi đi tiếp tới v bằng cung (u, v). Nên độ dài đường đi
ngắn nhất từ S tới v qua không quá i + 1 cạnh sẽ được tính bằng giá trị nhỏ nhất
trong các giá trị: (Nguyên lý tối ưu Bellman)
Độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh
Độ dài đường đi ngắn nhất từ S tới u qua không quá i cạnh cộng với trọng
số cạnh (u, v) (u)
Nên sau bước lặp tối ưu các d(v) bằng công thức d(v)
bước i+1
= min(d(v)
bước
i
d[u] nhỏ nhất, và cố định nhãn đỉnh u.
Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo
công thức:
d[v] := min(d[v], d[u] + c[u, v])
Bước lặp sẽ kết thúc khi mà đỉnh đích t được cố định nhãn (tìm được
đường đi ngắn nhất từ s đến t); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự
do đều có nhãn là + (không tồn tại đường đi).
Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn,
giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn
tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t],
trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh
được cố định nhãn do d[s] = 0.
Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông
báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[t] =
+). Có thể mô tả ngắn gọn thuật toán bằng giả mã như sau:
Bước 1: d[s] = 0 ; d[v] = + (v V\{s}); u = s;
Copyright: Tài liệu đại học ©