THUẬT TOÁN LUYỆN KIM SONG SONG (Parallel Simulated Annealing Algorithms) GIẢI QUYẾT BÀI TOÁN MAX-SAT

Tham khảo sách thuật toán luyện kim song song (parallel simulated annealing algorithms) giải quyết bài toán max-sat, tài liệu phổ thông, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
THUẬT TOÁN LUYỆN KIM SONG SONG (Parallel Simulated Annealing Algorithms) GIẢI QUYẾT BÀI TOÁN MAX-SATTHUẬT TOÁN LUYỆN KIM SONGSONG (Parallel Simulated AnnealingAlgorithms) GIẢI QUYẾT BÀI TOÁN MAX-SATChương I: Tổng quan thuật toỏn mụ phỏng luyện kim (SimulatedAnnealing = SA) .................................................................................... 5 I. Giới thiệu chung về thuật toỏn SA............................................... 5 II. Mụ hỡnh toỏn học của thuật toỏn SA ....................................... 8 1. Khụng gian trạng thỏi ................................................................ 8 2. Hàm nhiệt độ .............................................................................. 9 3. Hàm chi phớ và hàm sức khoẻ ................................................ 10 4. Sự phõn bố trạng thỏi giới hạn ................................................ 11 5. Sự hội tụ và điều kiện dừng ..................................................... 12 Sự hội tụ ....................................................................................... 12 Điều kiện dừng ............................................................................. 12Chương II: Xõy dựng khung thuật toỏn SA ........................................ 13 I. Lý do xõy dựng khung thuật toỏn.............................................. 13 II. Khung chung của thuật toỏn SA ............................................. 13 III. Sơ đồ khung thuật toỏn............................................................ 16 1. Lớp cung cấp (Provided) ......................................................... 17 2. Lớp đũi hỏi (Required) ............................................................ 22 3. Một số hàm quan trọng trong hai lớp Required và Provide . 24 3.1. SA.pro.cpp ............................................................................ 24 3.2. SA.req.cpp ............................................................................ 25 1Chương III: Ứng dụng của thuật toỏn SA ........................................... 26 I. Bài toỏn MAXSAT ...................................................................... 26 1. Giới thiệu bài toỏn.................................................................... 26 Hàm Main_Seq ................................................................................ 29 III. Khung thuật toỏn SA song song giải quyết bài toỏn MAXSAT 30 1. Lựa chọn mụ hỡnh ................................................................... 30 2. Cài đặt Bài toỏn Maxsat. ......................................................... 31 2.1 Sử dụng thuật toỏn SA ....................................................... 31 2.1.1 Đọc file cấu hỡnh ........................................................... 31 2.1.2 Lớp Problem đọc bài toỏn MAXSAT ............................. 31 2.1.3 Hàm khởi tạo nhiệt độ .................................................... 33 2.1.4 Hàm khởi tạo lời giải...................................................... 34 2.1.6 Hàm tớnh sức khoẻ ........................................................ 36 2.1.7 Hàm chấp nhận lời giải.................................................. 37 2.1.8 . Hàm kết thỳc thuật toỏn .............................................. 38 2.2 Hàm void Solver_Lan::DoStep() ....................................... 38 2.3 Hàm Main_Lan ................................................................... 39 Kết quả thực nghiệm .......................................................................... 40 1. Kết quả tuần tự ........................................................................... 40 2. Kết quả song song ...................................................................... 40 23 BÁO CÁO KHOA HỌCĐỂ TÀI: THUẬT TOÁN LUYỆN KIM SONG SONG (Parallel Simulated Annealing Algorithms) GIẢI QUYẾT BÀI TOÁN MAX-SATMỞ ĐẦU - Nhiều bài toỏn tối ưu chưa cú thuật toán chính xác để giải quyết cho nờn cần cú một thuật toỏn gần đúng để tỡm lời giải gần tối ưu. - Khụng gian lời giải cần tỡm là rất lớn nếu một mỏy tớnh tỡm kiếm sẽ rất lõu nờn cần nhiều mỏy giải quyết và cỏc mỏy phải thực hiện đồng thời. Điều này cú thể thực hiện dễ dàng nếu cỏc mỏy tớnh tớnh toỏn song song. Vỡ vậy việc tỡm hiểu về cỏc thuật toỏn song song là cần thiết và mang tớnh khả thi đối với cỏc bài toỏn tối ưu - Để rỳt ngắn thời gian lập trỡnh chỳng ta cần xõy dựng khung thuật toỏn giỳp giải quyết cỏc bài toỏn khỏc nhanh chúng hơn. - Mục đích của đề tài này là sử dụng thuật toỏn luyện kim song song ...