Đồ Án Môn Học Thuật Toán và Phương Pháp Giải Quyết Vấn Đề TRAVELLING SALESMAN PROBLEM (Full)



Bài toán Người du lịch, tìm đường đi ngắn nhất cho người thương nhân (salesman), hay còn gọi là người chào hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố duy nhất một lần và quay về thành phố ban đầu với chi phí rẻ nhất, được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn giáo trình Lý thuyết đồ thị nổi tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-khó). Người ta bắt đầu thử và công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa.

Bài tiểu luận này sẽ trình bày cách giải bài toán này theo hướng tiếp cận nhánh cận theo quy trình xây dựng giải pháp cho vấn đề. Với quy mô của một tiểu luận môn học thì ở đây chỉ trình bày thuật toán theo cách đơn giản nhất, cùng với một số cài đặt đi kèm.


NỘI DUNG:


MỞ ĐẦU 4

Chương 1. GIỚI THIỆU TỔNG QUAN VỀ BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN 5

1.1 Vấn đề và bài toán 5

1.2 Độ phức tạp của bài toán - Các lớp bài toán 6

1.1.1. Khái niệm các loại thời gian tính 6

1.1.2. Bài toán quyết định 7

1.1.3. Khái niệm quy dẫn 8

1.1.4. Lớp bài toán P 8

1.1.5. Lớp bài toán NP 8

1.1.6. Lớp bài toán Co-NP 9

1.1.7. Lớp bài toán NP-Complete (NP-Đầy đủ) 9

1.1.8. Lớp bài toán NP-Hard (NP-Khó) 9

Chương 2. GIỚI THIỆU HEURISTIC VÀ METAHEURISTIC 12

2.1 Heuristic 12

2.2 Metaheuristic 13

2.3 Thuật giải nhánh cận 13

2.3.1. Bài toán tối ưu 13

2.3.2. Ý tưởng 14

2.3.3. Mô hình 14

Chương 3. BÀI TOÁN NGƯỜI ĐƯA THƯ 16

3.1 Các khái niệm cơ bản về đồ thị 16

4.1.1. Định nghĩa đồ thị 16

3.1.1.1 Đồ thị vô hướng 16

3.1.1.2 Đồ thị có hướng 16

3.1.1.3 Đơn đồ thị và đa đồ thị 16

4.1.2. Bậc của đỉnh 17

4.1.3. Bậc của đỉnh 17

4.1.4. Đồ thị Euler và đồ thị Hamilton 17

3.2 Bài toán người đưa thư 18

4.2.1. Phát biểu bài toán và lịch sử bài toán người đưa thư 18

4.2.2. Mô hình hóa vấn đề 20

3.2.1.1 Vấn đề thực tế và vấn đề cần giải quyết 20

3.2.1.2 Xây dựng mô hình 22

4.2.3. Thiết kế thuật toán / thuật giải 22

4.2.4. Chứng minh tính đúng đắn 28

4.2.5. Phân tích thuật toán / thuật giải 28










LINK DOWNLOAD (TÀI LIỆU VIP MEMBER)



Bài toán Người du lịch, tìm đường đi ngắn nhất cho người thương nhân (salesman), hay còn gọi là người chào hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố duy nhất một lần và quay về thành phố ban đầu với chi phí rẻ nhất, được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn giáo trình Lý thuyết đồ thị nổi tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-khó). Người ta bắt đầu thử và công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa.

Bài tiểu luận này sẽ trình bày cách giải bài toán này theo hướng tiếp cận nhánh cận theo quy trình xây dựng giải pháp cho vấn đề. Với quy mô của một tiểu luận môn học thì ở đây chỉ trình bày thuật toán theo cách đơn giản nhất, cùng với một số cài đặt đi kèm.


NỘI DUNG:


MỞ ĐẦU 4

Chương 1. GIỚI THIỆU TỔNG QUAN VỀ BÀI TOÁN VÀ ĐỘ PHỨC TẠP CỦA BÀI TOÁN 5

1.1 Vấn đề và bài toán 5

1.2 Độ phức tạp của bài toán - Các lớp bài toán 6

1.1.1. Khái niệm các loại thời gian tính 6

1.1.2. Bài toán quyết định 7

1.1.3. Khái niệm quy dẫn 8

1.1.4. Lớp bài toán P 8

1.1.5. Lớp bài toán NP 8

1.1.6. Lớp bài toán Co-NP 9

1.1.7. Lớp bài toán NP-Complete (NP-Đầy đủ) 9

1.1.8. Lớp bài toán NP-Hard (NP-Khó) 9

Chương 2. GIỚI THIỆU HEURISTIC VÀ METAHEURISTIC 12

2.1 Heuristic 12

2.2 Metaheuristic 13

2.3 Thuật giải nhánh cận 13

2.3.1. Bài toán tối ưu 13

2.3.2. Ý tưởng 14

2.3.3. Mô hình 14

Chương 3. BÀI TOÁN NGƯỜI ĐƯA THƯ 16

3.1 Các khái niệm cơ bản về đồ thị 16

4.1.1. Định nghĩa đồ thị 16

3.1.1.1 Đồ thị vô hướng 16

3.1.1.2 Đồ thị có hướng 16

3.1.1.3 Đơn đồ thị và đa đồ thị 16

4.1.2. Bậc của đỉnh 17

4.1.3. Bậc của đỉnh 17

4.1.4. Đồ thị Euler và đồ thị Hamilton 17

3.2 Bài toán người đưa thư 18

4.2.1. Phát biểu bài toán và lịch sử bài toán người đưa thư 18

4.2.2. Mô hình hóa vấn đề 20

3.2.1.1 Vấn đề thực tế và vấn đề cần giải quyết 20

3.2.1.2 Xây dựng mô hình 22

4.2.3. Thiết kế thuật toán / thuật giải 22

4.2.4. Chứng minh tính đúng đắn 28

4.2.5. Phân tích thuật toán / thuật giải 28










LINK DOWNLOAD (TÀI LIỆU VIP MEMBER)

M_tả
M_tả

Không có nhận xét nào: