Đề tài: Sử dụng thuật toán luyện kim song song giải quyết bài toán Maxsat

MỤC LỤC

Chương I: Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing = SA)

I. Giới thiệu chung về thuật toán SA

II. Mô hình toán học của thuật toán SA

1. Không gian trạng thái

2. Hàm nhiệt độ

3. Hàm chi phí và hàm sức khoẻ

4. Sự phân bố trạng thái giới hạn

5. Sự hội tụ và điều kiện dừng

Sự hội tụ

Điều kiện dừng

Chương II: Xây dựng khung thuật toán SA

I. Lý do xây dựng khung thuật toán

II. Khung chung của thuật toán SA

III. Sơ đồ khung thuật toán

1. Lớp cung cấp (Provided)

2. Lớp đòi hỏi (Required)

3. Một số hàm quan trọng trong hai lớp Required và Provide

3.1. SA.pro.cpp

3.2. SA.req.cpp

Chương III: Ứng dụng của thuật toán SA

I. Bài toán MAXSAT

1. Giới thiệu bài toán

Hàm Main_Seq

III. Khung thuật toán SA song song giải quyết bài toán MAXSAT

1. Lựa chọn mô hình

2. Cài đặt Bài toán Maxsat.

2.1 Sử dụng thuật toán SA

2.1.1 Đọc file cấu hình

2.1.2 Lớp Problem đọc bài toán MAXSAT

2.1.3 Hàm khởi tạo nhiệt độ

2.1.4 Hàm khởi tạo lời giải

2.1.6 Hàm tính sức khoẻ

2.1.7 Hàm chấp nhận lời giải

2.1.8 . Hàm kết thúc thuật toán

2.2 Hàm void Solver_Lan::DoStep()

2.3 Hàm Main_Lan

Kết quả thực nghiệm

1. Kết quả tuần tự

2. Kết quả song son