Tài liệu Báo cáo áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị

lOMoARcPSD|16911810 Nhóm07-Áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị Công nghệ phần mềm (Trường Đại Học Điện Lực) StuDocu is not sponsored or endorsed by any college or university Downloaded by Dung Nguyen ([email protected]) lOMoARcPSD|16911810 TRƯỜNG ĐẠI HỌC ĐIỆN LỰC KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN NHẬP MÔN TRÍ TUỆ NHÂN TẠO ĐỀ TÀI: Áp dụng thuật giải heuristic cho bài toán tô màu tối ưu trên đồ thị Sinh viên thực hiện : PHẠM VĂN TUẤN Giảng viên hướng dẫn NGUYỄN HOÀNG HIỆU NGUYỄN DỨC THUẬN : VŨ VĂN ĐỊNH Ngành : CÔNG NGHỆ THÔNG TIN Chuyên ngành : HỆ THỐNG THƯƠNG MẠI ĐIỆN TỬ Lớp : D14HTTMDT1 Khóa : 2019 Hà Nội, tháng 10 năm 2021 Phiếu chấm điểm Downloaded by Dung Nguyen ([email protected]) lOMoARcPSD|16911810 STT Họ tên sinh viên Nội dung thực hiện 1 Phạm Văn Tuấn Làm báo cáo Làm chương trình 2 Nguyễn Hoàng Hiệu Làm báo cáo Làm chương trình 3 Nguyễn Đức Thuận Làm báo cáo Làm chương trình Họ tên giảng viên Chữ ký Downloaded by Dung Nguyen ([email protected]) Điểm Chữ ký Ghi chú lOMoARcPSD|16911810 MỤC LỤC I. GIỚI THIỆU BÀI TOÁN..................................................................................................................4 1. Tổng quan về heuristic..................................................................................................................4 1.1. Heuristic và các cách biểu diễn đồ thị.......................................................................................4 1.2. Các bài toán điển hình................................................................................................................6 2. Bài toán tô mầu đồ thị...................................................................................................................6 2.1. Bài toán tô mầu cạnh..................................................................................................................6 2.2. Bài toán tô mầu đỉnh..................................................................................................................6 2.3. Các khái niệm liên quan.............................................................................................................7 2.4. Ứng dụng......................................................................................................................................8 II. 1. 2. III. GIẢI THUẬT.................................................................................................................................9 Bài toán tô mầu đỉnh.....................................................................................................................9 1.1. Các định nghĩa sử dụng:........................................................................................................9 1.2. Thuật toán............................................................................................................................10 1.3. Ví dụ......................................................................................................................................12 Bài toán tô mầu cạnh...................................................................................................................17 2.1. Giải thuật..............................................................................................................................17 2.3. Độ phức tạp:.........................................................................................................................23 CÀI ĐẶT THUẬT TOÁN...........................................................................................................24 1. Bài toán tô mầu đỉnh.......................................................................................................................24 2. Bài toán tô mầu cạnh.......................................................................................................................30 2.1. Đọc dữ liệu từ fle..................................................................................................................30 2.2. Dữ liệu vào từ bàn phím........................................................................................................40 3. IV. Mã nguồn......................................................................................................................................51 TÀI LIỆU THAM KHẢO...........................................................................................................52 PHỤ LỤC 1: DANH MỤC CÁC HÌNH ẢNH TRONG TÀI LIỆU...................................................53 PHỤ LỤC 2: PHÂN CHIA CÔNG VIỆC..............................................................................................53 Downloaded by Dung Nguyen ([email protected]) lOMoARcPSD|16911810 I. GIỚI THIỆU BÀI TOÁN 1. Thuật giải heuristic 1.1.khái niệm heuristic  Là mở rộng khái niệm thuật toán. o Thuờng o Nhanh tìm lời giải tốt nhưng không tốt nhất. chóng tìm ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn. o Thuờng thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con nguời. Các nguyên lý của thuật giải heuristic  Vét cạn thông minh  Nguyên lý thứ tự Nguyên lý tham lam Hàm heuristic Kyỹ thuật heuristic:  Theo Từ điển tiêếng Anh Oxford: “Heuristics là nghệ thuật tm kiêếm chân lý. Nói riêng, heuristics là đặc trưng của quá trình học nhờ đó các học sinh học được cách tự tm ra cách giải thích các hiện tượng tự nhiên”.   Từ “Heuristics” có cùng một gôếc tiêếng Hy Lạp như từ Eureka. Feigenbaum Feldman đã đưa ra định nghĩa :  “Heuristics (Các quy tắếc heuristics, các phương pháp heuristics) là các quy tắếc, phương pháp, chiêến lược, mẹo giải hay phương cách nào đó nhắằm làm giảm khôếi lượng tm kiêếm lời giải trong không gian bài tóan cực lớn”. 2. Bài toán tô mầu đồ thị Tô màu đồ thị và sự tổng quát của nó là công cụ hữu dụng trong việc mô hình hóa rất nhiều bài toán khác nhau trong vấn đề xếp lịch, xây dựng chương trình và vấn đề phân công công việc. Bài toán tô màu đồ thị bao gồm nhiều loại: tô màu đỉnh đồ thị (vertex graph coloring) , tô màu cạnh đồ thị (edge graph coloring) ... 2.1. Bài toán tô mầu cạnh Bài toán Cho G=(V,E) là đơn đồ thị vô hướng ( G không là đồ thị khuyên) , hãy tìm cách gán (tô màu) cho mỗi cạnh của đồ thị một màu sao cho hai cạnh có cùng chung 1 đỉnh không bị tô bởi cùng một màu. Một phép gán màu cho các cạnh như vậy gọi là một phép tô màu cạnh đồ thị. Nói cách khác, phép tô cạnh đồ thị bởi k màu nói trên có thể được hiểu là một phân hoạch của tập cạnh E của G thành k tập con (tương ứng với k màu) sao cho mỗi tập con ứng với một màu i nhất định. Bài toán đặt ra là tìm cách tô màu nào sử dụng số màu ít nhất có thể. Ví dụ Downloaded by Dung Nguyen ([email protected]) lOMoARcPSD|16911810 Đồ thị trong hình trên có thể tô bởi 4 màu. Đồ thị G gọi là tô được bởi k màu-cạnh nếu G có một phép tô k màu-cạnh phù hợp.Thông thường hầu hết các đồ thị không là đồ thị khuyên đều tô được.Và nếu G có tính chất như vậy thì G cũng có thể tô bởi l màu với l>k. 2.2. Bài toán tô mầu đỉnh Một phép tô mầu sử dụng nhiều nhất k mầu gọi là một phép tô k mầu. Số lượng mầu nhỏ nhất cần để tô các đỉnh của đồ thị G gọi là sắc số đỉnh của đồ thị G, sao cho không có hai đỉnh kề nhau nào được tô cùng mầu. Một đồ thị có thể tô được bằng k mầu, trong đó mỗi một tập các đỉnh cùng mầu gọi là một lớp mầu. Một đồ thị có thể được tô bằng k mầu nghĩa là có có k tập độc lập trong đồ thị 2.3. Các nguyên lý của thuật giải heuristic 1.Vét cạn thông minh  Hạn chêế vùng không gian tm kiêếm và có sự định hướng để nhanh chóng tm đêến mục tiêu.  Tạo miêằn D’ râết nhỏ so với D  Vét cạn trên D’ 2.Nguyên lý tham lam (Greedy):  Lâếy tiêu chuẩn tôếi ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước.  a)Thuật giải GTS1: (Greedy-Traveling Saleman)  Xây dựng một lịch trình du lịch có chi phí Cost tôếi thiểu cho bài toán trong trường hợp phải qua n thành phôế với ma trận chi phí C và bắết đâằu tại một đỉnh U nào đó. Downloaded by Dung Nguyen ([email protected]) lOMoARcPSD|16911810                            W Thuật giải: Bước 1: {Khởi đâằu} Đặt Tour := {}; Cost := 0; V := U; {V là đỉnh hiện tại đang làm việc} Bước 2: {Thắm tâết cả các thành phôế} For k := 1 To n Do qua bước 3; Bước 3: {Chọn cung kêế tiêếp} Đặt (V, W) là cung có chi phí nhỏ nhâết tnh từ V đêến các đỉnh W chưa dùng: Tour := Tour + {(V,W)}; Cost := Cost + Cost(V,W); Nhãn W được sử dụng Đặt V := W; {Gán để xét bước kêế tiêếp} Bước 4: {Chuyêến đi hoàn thành} Đặt Tour := Tour + {(V,U)}; Cost := Cost + Cost(V,U); Dừng. U= A Tour = {} Cost = 0 V =A W ∈ {B, C, D, E}{Các đỉnh có thể đêến từ A} → W = B{Vì qua B có giá thành bé nhâết} Tour = {(A, B)} Cost = 1 V=B ∈ {C, D, E}→ W = EA  Tour = {(A, B),(B, E)}  Cost = 1 + 3 = 4  V =E W ∈ {C, D} → W = C b.Thuật giải GTS2:  Tạo ra lịch trình từ p thành phôế xuâết phát riêng biệt. Tìm chu trình của người bán hàng qua n thành phôế (1 - Xem thêm -