DSA Bài toán người bán hàng du lịch

Bài toán người bán hàng du lịch

Bài toán Người bán hàng du lịch nói rằng bạn là một nhân viên bán hàng và bạn phải đến thăm một số thành phố hoặc thị trấn.

Ngoại trừ thuật toán Held-Karp (khá tiên tiến và tốn thời gian, (\(O(2^nn^2)\)) và sẽ không được mô tả ở đây), không có cách nào khác để tìm ra con đường ngắn nhất ngoài để kiểm tra tất cả các tuyến đường có thể.

Điều này có nghĩa là độ phức tạp về thời gian để giải quyết vấn đề này là \(O(n!)\), nghĩa là cần kiểm tra 720 tuyến đường cho 6 thành phố, 40.320 tuyến đường phải được kiểm tra cho 8 thành phố và nếu bạn có 10 thành phố để ghé thăm , hơn 3,6 triệu tuyến đường phải được kiểm tra!

Bài toán Người bán hàng du lịch (TSP) là một bài toán rất thú vị để nghiên cứu vì nó rất thực tế nhưng tốn thời gian giải đến mức gần như không thể tìm được đường đi ngắn nhất, ngay cả trong một biểu đồ chỉ có 20-30 đỉnh.

Nếu chúng ta có một thuật toán hiệu quả để giải Bài toán người bán hàng du lịch, thì hậu quả sẽ rất lớn trong nhiều lĩnh vực, chẳng hạn như thiết kế chip, định tuyến phương tiện, viễn thông và quy hoạch đô thị.

Kiểm tra tất cả các tuyến đường để giải quyết vấn đề nhân viên bán hàng du lịch

Để tìm ra giải pháp tối ưu cho Bài toán người bán hàng du lịch, chúng tôi sẽ kiểm tra tất cả các tuyến đường có thể và mỗi khi tìm được tuyến đường ngắn hơn, chúng tôi sẽ lưu trữ để cuối cùng chúng tôi sẽ có được tuyến đường ngắn nhất.

Tốt: Tìm thấy con đường tổng thể ngắn nhất.

Xấu: Đòi hỏi phải tính toán rất nhiều, đặc biệt đối với một số lượng lớn các thành phố, điều đó có nghĩa là việc này rất tốn thời gian.

Cách tìm ra giải pháp cho một vấn đề như vậy được gọi là bạo lực .

Brute Force không thực sự là một thuật toán, nó chỉ có nghĩa là tìm ra giải pháp bằng cách kiểm tra tất cả các khả năng, thường là do thiếu cách tốt hơn để thực hiện điều đó.

Lý do tại sao cách tiếp cận mạnh mẽ để tìm ra con đường ngắn nhất (như được hiển thị ở trên) lại tốn thời gian là vì chúng tôi đang kiểm tra tất cả các tuyến đường và số lượng tuyến đường có thể tăng lên rất nhanh khi số lượng thành phố tăng lên.

 from itertools import permutations

def calculate_distance(route, distances):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]
    return total_distance

def brute_force_tsp(distances):
    n = len(distances)
    cities = list(range(1, n))
    shortest_route = None
    min_distance = float('inf')
    
    for perm in permutations(cities):
        current_route = [0] + list(perm)
        current_distance = calculate_distance(current_route, distances)
        
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_route = current_route
    
    shortest_route.append(0)
    return shortest_route, min_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = brute_force_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

Sử dụng thuật toán tham lam để giải quyết vấn đề nhân viên bán hàng du lịch

Vì việc kiểm tra mọi tuyến đường có thể để giải quyết Vấn đề nhân viên bán hàng du lịch (như chúng tôi đã làm ở trên) cực kỳ tốn thời gian nên thay vào đó, chúng tôi có thể tìm một tuyến đường ngắn bằng cách chỉ đi đến thành phố chưa được ghé thăm gần nhất trong mỗi bước, nhanh hơn nhiều.

Tốt: Tìm ra giải pháp cho Bài toán Người bán hàng du lịch nhanh hơn nhiều so với việc kiểm tra tất cả các tuyến đường.

Xấu: Không tìm thấy tuyến đường tổng thể ngắn nhất, nó chỉ tìm tuyến đường ngắn hơn nhiều so với tuyến đường ngẫu nhiên trung bình.

Cách tìm gần đúng con đường ngắn nhất trong Bài toán nhân viên bán hàng du lịch, bằng cách chỉ đi đến thành phố chưa được ghé thăm gần nhất trong mỗi bước, được gọi là thuật toán tham lam .

