Khóa Luận Tốt Nghiệp: Áp Dụng Thuật Toán Di Truyền Để Giải Bài Toán Người Du Lịch

Chuyên khảo toán học phân tích Áp dụng thuật toán di truyền để giải bài toán người du lịch, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Tác giả: Thái Công Danh
• Người hướng dẫn: TS. Nguyễn Đình Hoa Cương
• Trường học: Đại Học Kinh Tế Huế
• Chuyên ngành: Tin Học Kinh Tế
• Đề tài: Áp Dụng Thuật Toán Di Truyền Để Giải Bài Toán Người Du Lịch
• Loại tài liệu: Khóa Luận Tốt Nghiệp
• Năm xuất bản: 2017
• Địa điểm: Huế

Mục lục chi tiết

• LỜI CÁM ƠN
• DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÍ HIỆU
• DANH MỤC CÁC SƠ ĐỒ, ĐỒ THỊ
• DANH MỤC CÁC BIỂU BẢNG
• I. PHẦN I: ĐẶT VẤN ĐỀ
• I.1. Lý do chọn đề tài
• I.2. Mục tiêu nghiên cứu
• I.3. Đối tượng và phạm vi nghiên cứu
• I.4. Phương pháp nghiên cứu
• I.5. Nội dung khóa luận
• II. PHẦN II: NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU
• 1. CHƯƠNG 1: CƠ SỞ LÝ LUẬN
• 1.1. Bài toán người du lịch (Traveling Salesman Problem – TSP)
• 1.1.1. Lịch sử
• 1.1.2. Phát biểu bài toán
• 1.2. Lý thuyết độ phức tạp tính toán
• 1.2.1. Khái niệm
• 1.2.2. Các lớp độ phức tạp
• 1.2.3. Độ phức tạp của bài toán người du lịch
• 1.3. Thuật toán di truyền (Genetic Algorithm)
• 1.3.1. Lịch sử của thuật toán di truyền
• 2. CHƯƠNG 2: CÀI ĐẶT THUẬT TOÁN DI TRUYỀN ĐỂ GIẢI BÀI TOÁN NGƯỜI DU LỊCH
• 3. CHƯƠNG 3: THÍ NGHIỆM CHƯƠNG TRÌNH
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Thuật Toán Di Truyền và Bài Toán TSP

Bài toán người du lịch (TSP), hay còn gọi là bài toán người bán hàng, là một trong những bài toán tối ưu tổ hợp nổi tiếng. Bài toán yêu cầu tìm một lộ trình ngắn nhất để đi qua tất cả các thành phố, mỗi thành phố chỉ một lần và quay trở lại điểm xuất phát. Mặc dù phát biểu đơn giản, việc giải TSP, đặc biệt với số lượng lớn thành phố, là một thách thức lớn. Thuật toán di truyền (Genetic Algorithm) là một phương pháp metaheuristic được sử dụng rộng rãi để tìm kiếm giải pháp gần tối ưu cho bài toán này. GA mô phỏng quá trình tiến hóa tự nhiên, sử dụng các khái niệm như chọn lọc, lai ghép, và đột biến để cải thiện quần thể các giải pháp tiềm năng qua các thế hệ. Ưu điểm của giải thuật di truyền cho TSP là khả năng tìm kiếm trong không gian giải pháp rộng lớn mà không bị mắc kẹt trong các cực trị địa phương.

1.1. Khái niệm TSP Traveling Salesman Problem cơ bản

Bài toán người du lịch đặt ra yêu cầu tìm lộ trình ngắn nhất qua n thành phố, bắt đầu và kết thúc tại cùng một thành phố, mỗi thành phố ghé thăm đúng một lần. Trong đó, khoảng cách giữa các thành phố được xác định trước. Vấn đề này thuộc lớp NP-hard, có nghĩa là không có thuật toán nào tìm ra nghiệm tối ưu trong thời gian đa thức cho mọi trường hợp. Do đó, các phương pháp heuristic algorithm được sử dụng rộng rãi để tìm kiếm giải pháp chấp nhận được. Giải thuật sử dụng ma trận khoảng cách giữa các thành phố để tính toán chi phí hành trình.

1.2. Thuật toán di truyền Genetic Algorithm Giới thiệu và ưu điểm

