Giải giúp mình bài trong hình với nhé! Chủ yếu đưa ra thuật toán sử dụng thôi. Tại bài này có nhiều thuật toán có thể áp dụng mà mình không biết cái nào hiệu quả.

INPUT
6
0 1 2 1 3 4
5 0 3 2 3 4
4 1 0 2 1 2
4 2 5 0 4 3
2 5 3 5 0 2
5 4 3 3 1 0

OUTPUT
8
Trong kì nghỉ hè năm nay Sherry được bố thưởng cho một tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiến ((ì r,rất ngoan). Tất nhiên Sherry sẽ đi bằng máy bay.,Giá vé máy bay từ đất nước i đến đất nước j là $C_{ii}$ (dĩ nhiên $C_{ij}$ có thể khác C;;). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng,Sherry cũng muốn tìm cho mình một hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người (các chuyến bay ch,Sherry đều được đảm bảo an toàn tuyệt đối).,Bạn hãy giúp Sherry tìm một hành trình đi qua tất cả các nước, mỗi nước đúng một lần sao cho chi phí là bé nhất nhé.,Input,Dòng đầu tiên: N $(5

Question

Giải giúp mình bài trong hình với nhé! Chủ yếu đưa ra thuật toán sử dụng thôi. Tại bài này có nhiều thuật toán có thể áp dụng mà mình không biết cái nào hiệu quả.

INPUT
6
0 1 2 1 3 4 
5 0 3 2 3 4 
4 1 0 2 1 2 
4 2 5 0 4 3 
2 5 3 5 0 2 
5 4 3 3 1 0

OUTPUT
8
 Trong kì nghỉ hè năm nay Sherry được bố thưởng cho một tour du lịch quanh N đất nước tươi đẹp với nhiều thắng cảnh nổi tiến ((ì r,rất ngoan). Tất nhiên Sherry sẽ đi bằng máy bay.,Giá vé máy bay từ đất nước i đến đất nước j là $C_{ii}$ (dĩ nhiên $C_{ij}$ có thể khác C;;). Tuy được bố thưởng cho nhiều tiền để đi du lịch nhưng,Sherry cũng muốn tìm cho mình một hành trình với chi phí rẻ nhất có thể để dành tiền mua quà về tặng mọi người (các chuyến bay ch,Sherry đều được đảm bảo an toàn tuyệt đối).,Bạn hãy giúp Sherry tìm một hành trình đi qua tất cả các nước, mỗi nước đúng một lần sao cho chi phí là bé nhất nhé.,Input,Dòng đầu tiên: N $(5<N<16).$,Dòng thứ i trong N dòng tiếp theo: Gồm N số nguyên, số thứ j là $C_{ij}(0<C_{ij}<10001).$,Output,Gồm một dòng duy nhất ghi chi phí bé nhất tìm được.

Accepted Answer

{"userId":5258382,"userName":"Nguyễn Công Huy"}

Bài này chính là bài toán người du lịch (Traveling Salesman Problem – TSP), yêu cầu tìm hành trình đi qua tất cả các thành phố đúng một lần với chi phí nhỏ nhất.

Vì ràng buộc N ≤ 15 nên ta không thể duyệt brute force tất cả các hoán vị (N! trường hợp) vì sẽ quá lớn. Thuật toán hiệu quả và phù hợp nhất ở đây là Dynamic Programming với Bitmask.

Ý tưởng thuật toán: DP Bitmask

Ta dùng bitmask để lưu trạng thái những thành phố đã đi qua.

Ký hiệu:

dp[mask][i]: chi phí nhỏ nhất để đi qua tất cả các thành phố trong tập mask và kết thúc tại thành phố i.
mask là một số nhị phân dài N bit, bit j = 1 nếu thành phố j đã được thăm.
C[i][j] là chi phí từ thành phố i đến j.

Công thức quy hoạch động:

Trạng thái gốc:
dp[1<<i][i] = 0 (xuất phát từ i, chỉ thăm mình nó).
Chuyển trạng thái:

bash

Sao chép

Chỉnh sửa
dp[mask][i] = min(dp[mask ^ (1<<i)][j] + C[j][i])

với j thuộc mask, j != i.
Kết quả cuối:
Lấy min(dp[(1<<N) - 1][i] + C[i][start]) cho mọi i.

Độ phức tạp:

Số trạng thái: O(N * 2^N)
Mỗi trạng thái xét tối đa N cạnh → O(N² * 2^N)
Với N ≤ 15 → ~ 15² × 2¹⁵ ≈ 7.3 triệu phép tính, chạy tốt.

Code mẫu (Python):

python

Sao chép

Chỉnh sửa
INF = 10**9

def tsp(N, C):
    dp = [[INF] * N for _ in range(1 << N)]
    dp[1][0] = 0  # Bắt đầu từ thành phố 0
    
    for mask in range(1 << N):
        for u in range(N):
            if not (mask & (1 << u)):
                continue
            for v in range(N):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + C[u][v])
    
    ans = INF
    for i in range(N):
        ans = min(ans, dp[(1 << N) - 1][i] + C[i][0])
    return ans


# Đọc dữ liệu
N = int(input())
C = [list(map(int, input().split())) for _ in range(N)]

print(tsp(N, C))

Giải thích với input ví dụ:

csharp

Sao chép

Chỉnh sửa
N = 6
C = [
[0, 1, 2, 1, 3, 4],
[5, 0, 3, 2, 3, 4],
[4, 1, 0, 2, 1, 2],
[4, 2, 5, 0, 4, 3],
[2, 5, 3, 5, 0, 2],
[5, 4, 3, 3, 1, 0]
]

Thuật toán sẽ tìm đường tối ưu với chi phí = 8, đúng như output.

Nếu bạn muốn, mình có thể viết thêm phiên bản tối ưu bộ nhớ hoặc phiên bản backtracking + branch and bound để so sánh tốc độ.

Giải giúp mình bài trong hình với nhé! Chủ yếu đưa ra thuật toán sử dụng thôi. Tại bài này có nhiều thuật toán có thể áp dụng mà mình không biết cái nào hiệu quả. INPUT 6 0 1 2 1 3 4 5 0 3 2 3 4 4 1...