Khóa học Python từ Cơ bản đến Nâng cao

Bài 15.5 - Giải TSP đơn giản bằng Python

Bài toán người bán hàng (TSP) là một trong những bài toán kinh điển trong khoa học máy tính: cho một danh sách các thành phố và khoảng cách giữa từng cặp thành phố, tìm đường đi ngắn nhất để đi qua tất cả các thành phố đúng một lần và quay lại điểm xuất phát.

Trong bài này, ta sẽ sử dụng phương pháp vét cạn (brute-force) để giải bài toán TSP một cách đơn giản nhất trong Python.

1. Ý tưởng thuật toán

Chúng ta sẽ dùng:

• itertools.permutations để sinh tất cả các hoán vị (đường đi) có thể.
• Với mỗi đường đi, tính tổng khoảng cách.
• Lưu lại đường đi có tổng khoảng cách nhỏ nhất.

2. Cài đặt đơn giản với Python

import itertools

def tsp_brute_force(distance_matrix):
    n = len(distance_matrix)
    cities = list(range(n))
    min_path = None
    min_cost = float('inf')

    for path in itertools.permutations(cities):
        cost = 0
        for i in range(n - 1):
            cost += distance_matrix[path[i]][path[i + 1]]
        cost += distance_matrix[path[-1]][path[0]]  # Quay lại điểm xuất phát

        if cost < min_cost:
            min_cost = cost
            min_path = path

    return min_path, min_cost

Giải thích:

• distance_matrix[i][j]: khoảng cách từ thành phố i đến j.
• Thử mọi đường đi có thể và tính tổng chi phí.
• Giữ lại đường đi ngắn nhất.

3. Ví dụ minh hoạ

🔸 Ví dụ 1: 4 thành phố với ma trận khoảng cách đơn giản

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

path, cost = tsp_brute_force(distance_matrix)
print("Đường đi tối ưu:", path)
print("Chi phí tối thiểu:", cost)

📌 Kết quả có thể là:

Đường đi tối ưu: (0, 1, 3, 2)
Chi phí tối thiểu: 80

4. Thêm ví dụ khác để luyện tập

🔸 Ví dụ 2: 3 thành phố

distance_matrix = [
    [0, 5, 9],
    [5, 0, 10],
    [9, 10, 0]
]

path, cost = tsp_brute_force(distance_matrix)
print("Đường đi tối ưu:", path)
print("Chi phí tối thiểu:", cost)

📌 Kết quả có thể là:

Đường đi tối ưu: (0, 1, 2)
Chi phí tối thiểu: 24

5. Tổng kết

Dù thuật toán brute-force không hiệu quả với số lượng thành phố lớn (do độ phức tạp là n!), nhưng nó rất dễ hiểu, dễ triển khai và giúp bạn làm quen với ý tưởng tìm đường đi ngắn nhất.

✨ Bạn có thể thử kết hợp với Bitmask hoặc thuật toán DP để nâng cao hiệu suất trong tương lai nhé!

#HappyCoding cùng FullhouseDev! 🚀