Thuật toán di truyền là một phương pháp tìm kiếm và tối ưu hóa dựa trên cơ chế tiến hóa tự nhiên. Nó bắt đầu với một quần thể các giải pháp tiềm năng (nhiễm sắc thể), áp dụng các phép toán chọn lọc (selection), lai ghép (crossover), và đột biến (mutation) để tạo ra các thế hệ mới. Các cá thể có fitness function tốt hơn (trong trường hợp TSP là lộ trình ngắn hơn) sẽ có nhiều khả năng được chọn để lai ghép và tạo ra thế hệ sau. Ưu điểm của GA là khả năng khám phá không gian giải pháp rộng lớn và tránh được các cực trị địa phương.

II. Thách Thức và Vấn Đề Của Giải TSP Truyền Thống

Các phương pháp giải bài toán người du lịch truyền thống, như vét cạn hoặc quy hoạch động, trở nên bất khả thi khi số lượng thành phố tăng lên. Độ phức tạp tính toán tăng theo cấp số nhân, khiến thời gian tính toán trở nên quá lớn. Các phương pháp giải pháp tối ưu này không còn phù hợp với các bài toán thực tế có quy mô lớn. Do đó, cần có các phương pháp metaheuristic algorithm hiệu quả hơn để tìm kiếm các giải pháp gần tối ưu trong thời gian tính toán chấp nhận được. Điều kiện ràng buộc và mô hình hóa bài toán cũng là những yếu tố quan trọng cần xem xét.

2.1. Giới hạn về độ phức tạp tính toán của thuật toán vét cạn

Thuật toán vét cạn duyệt qua tất cả các hoán vị có thể của các thành phố, dẫn đến độ phức tạp tính toán là O(n!), với n là số lượng thành phố. Với số lượng thành phố tăng lên, thời gian tính toán tăng lên rất nhanh, làm cho thuật toán này không khả thi cho các bài toán có quy mô lớn. Ví dụ, với 20 thành phố, số lượng hoán vị là khoảng 2.4 x 10^18, cần một lượng lớn tài nguyên tính toán và thời gian để xử lý.

2.2. Khó khăn trong việc mô hình hóa bài toán với ràng buộc thực tế

Trong thực tế, bài toán người du lịch thường đi kèm với các điều kiện ràng buộc phức tạp, chẳng hạn như thời gian mở cửa của các địa điểm, giới hạn trọng tải của phương tiện vận chuyển, hoặc các yêu cầu về ưu tiên ghé thăm. Việc mô hình hóa bài toán để bao gồm các yếu tố này làm tăng độ khó của bài toán và đòi hỏi các phương pháp giải thuật tối ưu linh hoạt hơn.

III. Áp Dụng Thuật Toán Di Truyền Cho Bài Toán Người Du Lịch Chi Tiết

Áp dụng thuật toán di truyền để giải bài toán người du lịch bao gồm một số bước chính: mã hóa hành trình, khởi tạo quần thể ban đầu, tính fitness function, thực hiện các phép toán chọn lọc, lai ghép, và đột biến, và lặp lại quá trình này cho đến khi đạt được điều kiện dừng. Biểu diễn nhiễm sắc thể đóng vai trò quan trọng trong hiệu quả của thuật toán. Chọn lọc (Selection) đảm bảo các cá thể tốt có cơ hội sinh sản cao hơn. Lai ghép (Crossover) kết hợp các phần của hai nhiễm sắc thể cha mẹ để tạo ra các nhiễm sắc thể con. Đột biến (Mutation) giúp duy trì sự đa dạng trong quần thể.

3.1. Mã hóa hành trình và khởi tạo quần thể ban đầu

Một phương pháp phổ biến để mã hóa hành trình là sử dụng một danh sách các số nguyên, mỗi số đại diện cho một thành phố. Quần thể ban đầu có thể được tạo ngẫu nhiên hoặc sử dụng các phương pháp heuristic algorithm khác để tạo ra các giải pháp tốt hơn. Kích thước quần thể là một tham số quan trọng ảnh hưởng đến hiệu quả của thuật toán. Quần thể quá nhỏ có thể dẫn đến hội tụ sớm, trong khi quần thể quá lớn có thể làm tăng thời gian tính toán.

3.2. Hàm fitness function chọn lọc lai ghép và đột biến

