Phương pháp tham lam
ý tưởng phương pháp
Phương pháp tham lam là kỹ thuật thiết kế thường được dùng để giải các bài toán tối ưu. Phương pháp được tiến hành trong nhiều bước. Tại mỗi bước, theo một lựa chọn nào đó, sẽ tìm một lời giải tối ưu cho bài toán nhỏ tương ứng. Lời giải của bài toán được bổ sung dần từng bước từ lời giải của các bài toán con.
Các lời giải tìm được bằng phương pháp tham lam thường chỉ là chấp nhận được theo điều kiện nào đó, chưa chắc là tối ưu.
Cho trước một tập A gồm n đối tượng, ta cần phải chọn một tập con S của A. Với một tập con S được chọn ra thoả mãn các yêu cầu của bài toán, ta gọi là một nghiệm chấp nhận được. Một hàm mục tiêu gắn với mỗi nghiệm chấp nhận được với một giá trị. Nghiệm tối ưu là nghiệm chấp nhận được mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất (Lớn nhất).
Đặc trưng tham lam của phương pháp thể hiện bởi: Trong mỗi bước việc xử lý sẽ tuân theo một lựa chọn trước, không kể đến tình trạng không tốt có thể xảy ra khi thực hiện lựa chọn lúc đầu.
Mô hình
Chọn S từ tập A
Tính chất tham lam của thuật toán định hướng bởi hàm chọn
- Khởi động S= ?
- Trong khi A<> ? :
+ Chọn phần tử tốt nhất của A gán vào x: x = chọn(A)
+ Cập nhật đối tượng để chọn: A = A - {x}
+ Nếu S ? {x} thoả mãn yêu cầu bài toán thì cập nhật lời giải: S = S ? {x}


Bài toán người du lịch
Một người du lịch muốn tham quan n thành phố T1, T2, ., Tn. Xuất phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay lại đúng thành phố xuất phát.
Gọi CP(i,j) là chi phí đi từ thành phố Ti đến Tj. Hãy tìm hành trình thoả mãn yêu cầu bài toán sao cho chi phí là nhỏ nhất
ý tưởng
Đây là bài toán tìm chu trình có trọng số nhỏ nhất trong một đơn đồ thị vô hướng có trọng số.
Thuật toán tham lam cho bài toán là chon thành phố có chi phí nhỏ nhất tính từ thành phố hiện thời đến các thành phố chưa qua.
Thuật toán
Đầu vào: Số thành phố n, chi phí từ thành phố i đến thành phố j (cp(i,j))
Đầu ra: Hành trình tối ưu và chi phí tương ứng
Mô tả:
tour = 0
cost = 0
v = u
Với mọi k = 1 đến n:
Chọn (v,w) là đoạn nối hai thành phố có chi phí nhỏ nhất tính từ thành phố v đến các thành phố chưa qua.
tour = tour + (v,w)
cost = cost + cp(v,w)
Tour = tour + (v,u)
Cost = cost + cp(v,u)

Minh hoạ:
BTNDL.exe
Độ phức tạp của thuật toán
Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng lặp để duyệt. Nên chi phí cho thuật toán xác định bởi hai vòng lặp lồng nhau, nên T(n) là O(n2)
Cài đặt
Dim v1 As Byte
Dim k As Byte
Dim w As Byte
Dim m As Byte
Dim mini As Integer
Dim cost As Integer
Dim daxet(30) As Boolean
Dim cp(30, 30) As Integer
Dim dau As Byte
Dim tour(30) As Integer
Private Sub Cmdkq_Click()
m = txtstp.Text
Dim i As Integer
cost = 0
For k = 1 To m
daxet(k) = False
Next k
dau = InputBox("Chọn đỉnh xuất phát")
v1 = dau
i = 1
tour(i) = v1
daxet(v1) = True
While i < m
mini = 32767
For k = 1 To m
If Not daxet(k) Then
If mini > cp(v1, k) Then
mini = cp(v1, k)
w = k
End If
End If
Next k
v1 = w
i = i + 1
tour(i) = v1
daxet(v1) = True
cost = cost + mini
Wend
cost = cost + cp(v1, dau)
txttcp.Text = cost
txtct.Text = ""
For i = 1 To m
txtct.Text = txtct & tour(i) & " ==> "
Next i
txtct.Text = txtct & dau
End Sub
Chương trình
BTNDL.exe
Danh sách nhóm 1