Như bạn có thể thấy bằng cách chạy mô phỏng này một vài lần, các tuyến đường được tìm thấy không hoàn toàn không hợp lý. Có lẽ ngoại trừ một vài lần khi các đường thẳng cắt nhau, đặc biệt là ở cuối thuật toán, lộ trình kết quả sẽ ngắn hơn rất nhiều so với những gì chúng ta có thể nhận được bằng cách chọn ngẫu nhiên thành phố tiếp theo.

 def nearest_neighbor_tsp(distances):
    n = len(distances)
    visited = [False] * n
    route = [0]
    visited[0] = True
    total_distance = 0

    for _ in range(1, n):
        last = route[-1]
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and distances[last][i] < min_dist:
                min_dist = distances[last][i]
                nearest = i
        route.append(nearest)
        visited[nearest] = True
        total_distance += min_dist

    total_distance += distances[route[-1]][0]
    route.append(0)
    return route, total_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = nearest_neighbor_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

Các thuật toán khác tìm ra giải pháp gần như tối ưu cho bài toán nhân viên bán hàng du lịch

Ngoài việc sử dụng thuật toán tham lam để giải Bài toán người bán hàng du lịch, còn có các thuật toán khác có thể tìm ra các giá trị gần đúng cho tuyến đường ngắn nhất.

Các thuật toán này phổ biến vì chúng hiệu quả hơn nhiều so với việc thực sự kiểm tra tất cả các giải pháp có thể, nhưng cũng như thuật toán tham lam ở trên, chúng không tìm ra con đường tổng thể ngắn nhất.

Các thuật toán được sử dụng để tìm giải pháp gần như tối ưu cho Bài toán nhân viên bán hàng du lịch bao gồm:

• Heuristic 2-opt: Một thuật toán cải thiện giải pháp theo từng bước, trong mỗi bước sẽ loại bỏ hai cạnh và kết nối lại hai đường dẫn theo một cách khác để giảm tổng chiều dài đường dẫn.
• Thuật toán di truyền: Đây là một loại thuật toán lấy cảm hứng từ quá trình chọn lọc tự nhiên và sử dụng các kỹ thuật như chọn lọc, đột biến và lai ghép để phát triển các giải pháp cho các vấn đề, bao gồm cả TSP.
• Ủ mô phỏng: Phương pháp này được lấy cảm hứng từ quá trình ủ trong luyện kim. Nó liên quan đến việc làm nóng và sau đó làm nguội từ từ vật liệu để giảm khuyết tật. Trong bối cảnh TSP, nó được sử dụng để tìm ra giải pháp gần như tối ưu bằng cách khám phá không gian giải pháp theo cách cho phép thỉnh thoảng chuyển sang các giải pháp kém hơn, giúp tránh bị mắc kẹt trong các điểm cực tiểu cục bộ.
• Tối ưu hóa đàn kiến: Thuật toán này được lấy cảm hứng từ hành vi của loài kiến ​​trong việc tìm đường đi từ đàn kiến ​​đến nguồn thức ăn. Đó là một kỹ thuật xác suất phức tạp hơn để giải quyết các vấn đề tính toán có thể được ánh xạ để tìm đường dẫn tốt thông qua biểu đồ.

Độ phức tạp về thời gian để giải quyết vấn đề nhân viên bán hàng du lịch

Để nhanh chóng có được giải pháp gần tối ưu, chúng ta có thể sử dụng thuật toán tham lam chỉ đi đến thành phố chưa được ghé thăm gần nhất trong mỗi bước, như trong mô phỏng thứ hai trên trang này.

Giải bài toán người bán hàng du lịch theo cách tham lam như vậy, có nghĩa là ở mỗi bước, khoảng cách từ thành phố hiện tại đến tất cả các thành phố chưa được ghé thăm khác được so sánh và điều đó mang lại cho chúng ta độ phức tạp về thời gian \(O(n^2) \) .

Nhưng việc tìm ra con đường ngắn nhất trong số chúng đều đòi hỏi nhiều thao tác hơn và độ phức tạp về thời gian là \(O(n!)\), như đã đề cập trước đó, có nghĩa là đối với 4 thành phố, có 4! các tuyến đường có thể, giống như \(4 \cdot 3 \cdot 2 \cdot 1 = 24\). Và chỉ đối với 12 thành phố chẳng hạn, có \(12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479.001.600\) các tuyến đường khả thi!

Xem độ phức tạp về thời gian của thuật toán tham lam \(O(n^2)\), so với độ phức tạp về thời gian để tìm tuyến đường ngắn nhất bằng cách so sánh tất cả các tuyến đường \(O(n!)\), trong hình ảnh bên dưới.