Hàm fitness function đánh giá chất lượng của mỗi cá thể trong quần thể. Trong trường hợp TSP, hàm fitness thường là nghịch đảo của tổng độ dài hành trình. Chọn lọc (selection) chọn các cá thể tốt nhất để sinh sản, thường sử dụng các phương pháp như Roulette Wheel Selection hoặc Tournament Selection. Lai ghép (crossover) tạo ra các cá thể con bằng cách kết hợp các phần của hai cá thể cha mẹ. Đột biến (mutation) tạo ra sự thay đổi nhỏ trong nhiễm sắc thể để duy trì sự đa dạng của quần thể. Các tham số như tỷ lệ lai ghép và tỷ lệ đột biến cần được điều chỉnh cẩn thận để đạt được hiệu quả tốt nhất.

IV. Cải Tiến Hiệu Quả Thuật Toán Di Truyền Giải Bài Toán TSP

Để cải tiến thuật toán, cần tối ưu hóa các tham số như kích thước quần thể, tỷ lệ lai ghép, tỷ lệ đột biến. Sử dụng các kỹ thuật heuristic algorithm khác như 2-opt hoặc 3-opt để cải thiện các cá thể sau khi lai ghép hoặc đột biến. Phân tích hiệu năng và so sánh thuật toán với các phương pháp khác như thuật toán Heuristic algorithm giúp đánh giá và cải tiến hiệu quả của thuật toán. Ứng dụng thực tế vào các bài toán routing và logistics cho thấy tính hiệu quả của thuật toán trong các tình huống thực tế.

4.1. Tối ưu hóa tham số và tích hợp heuristic algorithm cục bộ

Việc điều chỉnh các tham số của thuật toán di truyền, chẳng hạn như kích thước quần thể, tỷ lệ lai ghép, và tỷ lệ đột biến, có thể ảnh hưởng đáng kể đến hiệu quả của thuật toán. Tích hợp các thuật toán heuristic algorithm cục bộ, như 2-opt, vào quá trình tìm kiếm có thể giúp cải thiện chất lượng của các giải pháp và giảm thời gian tính toán.

4.2. So sánh hiệu quả thuật toán và đánh giá hiệu năng

So sánh hiệu quả thuật toán di truyền với các thuật toán khác, chẳng hạn như thuật toán nhánh cận hoặc các thuật toán metaheuristic algorithm khác, có thể cung cấp thông tin về điểm mạnh và điểm yếu của thuật toán di truyền. Đánh giá hiệu năng của thuật toán dựa trên các tiêu chí như chất lượng giải pháp, thời gian tính toán, và độ ổn định.

V. Ứng Dụng Thực Tế Của Thuật Toán Di Truyền Trong Vận Tải và Logistics

Thuật toán di truyền được ứng dụng thực tế rộng rãi trong nhiều lĩnh vực, đặc biệt là trong routing, logistics, vận tải, và phân phối hàng hóa. Việc tối ưu hóa hành trình giúp giảm chi phí hành trình, cải thiện hiệu quả hoạt động, và tăng tính cạnh tranh. Ứng dụng trong các hệ thống vận tải thông minh giúp quản lý và điều phối phương tiện hiệu quả hơn. Các công ty logistics sử dụng GA để tối ưu hóa hành trình và giảm chi phí hành trình. Việc cài đặt thuật toán trong các ngôn ngữ như Python, Java, C++ giúp dễ dàng triển khai và tích hợp vào các hệ thống hiện có.

5.1. Tối ưu hóa hành trình và phân phối hàng hóa trong logistics

Trong lĩnh vực logistics, thuật toán di truyền có thể được sử dụng để tối ưu hóa hành trình cho các xe tải giao hàng, giảm chi phí hành trình và cải thiện hiệu quả giao hàng. Thuật toán có thể xem xét các yếu tố như thời gian giao hàng, giới hạn trọng tải, và khoảng cách giữa các điểm đến.

5.2. Ứng dụng trong routing và hệ thống vận tải thông minh

Trong lĩnh vực routing, thuật toán di truyền có thể được sử dụng để tìm đường đi ngắn nhất giữa hai điểm, xem xét các yếu tố như tình trạng giao thông, giới hạn tốc độ, và các tuyến đường cấm. Các hệ thống vận tải thông minh có thể sử dụng thuật toán di truyền để điều phối phương tiện và quản lý lưu lượng giao thông hiệu quả hơn.

VI. Kết Luận Tiềm Năng và Hướng Phát Triển Của Thuật Toán Di Truyền

