Luận Văn tìm hiểu Thuật toán nhánh cận trên môi trường song song

MỤC LỤC




Chương 1 : TỔNG QUAN VỀ THUẬT TOÁN NHÁNH CẬN - 3 -

1.1. Thuật toán nhánh cận - 3 -

1.2. Một số ví dụ cụ thể áp dụng thuật toán nhánh cận - 4 -

Chương 2 : XÂY DỰNG KHUNG THUẬT TOÁN NHÁNH CẬN - 6 -

* Nhóm các lớp yêu cầu - 7 -

* Nhóm các lớp cung cấp - 9 -

2.1. Xây dựng khung nhánh cận - 11 -

2.1.1. Cấu trúc dữ liệu - 11 -

2.1.2. Thuật toán - 11 -

2.2. Xây dựng khung nhánh cận tuần tự - 14 -

2.3. Xây dựng khung nhánh cận song song - 15 -

2.3.1. Lược đồ song song dữ liệu tập trung - 18 -

2.3.2. Lược đồ song song dữ liệu phân tán - 20 -

2.4. Công cụ phát triển hệ thống - 24 -

2.5. Lựa chọn mô hình phát triển hệ thống - 25 -

Chương 3 : SỬ DỤNG THUẬT TOÁN NHÁNH CẬN ĐỂ GIẢI QUYẾT BÀI TOÁN TSP - 27 -

* Bài toán TSP (Bài toán người du lịch) - 27 -

3.1. Giới thiệu bài toán - 27 -

3.2. Định nghĩa bài toán - 27 -

3.3. Sử dụng thuật toán nhánh cận để giải bài toán TSP - 28 -

3.4. Chương trình thực thi - 31 -





Chương 1 : TỔNG QUAN VỀ THUẬT TOÁN

NHÁNH CẬN


Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước, nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó, không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó, chỉ ghi nhận các kết quả tốt hơn lúc ban đầu. Nghiệm của bài toán sẽ tốt dần lên do khi tìm ra kết quả tốt hơn ta sẽ cập nhật lại giá trị hiện thời của bài toán.


1.1. Thuật toán nhánh cận

Một trong những bài toán đặt ra trong thực tế là tìm một nghiệm của bài toán thỏa mãn một số điều kiện nào đó và nghiệm đó là tốt nhất theo một tiêu chí cụ thể, nghiên cứu lời giải các bài toán tối ưu thuộc về lĩnh vực quy hoạch toán học. mô hình được sử dụng để tìm kiếm là mô hình cây phân cấp . việc tìm nghiệm của các bài toán thường phải dựa vào việc liệt kê toàn bộ các cấu hình có thể và đánh giá tìm ra cấu hình tốt nhất.

Ví dụ: Bài toán người du lịch: không gian trạng thái là N!

Bài toán K- median : không gian trạng thái là

Khi đó, không gian tìm kiếm của bài toán là rất lớn trong khi nhiều trường hợp có thể loại bỏ được ngay. Điều này gây nên tình trạng lãng phí bộ nhớ và mất rất nhiều thời gian. Vấn đề đặt ra là trong quá trình liệt kê lời giải cần tận dụng những thông tin đã có để loại bỏ sớm những phương án chắc chắn không tối ưu. Thuật toán nhánh cận được sử dụng để khắc phục những vấn đề trên

Tư tưởng cơ bản của thuật toán là trong quá trình tìm kiếm lời giải, ta sẽ phân hoạch tập các phương án của bài toán thành hai hay nhiều tập con biểu diễn như một nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận các nút, tìm cách loại bỏ các nhánh cây (những tập con các phương án của bài toán) mà ta biết chắc chắn không phải là phương án tối ưu. Mặc dù trong trường hợp tồi nhất thuật toán sẽ trở thành duyệt toàn bộ, nhưng những trường hợp cụ thể nó rút ngắn đáng kể thời gian tìm kiếm.

Để áp dụng phương pháp nhánh cận đối với 1 tập các bài toán tối ưu chúng ta cần làm theo các bước sau:

ã Bước1 ( khởi tạo): L:={П0}, Q: ={П0},bs:= -∞ và T:= (tập hợp rỗng).

ã Bước 2( tìm kiếm): đi tới Bước 9 nếu L =

đi đến Bước 3 sau khi lựa chọn Пi:= s(Ls) để kiểm tra.

ã Bước 3 (cập nhật ): Nếu lower_bound(Пi)> bs, thì bs:= lower_bound(Пi) và T:={σ } với σ là lời giải khả thi của Пi sao cho f(x,σ )= lower_bound(П i). Đi tới bước 4.

ã Bước 4 : đi tới Bước 8 nếu Пi G (tập hợp các bài toán bộ phận Пi được giải trong tiến trình tính toán cận trên của Пi). ngược lại thì đi đến Bước 5.

ã Bước 5: ( kiểm tra cận trên): đi đến bước 8 nếu cận trên nhỏ hơn bs: upper_bound(Пi) ≤ bs. Ngược lại đi tới bước 6.

ã Bước 6: đi tới bước 8 nếu tồn tại một Пk (≠ Пi) Q mà f(Пk) ≥ f(Пi). Ngược lại đi tới bước 7.

ã Bước7: (phân nhánh): Phân và cập nhật . Quay trở lại bước 2.

ã Bước 8 ( kết thúc bài toán con): gán L:= L - Пi sau đó quay trở lại bước 2.

ã Bước 9 ( kết thúc toàn bộ ) : Dừng. bs = f(П0) và T lưu trữ một lời giải tối ưu của П0, nếu bs = - ∞ , П0 không có lời giải