Nhánh cận

Giới thiệu

Trong thực tế có rất nhiều bài toán yêu cầu tìm ra nghiệm theo một số điều kiện nào đó, và phương án đó là tốt nhất theo một tiêu chí cụ thể nào đó. Những bài toán như vậy được gọi là bài toán tối ưu. để giải một bìa toán tối ưu, chúng ta có thể có rất nhiều cách, nhưng cũng có thể không có cách nào khác ngoài việc phải vét cạn toàn bộ rồi so sánh xem nghiệm nào thoả mãn hết các tiêu chí mà ta định nghĩa là tối ưu rồi chọn lấy nghiệm đó. Tối ưu ở đây có thể là một giá trị lớn nhất hay giá trị nhỏ nhất trong những tình huống nhất định nào đó.

Ví dụ như từ nhà đến trường chúng ta phải đi qua rất nhiều con đường, do vậy có nhiều cách đi khác nhau qua những con đường này. Mỗi cách đi đó mang nhiều giá trị như độ dài đường đi, thời gian đi, chi phí đi, ...Việc chúng ta lựa chọn cách đi nào tối ưu là phụ thuộc vào việc chúng ta lấy tiêu chí nào để so sánh. Chẳn hạn ta lấy tiêu chí đường đi ngắn nhất làm tiêu chí thì cách đơn giản nhất là ta liệt kê ra tất cả các cách đi cũng quảng đường tương ứng. Sau đó so sánh các quản đường rồi tìm ra cách đi tốt nhất. đây chính xác là cách làm của quay lui - vét cạn. Nhưng nếu ta có cách nào đó để dự đoán được trước những những cách đi mà sẽ dài hơn cách ta đã chọn trước thì ta không cần thử những cách này nữa, đó chính là phương pháp nhánh cận, là một sự cải tiến của phương pháp quay lui, cho phép ta tìm ra nghiệm tối ưu nhanh hơn.

Tư tưởng nhánh cận

Vì cải tiến dựa trên quay lui, nên trước tiên chúng ta cũng mô hình hoá nghiệm thành một vector X = (x₁, x₂, ...,x_n), mỗi thành phần x_i (i=1, 2,...,n) được chọn ra từ tập S_i. Mỗi nghiệm X của bài toán được xác định đôt tốt bang một hàm f(x) và mục tiêu là tìm ra nghiệm X có giá trị f(x) là nhỏ nhất ( hoặc lớn nhât) tuỳ theo ngữ cảnh.

Tư tưởng chính của nhánh cận như sau: Giả sử ta đã xây dung được k thành phần từ x₁ đến x_k, giờ ta chuẩn bị mở rộng thành phần thứ x_k+1 từ x_k. Nhưng khi đánh giá ta lại thấy tất cả các nghiệm mở rộng từ x_k không có nghiệm nào có giá trị tốt hơn giá trị tối ưu ta đã biết tại thời điểm đó, vậy thì ta không cần mở rộng nữa, như vậy ta đã cắt bỏ đi một nhánh, giảm được số nghiệm phải tìm rất nhiều.

điều khó nhất ở đây là phải đánh giá được các nghiệm mở rộng, nếu đánh giá được tốt, thuật toánh nhánh cận sẽ chạy nhanh hơn rất nhiều so với vét cạn.

Mô hình tổng quát

Trong ví dụ trên, Bestsolution là giá trị nghiệm tốt nhất đã biết ở thời điểm đó, thụ tục <Cập nhật BestSolution> sẽ xác định độ tốt nghiệm mới tìm thấy rồi so sánh với BestSolution, nếu tốt hơn sẽ thay thế BestSolution là nghiệm mới tìm thấy.

Ví dụ

Bài toán người đi du lịch

Cho n thành phố đánh số từ 1 đến n và các tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi mảng C[1..n,1..n], Cij=Cji là chi phí đi đoạn đường trực tiếp từ thành phố i đến thành phố j.

Một người du lịch xuất phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng 1 lần rồi quay lại thành phố 1. Hãy chỉ ra cho người đó hành trình với chi phí ít nhất. Bài toán được gọi là bài toàn người đi du lịch, hay người chào hang ( Travelling Salesman Problem - TSP)

Input: Tệp "TSP.INP" có dạng:

- Dòng đầu chứa số n ( 1<n<=20), là số thành phố

- n dòng tiếp theo, mỗi dòng n số mô tả mảng C

Output: Tếp :TSP.OUT" có dạng:

- Dòng đầu là chi phí ít nhất.

- Dòng thứ 2 mô tả hành trình

Giải

Bước 1: Mô hình hoá bài toàn

Hành trình cần tìm có dạng vector X ( x1, x2, ...xn, x1).

điều kiện nghiệm:

• • X1 =1, hành trình cuối cùng phải quay về thành phố đầu tiên

  • xi và xi+1 là hai thành phố liên tiêp trong hành trình phải có đường đi trực tiếp tới nhau.

  • Trừ thành phố 1, không có thành phố nào được lặp lại 2 lần, nghĩa là xi != xj với mọi i,j

Bước 2: Duyệt quay lui

x2 có thể chọn trong các thành phố mà x1 có đường đi tới, với mỗi x2 ta chọn các x3 là một trong các thành phố mà x2 có đường đi tới (trừ x1). Tổng quát là xi có thể chọn từ các thành phố mà xi-1 có đường đi tới.

Bước 3: Thực hiện nhánh cận

đầu tiên ta khởi tạo giá trị BestSolution = + vô cực.

Với mỗi bước chọn xi, xem chi phí đường đi cho tới lúc đó có nhỏ hơn BestSolution không, nếu không nhỏ hơn thì thử giá trị khác ngay bởi đi tiếp cũng chỉ tốn thời gian.

Khi thử được giá trị xn, ta kiểm tra xem xn có đi trực tiếp về 1 được không, nếu được ta cộng chi phí đi từ 1 đến n với chi phí đi trực tiếp từ n về 1 xem có nhỏ hơn BestSolution khong, nếu nhỏ hơn ta cấp nhật lại BestSolution cho cách đi mới.

Code: Xem trang 77 ( SGK chuyên tin quyển 1 - HSD)

Bài tập

Làm tiếp bài máy rút tiền ATM trang 78 - SGK chuyên tin quyển 1 - HSD và một số bài toán dưới đây