Thuật toán di truyền là một công cụ mạnh mẽ để giải quyết bài toán người du lịch và các bài toán tối ưu hóa hành trình khác. Mặc dù không đảm bảo tìm ra giải pháp tối ưu, GA có thể tìm kiếm các giải pháp gần tối ưu trong thời gian tính toán chấp nhận được, đặc biệt với các bài toán có quy mô lớn. Các nghiên cứu tiếp theo có thể tập trung vào việc cải tiến thuật toán, tích hợp các kỹ thuật heuristic algorithm mới, và mở rộng ứng dụng thực tế vào các lĩnh vực khác. Các ngôn ngữ lập trình hướng đối tượng hỗ trợ tốt cho việc triển khai thuật toán.

6.1. Tổng kết hiệu quả và hạn chế của thuật toán di truyền

Thuật toán di truyền cung cấp một phương pháp hiệu quả để tìm kiếm các giải pháp gần tối ưu cho bài toán người du lịch, đặc biệt khi số lượng thành phố lớn. Tuy nhiên, thuật toán không đảm bảo tìm ra giải pháp tối ưu và có thể đòi hỏi thời gian tính toán đáng kể. Việc lựa chọn các tham số phù hợp và tích hợp các kỹ thuật heuristic algorithm là rất quan trọng để cải thiện hiệu quả của thuật toán.

6.2. Hướng nghiên cứu và phát triển giải pháp tối ưu trong tương lai

Các hướng nghiên cứu trong tương lai có thể tập trung vào việc cải tiến thuật toán di truyền, tích hợp các kỹ thuật heuristic algorithm mới, và khám phá các phương pháp mã hóa hành trình hiệu quả hơn. Việc phát triển các thư viện thuật toán di truyền dễ sử dụng cũng có thể giúp mở rộng ứng dụng thực tế của thuật toán trong nhiều lĩnh vực khác nhau.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: CƠ SỞ LÝ LUẬN 1. Bài toán người du lịch (Traveling Salesman Problem – TSP) 1. Lịch sử: Vấn đề toán học liên quan đến bài toán người du lịch đã được nghiên cứu từ những năm 1800 bởi nhà toán học Ai-Len William Rowan Hamilton và nhà toán học người Anh Thomas Penyngton Kirkman. Hamilton đã tạo ra một trò chơi gọi là Icosian vào năm 1857, trò chơi này yêu cầu người chơi phải hoàn thành một chu trình mà chỉ sử dụng những đường kết nối cho trước qua 20 đỉnh [12].

Bài toán người du lịch được nghiên cứu đầu tiên vào năm 1930 bởi nhà toán học và kinh tế học Karl Menger tại đại học Vienna và Harvard. Sau đó nó được nghiên cứu bởi Hassler Whitney và Merrill Flood tại đại học Princeton. Vào những năm 1940 bài toán người du lịch được nghiên cứu bởi những nhà thống kê học là Mahalanobis, Jessen, Gosh, và Marks liên quan đến các ứng dụng nông nghiệp, và nhà toán học Merill Flood phổ biến nó với các đồng nghiệp tại công ty RAND. Phương pháp giải của bài toán bắt đầu xuất hiện trong các tài liệu vào giữa những năm 1950, các tài liệu sử dụng một số thay đổi nhỏ về thuật ngữ "Bài toán người du lịch".

Trong những thế kỷ sau đó, bài toán được nghiên cứu bởi rất nhiều nhà toán học, khoa học máy tính, hóa học, vật lý và những ngành khoa học khác. Mặc dù bài toán người du lịch khá dễ hiểu, tuy nhiên nó rất khó giải quyết. Karp đã chứng minh vào năm 1972 rằng bài toán tìm chu trình Hamilton là bài toán NP-đầy đủ (NP-Complete). NP-khó (NP-hard), là một lớp các bài toán khó nhất trong NP, nói cách khác nó không có thuật toán nào có thể giải bài toán người du lịch trong thời gian đa thức.

Điều này cung cấp một sự giải thích khoa học cho sự khó khăn trong việc tìm ra chu trình tối ưu. Những phương pháp giải quyết bài toán người du lịch đã trở nên phức tạp và các phương pháp khả thi xuất hiện ngày càng nhiều. Dưới đây là một bảng tổng hợp mốc lịch sử của bài toán người du lịch : SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 4 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Bảng 1.1: Các cột mốc lịch sử của bài toán người du lịch Năm Người nghiên cứu Số thành phố giải được G.