Nhưng có hai điều chúng ta có thể làm để giảm số lượng tuyến đường cần kiểm tra.

Trong Bài toán Người bán hàng du lịch, tuyến đường bắt đầu và kết thúc ở cùng một địa điểm, tạo thành một chu kỳ. Điều này có nghĩa là độ dài của tuyến đường ngắn nhất sẽ giống nhau cho dù chúng tôi bắt đầu ở thành phố nào. Đó là lý do tại sao chúng tôi đã chọn một thành phố cố định để bắt đầu cho mô phỏng ở trên và điều đó làm giảm số lượng tuyến đường có thể có từ \(n !\) đến \((n-1)!\).

Ngoài ra, do các tuyến đường này đi theo chu kỳ nên một tuyến đường có khoảng cách như nhau nếu chúng ta đi theo hướng này hay hướng khác, nên thực ra chúng ta chỉ cần kiểm tra khoảng cách của một nửa số tuyến đường, vì nửa còn lại sẽ chỉ là các tuyến đường giống nhau theo hướng ngược lại nên số tuyến đường chúng ta cần kiểm tra thực tế là \( \frac{(n-1)!}{2}\).

Nhưng ngay cả khi chúng tôi có thể giảm số lượng tuyến đường chúng tôi cần kiểm tra xuống \( \frac{(n-1)!}{2}\), thì độ phức tạp về thời gian vẫn là \( O(n!)\), vì đối với rất lớn \(n\), việc giảm \(n\) đi một và chia cho 2 không tạo ra thay đổi đáng kể về độ phức tạp thời gian tăng lên khi \(n\) tăng lên.

Để hiểu rõ hơn về độ phức tạp về thời gian, hãy truy cập trang này .

Các vấn đề thực tế của nhân viên bán hàng du lịch phức tạp hơn

Trọng số cạnh trong biểu đồ trong bối cảnh này của Bài toán người bán hàng du lịch cho chúng ta biết việc đi từ điểm này đến điểm khác khó đến mức nào và đó là tổng trọng số cạnh của tuyến đường mà chúng ta muốn giảm thiểu.

Cho đến nay trên trang này, trọng số của cạnh là khoảng cách theo đường thẳng giữa hai điểm. Và điều đó làm cho việc giải thích và trình bày Bài toán Người bán hàng du lịch trở nên dễ dàng hơn nhiều.

Nhưng trong thế giới thực, có nhiều thứ khác ảnh hưởng đến trọng lượng cạnh:

1. Chướng ngại vật: Khi di chuyển từ nơi này sang nơi khác, chúng ta thường cố gắng tránh những chướng ngại vật như cây cối, sông suối, nhà cửa chẳng hạn. Điều này có nghĩa là nó dài hơn và mất nhiều thời gian hơn để đi từ A đến B, đồng thời giá trị trọng số của cạnh cần phải được tăng lên để tính đến yếu tố đó, vì nó không còn là một đường thẳng nữa.
2. Mạng lưới Giao thông: Chúng ta thường đi theo một con đường hoặc sử dụng hệ thống giao thông công cộng khi đi du lịch và điều đó cũng ảnh hưởng đến mức độ khó khăn khi đi (hoặc gửi một gói hàng) từ nơi này đến nơi khác.
3. Điều kiện giao thông: Tắc nghẽn giao thông cũng ảnh hưởng đến thời gian di chuyển, do đó điều đó cũng phải được phản ánh trong giá trị trọng số của cạnh.
4. Ranh giới pháp lý và chính trị: Chẳng hạn, việc vượt biên có thể khiến một tuyến đường khó chọn hơn tuyến đường khác, điều đó có nghĩa là tuyến đường thẳng ngắn nhất có thể chậm hơn hoặc tốn kém hơn.
5. Yếu tố kinh tế: Sử dụng nhiên liệu, sử dụng thời gian của nhân viên, bảo trì phương tiện, tất cả những thứ này đều tốn tiền và cũng phải được tính vào trọng lượng cạnh.

Như bạn có thể thấy, chỉ sử dụng khoảng cách đường thẳng làm trọng số của các cạnh có thể quá đơn giản so với bài toán thực tế. Và việc giải Bài toán Người bán hàng du lịch cho một mô hình bài toán đơn giản hóa như vậy có thể sẽ cho chúng ta một giải pháp không tối ưu về mặt thực tế.

Không dễ để hình dung Bài toán Người bán hàng du lịch khi độ dài cạnh không chỉ là khoảng cách đường thẳng giữa hai điểm nữa mà máy tính xử lý rất tốt điều đó.