Phương pháp chc song song

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

Đề tài:

PHƯƠNG PHÁP CHC SONG SONG

Giáo viên hướng dẫn:

Đỗ Trung Kiên

Nhóm sinh viên:

Phạm Thị Thảo (K54B)

Lê Việt Thanh (K55C)

Nguyễn Quang Hưng (K55C)

Vũ Văn Đán (K55C)

Mai Khánh Nguyên (K55C)

Hà Nội, 16-04-2008

1

Lời nói đầu

Những năm gần đây, cùng với sự phát triển của khoa học kỹ thuật, người ta

đã giải quyết được nhiều bài toán hóc búa bằng máy tính. Nhưng bên cạnh đó, vẫn

còn khá nhiều các bài toán vẫn chưa tìm được giải thuật phù hợp để giải nó, đó là

các bài toán tối ưu, trí tuệ nhân tạo và các bài toán xuất phát từ thực tế cuộc sống

như bài toán lập lịch, bài toán điều khiển Robot, bài toán người du lịch,... Đây là các

bài toán có khá nhiều ràng buộc phức tạp, không rõ ràng, ko gian tìm kiếm lớn. Do

đó các phương pháp truyền thống như quay lui vét cạn, leo đồi, mô phỏng luyện

thép, … tỏ ra ít hiệu quả, và người ta đã sử dụng một phương pháp khá tối ưu đó là

phương pháp CHC và sử dụng trong mô hình song song.

Trong bài nghiên cứu này nhóm tác giả nghiên cứu về phương pháp CHC sử

dụng mô hình song song để giải quyết bài toán MAXSAT. Chúng ta sẽ thấy được sự

độ tối ưu khi sử dụng mô hình song song so với mô hình tuần tự về thời gian, độ

thích nghi …

Trong tương lai nhóm sẽ tiếp tục phát triển đề tài nghiên cứu bằng cách sử

dụng thuật toán để giải quyết một số bài toán khác.

Nhóm tác giả xin chân thành cảm ơn sự giúp đỡ tận tình của thầy giáo Đỗ

Trung Kiên đã giúp cho nhóm trong quá trình thực hiện.

Cuối cùng xin chúc hội nghị nghiên cứu khoa học của chúng ta thành công

rực rỡ.

Hà Nội, tháng 04 năm 2008.

Nhóm tác giả.

2