Fulkerson, và 1954 49 thành phố S. Karp 64 thành phố P. Fratta, và 1975 67 thành phố F. Grötschel 120 thành phố H.

1980 318 thành phố Padberg 1987 M. Rinaldi 532 thành phố 1987 M. Grötschel và O. Holland 666 thành phố 1987 M.397 thành phố Chvátal, và W.509 thành phố Chvátal, và W.112 thành phố Chvátal, và W.978 thành phố Helsgaun 1.

Phát biểu bài toán: Có rất nhiều cách để phát biểu bài toán người du lịch, tuy nhiên tư tưởng của bài toán là giống nhau:  Bài toán người du lịch liên quan đến một người du lịch muốn thực hiện một chuyến đi qua một số thành phố sử dụng đường đi ngắn nhất có thể và thăm mỗi thành phố chỉ một lần sau đó trở về thành phố bắt đầu [18].  Nếu một người du lịch muốn thăm đúng một lần mỗi thành phố của một danh sách m thành phố (chi phí đi từ thành phố i tới thành phố j là cij) và sau đó trở về thành phố bắt đầu. Lộ trình ít tốn kém nhất mà người du lịch có thể đi là bao nhiêu [10] ?  Cho một danh sách các thành phố và đường đi giữa chúng, hãy tìm chu trình ngắn nhất có thể (chu trình Hamilton) đi qua mỗi thành phố đúng một lần [12]. Ta có thể phát biểu lại bài toán như sau: Có n thành phố mà một người du lịch muốn đi tham quan.

Giữa các thành phố đó có khoảng cách dài ngắn khác nhau. Xuất phát từ một thành phố bất kì, người đó SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 5 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay trở về thành phố ban đầu.  Yêu cầu: Hãy tìm hành trình với quãng đường đi là ngắn nhất.

- Ví dụ: Cho 4 thành phố với khoảng cách giữa các thành phố như hình sau: Hình 1.1: Ví dụ về bài toán người du lịch Xuất phát từ thành phố 1, chu trình ngắn nhất mà ta có thể tìm được chính là qua thành phố 2 , thành phố 4, thành phố 3 rồi trở về thành phố 1 với tổng độ dài là 80. 1 20 10 15 4 25 30 2 35 3 Tổng độ dài: 80 Hình 1.2: Chu trình với độ dài ngắn nhất SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 6 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Nếu phát biểu theo lý thuyết đồ thị, ta có thể dễ dàng liên tưởng các thành phố như các đỉnh của đồ thị, các đường đi chính là các cạnh và khoảng cách chính là trọng số của cạnh đó. Có thể phát biểu ngắn gọn bài toán theo lý thuyết đồ thị như sau: “Cho đồ thị đầy đủ (giữa 2 cạnh bất kì đều có đường đi).

Hãy tìm chu trình Hamilton với tổng các trọng số các cạnh trong chu trình là nhỏ nhất.” Chú thích: Chu trình Hamilton là chu trình xuất phát từ một đỉnh của đồ thị, đi qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần rồi quay lại đỉnh ban đầu. Trong phạm vi khóa luận này, chúng ta sẽ giải quyết bài toán người du lịch trong hệ trục tọa độ với mỗi đỉnh xác định bằng tung độ x và hoành độ y, và khoảng cách giữa chúng được tính bằng công thức: , (1) Mặc dù bài toán người du lịch rất dễ hiểu, nhưng giải quyết nó thì không hề đơn giản. Phần tiếp theo sẽ trình bày về lý thuyết độ phức tạp tính toán và phân tích độ phức tạp của bài toán người du lịch.Lý thuyết độ phức tạp tính toán:  Khái niệm Để phân loại các vấn đề đó theo độ khó của chúng, người ta đưa ra khái niệm lý thuyết độ phức tạp tính toán. Khái niệm: “Độ phức tạp tính toán là sự biểu thị toán học về độ khó của một vấn đề, chỉ sự hao tốn những tài nguyên được đòi hỏi bởi máy tính để giải vấn đề đó.

