XỬ LÝ SONG SONG.doc

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI

KHOA CÔNG NGHỆ THÔNG TIN

-------***-------

BÁO CÁO KHOA HỌC

Chuyên đề: Xử lí song song

Đề tài: Thuật toán nhánh cận trên

môi trường song song

Giáo viên hướng dẫn : Th.s Đỗ Trung Kiên

Sinh viên thực hiện : Nguyền Thị Bích Nhật

Phạm Thị Thuỳ

Trần Thị Thanh Tâm

Bùi Thu Hường

Trần Thị Hoa

Nguyễn Chí Công

Hà Nội, 15/04/2008

1

MỤC LỤC

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

NHÁNH CẬN .............................................................................................................................. 2

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 ............................................................................................................................................... 7

* Nhóm các lớp yêu cầu ....................................................................................................................... 8

* Nhóm các lớp cung cấp ................................................................................................................... 10

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

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

2.1.2. Thuật toán ............................................................................................................................... 12

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

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

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

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

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

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

* Tính cận và phân nhánh .................................................................................................................. 28

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

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

NHÁNH CẬN

2

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à !( )!

!

k n k

n

C

k

n

−

=

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

3