Giải bài toán người du lịch qua phép dẫn về bài toán chu trình Hamilton

Bài viết Giải bài toán người du lịch qua phép dẫn về bài toán chu trình Hamilton giới thiệu một thuật toán hiệu quả để giải quyết bài toán trên theo cách dẫn nó về bài toán chu trình Hamilton với thuật toán tìm chu trình Hamilton được đề xuất.
Nội dung trích xuất từ tài liệu:
Giải bài toán người du lịch qua phép dẫn về bài toán chu trình Hamilton TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP QUẢNG NINH Giải bài toán ngƣời du lịch qua phép dẫn về bài toán chu trình Hamilton Nguyễn Thị Thúy Chinh*, Nguyễn Huy Hoàng Trường Đại học Công nghiệp Quảng Ninh *E-mail: nguyenthuychinh86qui@gmail.com Tóm tắt: Bài toán người du lịch được nhiều người biết đến với độ khó và phức tạp, đặc biệt với trường hợp có dữ liệu đầu vào lớn. Giải thuật láng giềng gần nhất là một trong các giải thuật heuristic được áp dụng để giải bài toán người du lịch trong trường hợp với dữ liệu đầu vào lớn. Việc tìm ra một thuật toán heuristic hiệu quả hơn vẫn là một trong những hướng nghiên cứu được nhiều nhà khoa học quan tâm. Bài báo giới thiệu một thuật toán hiệu quả để giải quyết bài toán trên theo cách dẫn nó về bài toán chu trình Hamilton với thuật toán tìm chu trình Hamilton được đề xuất. Từ khoá: Bài toán người du lịch; Bài toán Hamilton; Chu trình Hamilton; Thuật toán tham lam 1. ĐẶT VẤN ĐỀ Bài toán người du lịch (Travelling Salesman Problem - TSP) là bài toán có phát biểu đơn giản nhưng lại được đánh giá là một trong những bài toán kinh điển và khó trong trường hợp tổng quát với không gian dữ liệu đầu vào lớn. Nó được đánh giá là khó bởi các thuật toán hiệu quả nhất lại có thời gian xử lý tăng dần theo cấp số nhân của n, hay độ phức tạp thuật toán tăng theo hàm số mũ [3]. Có rất nhiều cách giải quyết bài toán này như thuật toán vét cạn, thuật toán người láng giềng gần nhất, kỹ thuật nhánh cận, nhưng mới chỉ hiệu quả với các bộ dữ liệu nhỏ. Trong khuôn khổ bài báo này, tôi xin giới thiệu một phương pháp giải bài toán người du lịch bằng cách dẫn về bài toán chu trình Hamilton, với thuật toán tìm chu trình Hamilton được đề xuất có thể cải thiện hiệu quả giải quyết bài toán với bộ dữ liệu lớn hơn. 2. GIỚI THIỆU BÀI TOÁN NGƯỜI DU LỊCH VÀ BÀI TOÁN CHU TRÌNH HAMILTON 2.1. Bài toán ngƣời du lịch 2.1.1. Phát biểu bài toán người du lịch Bài toán người du lịch (Travelling Salesman Problem - TSP) [4] là một bài toán trong lĩnh vực tối ưu tổ hợp được nhiều người biết đến. Nội dung của nó khá đơn giản, nó được phát biểu như sau: Một người du lịch xuất phát từ thành phố của anh ta, anh ta muốn tìm một đường đi đi qua tất cả các thành phố, mỗi thành phố đi đúng một lần và sau đó trở về thành phố ban đầu sao cho chi phí là ít nhất. Tên gọi bài toán người du lịch mang tính chất tượng trưng, nó dùng để gọi chung cho các bài toán có mô hình toán học như trên mặc dù phát biểu có nội dung khác, chẳng hạn bài toán tìm chu trình sản xuất cho một nhà máy hóa chất sao cho chi phí xúc rửa các thiết bị (như bể chứa, ống dẫn, ...), mỗi khi chuyển từ loại hóa chất này sang loại hóa chất khác của chu trình là ít nhất. Trong một số ứng dụng khác, khái niệm thành phố có thể thay đổi thành khách hàng, các mảnh DNA trong gen, các điểm hàn trên bảng mạch và khái niệm chi phí có thể biểu diễn bởi thời gian du lịch hay khoảng cách, hay giống như sự so sánh giữa các mảnh DNA với nhau [8]. Trong lý thuyết của độ phức tạp tính toán, bài toán TSP là bài toán khó, thuộc lớp NP- Complete. Nên nó không có giải thuật hiệu quả nào có thể áp dụng cho mọi trường hợp, đặc biệt với các trường hợp có số lượng thành phố lớn. 250 Kỷ yếu Hội nghị KHCN lần 7, tháng 5/2022 TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP QUẢNG NINH Bài toán TSP có thể phát biểu dưới ngôn ngữ đồ thị: Cho đồ thị G = (V, E), trong đó V là tập các đỉnh, E là tập các cạnh, mỗi cạnh được gán trọng số. Tìm chu trình Hamilton có tổng trọng số là nhỏ nhất. Trong đó, các đỉnh của đồ thị tương ứng với các thành phố và các cạnh thì tương ứng với đường nối giữa các thành phố, trọng số gán cho mỗi cạnh là chi phí di chuyển giữa hai thành phố. Một đường đi trong bài toán TSP là một chu trình Hamilton trên đồ thị và một lời giải tối ưu của bài toán là chu trình Hamilton ngắn nhất. Việc tìm chu trình Hamilton trong một đồ thị đầy đủ là dễ, nên các bài toán mà không phải hai thành phố nào cũng được nối với nhau có thể được chuyển đổi thành đồ thị đầy đủ, bằng cách thêm những cạnh có độ dài lớn giữa các thành phố này, những cạnh này sẽ không xuất hiện trong chu trình tối ưu. 2.1.2. Giải bài toán TSP với thuật toán người láng giềng gần nhất Khi dữ liệu đầu vào bài toán TSP có kích thước nhỏ, thì ưu tiên sử dụng các thuật toán giải chính xác cho kết quả nhanh và duy nhất như thuật toán vét cạn. Nhưng khi dữ liệu đầu vào lớn, thì thuật toán giải chính xác không còn hiệu quả do thời gian xử lý quá lâu. Lúc này, người ta quan tâm và ưu tiên tới hiệu suất tính toán và khi đó thuật toán heuristic được sử dụng. Tuy không thể đưa ra kết quả tối ưu nhất nhưng sai số so với giải pháp tối ưu nhất không nhiều, có thể chấp nhận được. Thuật toán láng giềng gần nhất là một trong những thuật toán heuristic như vậy. Giải thuật người láng giềng gần nhất (Nearest Neighbour - NN) (hay còn gọi là giải thuật tham lam – Greedy Algorithm) [6] là giải thuật cho người du lịch chọn thành phố gần nhất chưa thăm trong lần di chuyển tiếp theo. Thuật toán này bắt đầu từ một thành phố tùy ý, duyệt lần lượt tất cả các cạnh kề với nó rồi lựa chọn đỉnh có cạnh nối với đỉnh hiện tại đang xét có chi phí là thấp nhất để đưa vào hành trình. Lại tiếp tục xét các đỉnh kề với đỉnh mới đưa vào hành trình, như vậy cho đến khi không còn đỉnh nào để xét nữa thì thuật toán dừng. Các đỉnh đưa vào hành trình cần thỏa mãn 2 yêu cầu: - Không tạo thành một chu trình thiếu (không đi qua đủ n đỉnh). - Không tạo thành một đỉnh có nhiều hơn hai cạnh xuất phát từ một đỉnh, do yêu cầu của bài toán là mỗi thành phố chỉ được đến một lần: một lần đến và một lần đi. Độ phức tạp của thuật toán là O(n2) Tuy nhiên, khi áp dụng thuật toán này sẽ có ...