English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtĐồ thị và Mạng lướiBài toán vận chuyển của người bán hàng
Hãy cùng suy nghĩ thêm một lần nữa về bản đồ và mạng lưới. Hãy tưởng tượng rằng một hệ thống giao hàng hóa phải đi qua
Chiếc xe tải đi giao hàng phải đi qua hết các thành phố, theo bất kỳ thức tự nào. Trong bài toán về những cây cầu Königsberg chúng ta muốn tìm thấy những con đường đi qua mỗi cạnh chỉ đúng một lần. Bây giờ chúng ta muốn tìm con đường đi qua các đỉnh đúng một lần. Những con đường này được gọi là các vòng Hamiltonian.
Có vô vàn các khả năng khác nhau của các vòng Hamiltonian trong đồ thị hoàn chỉnh. Thực tế, chúng ta có thể lấy bất kỳ đỉnh nào làm điểm khởi đầu và chọn bất kỳ thành phố còn lại nào theo bất kỳ thứ tự nào:
Diagram coming soon…
Diagram Coming Soon…
Trong bản đồi với
- ${tsmString(tsn1)}
Điều này có nghĩa là, tổng cộng có ${tsnPaths(tsn1)} cách đi. Viết tắt của kết quả này là ${tsn1}! hoặc ${tsn1} Giai thừa.
Bạn có thể tưởng tượng rằng không thể di chuyển giữa hai thành phố mà không đi qua các thành phố khác. Trong trường hợp này ta không có một đồ thị hoàn chỉnh nữa, và tìm kiếm số lượng các vòng Hamiltonian, nếu có tồn tại, là hết sức khó khăn.
Cho tới lúc này chúng ta đã bỏ qua thực tế là một số thành phố có thể xa nhau hơn những thành phố khác. Trong ứng dụng thực tế xem xét điều này là rất quan trọng: vì chúng ta không chỉ muốn tìm đường đi bất kỳ mà là đường đi ngắn nhất. Bài toán này được gọi là Bài toán vận chuyển của người bán hàng. Bài toán này phải được giải không chỉ cho việc vận chuyển và hậu cần (logistics), mà có liên quan đến việc lắp đặt linh kiện bán dẫn và microchips, để làm cho máy tính nhanh hơn, hay được sử dụng để phân tích cấu trúc của
Một phương pháp đơn giản là tìm tất cả các đường đi có thể có, tìm độ dài đường đi của mỗi con đường và chọn ra phương án đi ngắn nhất. Tuy nhiên ta vừa thấy rằng, duy với
Rất tiếc là không có thuật toán nào hiệu quả hơn để giải bài toán vận chuyển của người bán hàng. Thay vào đó, các nhà toán học và nhà khoa học máy tính đã cùng nhau phát triển một số thuật toán tìm ra những giải pháp tốt, mặc dù nó không phải là giải pháp tốt nhất. Những thuật toán này chỉ cho ra những giải pháp ước chừng được gọi là Heuristics.
Hãy thử sắp xếp lại vị trí của các thành phố trên bản đồ sau. Bạn có thể loại bỏ một thành phố bằng cách nhấn vào thành phố và nhấn vào một chỗ khác để thêm thành phố vào.
Thuật toán tham lam (hay thuật toán Hàng xóm gần nhất) rất đơn giản: bạn xuất phát từ một thành phố bất kỳ và tiếp tục di chuyển đến các thành phố gần nhất mà bạn chưa đi qua. Khi bạn đã đi qua hết tất cả các thành phố thì dừng lại.
Sẽ có hình ảnh bổ sung sớm…
Bạn thấy rằng, trung bình, các đường đi tìm thấy sử dụng "thuật toán tham lam" thì thường dài hơn 25% so với phương án các đường đi ngắn nhất.
Thuật toán 2-Opt bắt đầu với con đường bất kỳ ngẫu nhiên. Sau đó bạn liên tục chọn hai cạnh và đổi lại nếu chúng giúp giảm chiều dài đường đi. Bạn dừng lại khi bạn không thể đổi hai cạnh được nữa để rút ngắn chiều dài đường đi.
Sẽ có hình minh họa sớm…
Rốt cuộc là, rất lâu trước khi máy tính ra đời, thiên nhiên đã có cách thông minh tìm ra đường đi tối ưu giữa các địa điểm: thể hiện ở bầy kiến.
Những chú kiến muốn tìm thấy đường đi ngắn nhất giữa tổ của chúng và nguồn thức ăn tìm thấy. Chúng có thể liên lạc với nhau bằng cách tiết ra chất đánh dấu đường đi, giúp những chú kiến khác đi theo.
- Đàn kiến gửi đi một số chú tiên phong, đi theo các hướng ngẫu nhiên khác nhau. Một khi một chú tìm được nguồn thức ăn sẽ quay về tổ, để lại dấu vết trên đường đi là chất pheromone.
- Những chú kiến khác một khi bắt gặp đường đánh dấu đó thì sẽ đi theo đến nguồn thức ăn. Và trên đường trở về, mỗi chú kiến lại tiết ra chất pheromone, để khẳng định đánh dấu đường đi.
- Thời gian trôi qua, chất pheromone bốc hơi. Đường đi càng dài thì càng mất thời gian và chất pheromone càng dễ bay hơi. Những con đường ngắn, mặt khác, sẽ được khẳng định và đánh dấu lại nhanh chóng hơn, bởi vậy sức mạnh của đàn kiến sẽ tăng lên.
Biểu đồ đang được cập nhật…
Các thuật toán liên quan đến Hệ thống Bầy Kiến (Ant Colony System - ACS) tìm cách bắt chước hệ thống này trên máy tính, sử dụng nhiều chú kiến “ảo”. Chúng có thể nhaanh chóng tìm ra giải pháp tốt cho bài toán vận chuyển của người bán hàng.
Một điểm đặc biệt hữu dụng của thuật toán ACS là chúng có thể chạy liên tục và thích nghi theo thời gian thực với những thay đổi của đồ thị. Những thay đổi này có thể gây ra do tai nạn, tắt đường trên hệ thống giao thông, hay sự tăng đột biến kết nối vào các trang web hay hệ thống máy tính.
Bài toán vận chuyển của người bán hàng khó ở mức độ NP
Tìm ra được thuật toán nhanh và chính xác sẽ có tác động rất lớn vào ngành khoa học máy tính: nghĩa là sẽ có thuật toán nhanh cho tất cả các bài toán khó mức độ NP-hard. Nó cũng làm cho hầu hết các hệ thống an ninh internet vô dụng, vốn được xây dựng dựa trên nền tảng có những bài toán phức tạp máy tính không giải được.
Tìm được một thuật toán nhanh giải quyết bài toán vận chuyển của người giao hàng cũng giúp giải quyết một trong những bài toán khó nổi tiếng trong toán học và khoa học máy tính, bài toán P vs NP. Đây là một trong 7