Quá trình nghiên cứu về những sự biểu thị đó được gọi là lý thuyết độ phức tạp tính toán và nó rất quan trọng trong nhiều nhánh của khoa học máy tính, đặc biệt là ngành mã hóa” [4].  Các lớp độ phức tạp Một lớp độ phức tạp là một tập hợp các vấn đề có độ phức tạp tương tự nhau. Trong Lý thuyết độ phức tạp thuật toán, có các lớp độ phức tạp đáng chú ý như sau: SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 7 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Bảng 1.2: Các lớp độ phức tạp thuật toán Lớp độ phức tạp Định nghĩa P là viết tắt của “polynomial”, tức là đa thức, là một trong những lớp cơ bản nhất trong các lớp độ phức tạp tính toán.

Một vấn đề được xếp vào lớp P, nếu như có P thuật toán có thể giải quyết bài toán trong thời gian đa thức. Ví dụ: với mỗi “đầu vào” N cho ra kết quả sau P(N) phép toán (cộng, trừ, nhân chia,…), trong đó P là một đa thức nào đó. NP là viết tắt của "nondeterministic polynomial time" (thuật toán bất định trong thời gian đa thức). Một vấn đề thuộc lớp NP khi có một thuật toán kiểm tra lời giải sao cho mỗi khi có 1 lời giải cho 1 input có NP độ dài N thì thuật toán kiểm tra lời giải sẽ cho biết là lời giải có đúng hay không sau không quá P(N) phép toán đơn giản, trong đó P là một đa thức (không phụ thuộc vào input).

Đây là lớp các bài toán khó nhất trong NP. mọi bài toán khác thuộc lớp NP NP-Complete đều có thể đưa được về một bài toán NP- complete cho trước bằng một phép biến đổi sử dụng một lượng thời gian là đa thức. Là lớp các bài toán ít nhất là khó NP-Hard bằng NP-Complete. Chú ý rằng NP-Hard không cần phải ở trong NP.

SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 8 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Vấn đề liệu P có bằng NP hay không vẫn là một vấn đề gây ra tranh cãi trong lý thuyết độ phức tạp tính toán. Trong khuôn khổ của khóa luận này, chúng ta sẽ không bàn đến vấn đề này. Để dễ hình dung, ta có thể thấy phạm vi của các lớp độ phức tạp tính toán qua hình vẽ sau: Hình 1.3: Mô tả các lớp độ phức tạp thuật toán [5]  Độ phức tạp của bài toán người du lịch Để giải bài toán người du lịch, ta cần phải tìm ra chu trình Hamilton với tổng trọng số các cạnh là nhỏ nhất.

Trong trường hợp đồ thị có ít đỉnh, ta có thể sử dụng phương án vét cạn tất cả các chu trình rồi tìm ra chu trình nhỏ nhất. Tuy nhiên, với số đỉnh của đồ thị tăng lên, thì phương án vét cạn là bất khả thi vì không có máy tính nào đủ nhanh để có thể duyệt qua các phương án đó trong thời gian ngắn. Bảng dưới đây thống kê số lượng các chu trình khi số đỉnh của đồ thị tăng lên: SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 9 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Bảng 1.3: Số lượng các chu trình khi số đỉnh của đồ thị tăng lên: Số đỉnh Số cạnh Số lượng chu trình 6 15 120 7 21 720 8 28 5,040 9 36 40,320 10 45 362,880 11 55 3,628,800 12 66 3.216451x1017 Với số đỉnh là n thì số chu trình sẽ là (n-1)! chu trình.

Với số đỉnh càng lớn thì số chu trình càng lớn. Ví dụ như với 20 đỉnh, số chu trình cần phải duyệt qua đến hơn 121 triệu tỷ chu trình. Với khả năng của các máy tính hiện tại thì việc giải chính xác bài toán này với những trường hợp như vậy dường như là bất khả thi. Các nghiên cứu đã chứng minh rằng bài toán người du lịch thuộc lớp các bài toán có độ phức tạp NP-Complete [15], điều này chứng tỏ vẫn chưa có lời giải cho bài toán này trong thời gian đa thức.

Đây hiện vẫn là một trong những bài toán thu hút rất đông các nhà nghiên cứu tìm tòi cách giải. Vì các bài toán thuộc lớp NP-Complete ít nhiều có sự tương đồng, chỉ cần tìm ra cách giải một bài toán có thể tìm ra cách giải tất cả các bài toán còn lại. Hiện nay có khá nhiều cách giải cho bài toán này nhưng hầu hết chỉ là các cách giải gần đúng.