Bài toán người du lịch với ma trận chi phí
- 1. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 1 LỜI MỞ ĐẦU Thuật ngữ thuật toán [Algrithm] là từ viết tắt của tên một nhà toán học nổi tiếng người Ai Cập ở thế kỷ thứ IX: Abu Ja’fa Mohammed ibn Musa al- Khowarizmi. Ông là người viết hai quyển sách nổi tiếng là “Sơ lược về các phép tính trên Al jafar và Al Mukabal” và “Hệ đếm Ấn Độ”. Đầu tiên, thuật toán được hiểu như là các quytắc thực hiện các phép toán sốhọc với các con số được viết trong hệ thập phân. Cùng với sự phát triển của máy tính, khái niệm thuật toán cũng được hiểu theo nghĩa rộng hơn. Một định nghĩa hình thức về thuật toán được nhà toán học người Anh là Alan Mathison Turing là cha đẻ của ngành khoa học máy tính đưa ra vào năm 1936 thông qua máy Turing. Có thể nói lý thuyết thuật toán được hình thành từ đó. Định nghĩa một cách trực quan thì thuật toán là một bản liệt kê các chỉ dẫn, các quy tắc cần thực hiện theo từng bước xác định nhằm giải quyết một bài toan đã cho trong khoảng thời gian hữu hạn. Một thuật toán bao gồm các tính chất sau: Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác. Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnhminh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định. Tính khách quan: Một thuật toán dù được viết bởi nhiều ngườitrên nhiều máy tính vẫn phải cho kết quả như nhau. Tính phổ dụng: Thuật toán không chỉáp dụng cho một bàitoán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau. Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán. Phân tích và thiết kế thuật toán là một lĩnh vực quan trọng của khoa học máy tính. Phân tích thuật toán giúp cho người thiết kế giải thuật có thể tiên liệu được các tài nguyên mà thuật toán yêu cầu như: bộ nhớ, băng thông, thiết bị ngoại vi, … Song yếu tố quan trọng nhất chính là thời gian thực hiện giải thuật. Trong bài viết này, chúng em xin trình bày những hiểu biết của mình về bài toán tối ưu trong việc tìm đường đi ngắn nhất sử dụng những kiến thức liên quan đến đồ thị và ứng dụng những kiến thức đã học được từ môn Phân tích và đánh giá thuật toán để giải quyết bài toán “Có n thành phố và giữa các cặp thành phố xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố, qua tất cả các thành phố còn lại và quay lại vị trí xuất phát. Tìm hành trình có chi phí nhỏ nhất.” Tìm đường đi ngắn nhất trong đồ thị được ứng dụng nhiều trong các bài toán tìm đường đi ngắn tối ưu giữa hai điểm trong mạng giao thông, đường đi ngắn nhất của gói tin giữa các nút mạng máy tính…
- 2. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 2 Do thời gian và kiến thức còn hạn chế nên trong quá trình trình bày chắc chắn không tránh khỏi những sai sót, rất mong nhận được sự góp ý của Thầy Giáo và các bạn học viên trong lớp. Chúng em xin gửi lời cảm ơn thầy giáo, PGS.TS Đào Thanh Tĩnh và các bạn trong lớp học đã tạo điều kiện thuận lợi và giúp đỡ em hoàn thành bài tập này. Xin chân thành cảm ơn! Nhóm học viên thực hiện Lê Đình Hưng Đỗ Thanh Liên Lương Thúy Vượng
- 3. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 3 CHƯƠNG I: PHÂN TÍCH BÀI TOÁN 1. Phát biểu bài toán Có n thành phố và giữa các cặp thành phố xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố, qua tất cả các thành phố còn lại và quay lại vị trí xuất phát. Tìm hành trình có chi phí nhỏ nhất. Giải bài toán bằng phương pháp gần đúng. So sánh hiệu quả với phương pháp vét cạn. 2. Giới thiệu về bài toán người đi du lich Bài toán người đi du lịch là một vấn đề kết nối tối ưu trong nghiên cứu khoa học máy tính. Cho một danh sách các thành phốvà các cặp khoảng cách giữa hai thành phố trong đó, nhiệm vụ là phải tìm một chu kỳ ngắn nhất để thăm mỗi thành phố một lần duy nhất. Hình 1. Ví dụ về bài toán người đi du lịch Trong hình trên, tour đề người đi du lịch có thể thăm hết các thành phố với chi phí ngắn nhất có thể được thể hiện bằng cạnh màu đỏ. Vấn đề bài toán người đi du lịch được nêu ra đầu tiên như là vấn đề toán học đầu tiên vào năm 1930và là vấn đề được tập trung nghiên cứu nhiều nhất trong lĩnh vực tối ưu. Nó được sử dụng trong thực nghiệm, đánh giá các thuật toán tối ưu. Tuy vấn đề có tính phức tạp cao, những được sử dụng rất nhiều phương pháp chinh xác và gần đúng[xấp xỉ] đã được biết đến, do đó có thể giải được vài trường hợp có đến 10 ngàn thành phố. Trong những năm 1950 và 1960, bài toán mở rộng trở nên phổbiến trong giới khoa học Châu Âu và Bắc Mỹ. Các công trình nghiên cứu đáng kể đầu tiên được thực hiện bởi George Dantzig, Delbert Ray Fulkerson và Selmer M.Johnson người đã đề xuất bài toán như một chương trình tuyến tính và phát triển phương pháp cận nhánh cho bài toán. Với các phương pháp mới họ đã giải quyết một trường hợp với 49 thành phốmột cách tối ưu bằng cách xây dựng một chu trình và chứng minh rằng không có chu trình nào ngắn hơn vào năm 1954, cho đến năm 2004 bài toán giải quyết được với số đỉnh
- 4. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 4 nên đến 24.978 đỉnh dự báo sẽ còn tiếp tục tăng nên nữa. Trong nhiều thập kỷ liên tiếp sau đó, bàitoán được nghiên cứu trong rất nhiều ngành như Toán rời rạc; khoa học máy tính; hóa học; vật lý… 3. Mô tả chi tiết bài toán người đi du lịch Bài toán người đi du lịch có thể biểu diễn thành một đồ thị, trong đó các thành phố được biểu diễn dưới dạng các đỉnh, các con đường đi lại giữa các thành phố là các cạnh và chi phí đi lại giữa các thành phố được biểu diễn dưới dạng giá trị các cạnh nối các đỉnh. Tất nhiên, đồ thị sau khi được xây dựng dựa vào các đỉnh và chi phí đi lại giữa các thành phố là đồ thị hoàn chỉnh và đủ, giữa hai thành phố không có đường đi trực tiếp được nối với nhau mà phải thông qua một hoặc nhiều thành phố trung gian khác ta gán trọng số của cạnh đó với số lớn nhất có thể [thường là ∞]. Khi đó, bài toán người đi du lịch trở thành bài toán tìm chu trình Hamilton ngắn nhất, và lộ trình của người du lịch chinh là chu trình Hamilton ngắn nhất. A B C D E D A 0 3 93 13 33 9 B 4 0 77 42 21 6 C 45 17 0 36 16 28 D 39 90 80 0 56 7 E 28 46 88 33 0 25 F 3 88 18 46 92 0 Nếu như khoảng cách giữa hai thành phố bất kỳ là như nhau cho cả hai hướng thì dung đồthịvô hướng, ngược lại ta sửdụng đồthịcó hướng. Trong ví dụ trên, ta giả định đường đi từ 2 hướng là như nhau. Trường hợp khoảng cách giữa hai thành phố trong đồ thị là khoảng cách Metric[tức là khoảng cách thỏa mãn bất đẳng thức tam giác sau Cij 1 vào Sum và gán min bằng Min[sum, min]. Sum-=canh i->1. 3. Lặp lại quá trình sau: Lấyđỉnh từ stackra, nếu đỉnh này không còn đỉnh kề thỏa mãn yêu cầu thì Pop đỉnh và trọng số này ra, nếu có đỉnh thỏa mãn thì thoát vòng lặp và duyệt tiếp từ đỉnh này, trường hợp lấy đỉnh từ stack ra là 0 thì Pop 2 lần để lấy 2 đỉnh liên tục trong stack ra sau đó tiếp tục vòng lặp.
- 6. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 6 Ví dụ về việc sử dụng thuật toán vét cạn đề giải quyết bài toán: Các bước Stack chứa đỉnh Stack trọng số Đỉnh đang xét Sum min 1 1 0 Ø 0 +∞ 2 1;0;4;3;2 0;0;1;6;3 1 0 +∞ 3 1;0;4;3;2;0;4;3 0;0;1;6;3;0;7;5 2 3 +∞ 4 1;0;4;3;2;0;4;3;0;4 0;0;1;6;3;0;7;5;0;2 3 8 +∞ 5 1;0;4;3;2;0;4;3;0;4;0 0;0;1;6;3;0;7;5;0;2;0 4 8+2+1=11 11 6 1;0;4;3;2;0;4 0;0;1;6;3;0;7 4 3 11 7 1;0;4;3;2;0;4;0;3 0;0;1;6;3;0;7;0;2 4 10 11 8 1;0;4;3;2;0;4;0;3;0 0;0;1;6;3;0;7;0;2;0 3 18 11 9 1;0;4;3 0;0;1;6 3 0 11 10 1;0;4;3;0;4;2 0;0;1;6;0;2;5 3 6 11 11 1;0;4;3;0;4;2;0;4 0;0;1;6;0;2;5;0;7 2 11 11 12 1;0;4;3;0;4;2;0;4;0 0;0;1;6;0;2;5;0;7;0 4 19 11 13 1;0;4;3;0;4 0;0;1;6;0;2 4 6 11 14 1;0;4;3;0;4;0;2 0;0;1;6;0;2;0;7 4 8 11 15 1;0;4;3;0;4;0;2;0 0;0;1;6;0;2;0;7;0 2 18 11 16 1;0;4 0;0;1 4 0 11 17 1;0;4;0;3;2 0;0;1;0;2;7 4 1 11 18 1;0;4;0;3;2;0;3 0;0;1;0;2;7;0;5 2 8 11 19 1;0;4;0;3;2;0;3;0 0;0;1;0;2;7;0;5;0 3 19 11 20 1;0;4;0;3 0;0;1;0;2 3 1 11 21 1;0;4;0;3;0;2 0;0;1;0;2;5 3 3 11 22 1;0;4;0;3;2;0 0;0;1;0;2;5;0 2 11 11 Kết thúc thuật toán ta tìm được chu trình Hamiltin là: 1=>2=>3=>4>=1 với chi phí là 11.
- 7. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 7 2. Giải thuật gần đúng[hay gọi là xấp xỉ] Thuật toán vét cạn ở trên cho ta một đáp án tối ưu, tuy nhiên độ phức tạp của thuật tán là quá cao [n-1]! Thuộc nhóm O[n!]. Do đó, trong thực tế người ta chấp nhận các giải thuật cho kết quả tốt[những không phải lúc nào cũng tốt] bởi sự đơn giản, nhanh chóng và cài đặt dễ dàng. Ở trong phần này chúng tôi giới thiệu hai thuật toán gần đúng để giải quyết bàitoán: đólà thuật toán láng giềng gần nhất và nhánh cận để giảiquyết bài toán. 2.1.Giải thuật láng giềng gần nhất Thuật toán láng giềng gần nhất hay còn gọi là giải thuật tham lam. Trong giải thuật này, tại mỗi bước, ta chọn con đường [cạnh] nối với thành phố [đỉnh] gần nhất với hi vọng rằng n con đường ngắn nhất sẽ cho ra đường đi ngăn nhất. Ý tưởng của thuật toán láng giềng gần nhất: là tìm kiếm lựa chọn tối ưu cục bộ tại mỗi bước với hi vọng tìm được tìm được tối ưu toàn cục khi kết thúc. Tại mỗi bước lựa chọn, thuật toán này chọn “miếng ngon nhất” được xác định bằng hàm chọn “ngon nhất” [có thể là giá trị max hoặc min, hoặc theo1 ý nghĩa nào đó tùyvào bài toán cụ thể và nếu cóthể “ăn” trở thành nghiệm của bài toán] được thì “ăn” luôn; nếu không nó sẽ bỏđi và không xem xét lại. Thuật toán láng giềng gần nhất: Input C=[cij] Output tour// hành trình tối ưu Cost; // Chi phí tương ứng của các hành trình Mô tả: Tour := Ø ; Cost:=0; v:=u; // Khởi tạo ∀𝑘 ≔ 1 → 𝑛 ;// Thăm tất cả các thành phố; // Chọn cạnh kề. Chọn[u, w] là đoạn nối 2 thành phố có chi phí nhỏ nhất từ thành phố V đến các thành phố chưa đi qua. Tour := Tour+ [u, w]; // cập nhật hành trình. Cost := Cost +Cv,w // cập nhật chi phí. // Hoàn thành chuyến đi. Độ phức tạp của thuật toán tham lam: Thuật toán tham lam có độ phức tạp nhỏ hơn nhiều sovới giải thuật vét cạn, chiphí chogiải thuật là n[n- 1]/2 thuộc nhóm O[n2 ]. Tour := Tour+[v, w]; Cost := Cost + Cvw Tuy nhiên, đã nói ở trên giải thuật này không phải luôn luôn đúng, trong một số trường hợp, lời giải của thuật toán tham lam là rất tệ.
- 8. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 8 Ví dụ 1: minh họa giải thuật tham lam với n=5 Đáp án của thuật toán láng giềng gần nhất thường là tốt[tuykhông phải tối ưu] vì đáp án tối ưu của bài toán trên là: 1=>3=>4=>5=>3=>1 với chi phí là 10 so với kết quả của thuật toán tham lam là 14. Ví dụ 2: Cho ma trận chi phí: ∞ 48 43 54 31 20 ∞ 30 63 22 C= 29 64 ∞ 4 7 6 19 2 ∞ 8 1 28 7 18 ∞ Bước 1: Từ thành phố1 ta chọn đích là thành phố5[chi phí=31 thấp nhất] Tour := Ф; Cost := 0; u=1; w =5; Bước 2: Từ thành phố5 ta chọn đích là thành phố3[chi phí=7 thấp nhất] Tour := ; Cost := 31; u=5; w =3; Bước 3: Từ thành phố3 ta chọn đích là thành phố4[chi phí=4 thấp nhất] Tour := {, } ; Cost := 38; u=4; w =4; Bước 4: Từthành phố4 ta chọn đích là thành phố 2[thành phốcuối chưa đi đến chi phí =19] Tour := {, ,} ; Cost := 42; u=2; w =19;
- 9. đi du lịch Hoc viên: Lê Đình Hưng; Đỗ Thanh Liên; Lương Thúy Vượng Trang 9 Bước 5: Từ thành phố 2 ta quay lại thành phố 1[chi phí=20] Tour := {, ,, } ; Cost := 61; u=5; w =20; Tour := {, ,,,} ; Cost := 81; Theo thuật toán tham lam ta có hành trình như sau: 1 => 5 => 3 => 4 =>2 >1. Chi phí: 31+7+4=19+20 =81. Cài đặt và code thuật toán tham lam: int GTS[mat c, int n, tin TUOR[max], int Ddau] { int v; // đỉnh đang xét int k; // duyệt qua n đỉnh để chọn int w; // đỉnh được chọn trong mỗi bước int mini; // chọn min các cạnh trong mỗi bước int COST; trọng số nhỏ nhất của chu trình int daxet[max]; // danh sách các đỉnh được sử dụng for [k=1; k